5-qs/5-qs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{5}{Tøidìní a QuickSort}{(???)}
   4
   5 Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
   6 nejefektivnìji posloupnost setøídit. Mù¾eme napøíklad pou¾ít metodu Rozdìl a panuj:
   7
   8 \s{Algoritmus:} (QuickSort)
   9
  10 \def\concat{\mathop{\hbox{.}}}
  11
  12 \algo
  13 \:Pokud $\vert X\vert \leq 1$, vrátíme~$X$.
  14 \:Vybereme pivota $p \in X$ (pozdìji upøesníme, jak).
  15 \:$M = \{x \in X ; x \le p\}$
  16 \:$P = \{x \in X ; x = p\}$
  17 \:$V = \{x \in X ; x \ge p\}$
  18 \:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$ \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
  19 \endalgo
  20
  21 \s{Pozorování:}
  22 \itemize\ibull
  23 \:zastaví se
  24 \:vydá správný výsledek (dùkaz napø. indukcí podle $\vert X\vert$)
  25 \:pivot
  26   \itemize\istar
  27   \:pøi ideální volbì: $$ T(n) = 2T(n/2) + O(n) = O(n\log n) $$ (jako u mergesortu)
  28   \:pøi ¹patné volbì: $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2) $$
  29   \endlist
  30 \:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu
  31 \endlist
  32
  33 \s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$
  34 \foot{Vìta': QS s pevnou volbou pivota má v prùmìru pøes v¹echny permutace na vstupu èasovou slo¾itost $\O(n\log n)$.}
  35
  36 \proof
  37
  38 \figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize}
  39
  40 Provedeme rozdìlováním na fáze, pøi¾em¾ fází rozumíme cestu ve stromu, která sleduje
  41 vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián.
  42 \qed
  43
  44 \s{Pozorování:}
  45
  46 \itemize\ibull
  47 \:Ka¾dá fáze rozdìlí vstup na disjunktní èásti a pivoty $X_1, \ldots, X_k$ ($k \geq 2$)
  48
  49 \:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$
  50
  51 \:$\sum_i  \vert X_i \vert \leq \vert X \vert$
  52
  53 \:prùmìrná délka fáze je nejvý¹e~2 (proto¾e pravdìpodobnost na vybrání l¾imediánu je alespoò $1/2$)
  54
  55 \:v prùmìru poèítáme jednu fázi v èase $\O(n)$
  56
  57 \:Proto $T(n) = \sum_i T (n_i) + \O(n)$, kde $n = \vert X \vert$, $n_i = \vert X_i \vert$.
  58
  59 \endlist
  60
  61 \s{Komprimovaný strom}
  62
  63 <!-- obrázek -->
  64
  65 Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost
  66 fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti
  67 velikosti~1).
  68
  69 Práce na jedné hladinì je $\O(n)$.
  70
  71 $\Downarrow$
  72
  73 Celková èasová slo¾itost je tedy v~prùmìru $\O(n \log n)$.
  74
  75 Pamì»ové nároky jsou:
  76 $\O(n)$ na pomocné pole
  77 $\O(n)$ na zásobníku
  78
  79
  80 Dal¹í modifikace QSortu mù¾ete najít na:
  81 http://mj.ucw.cz/vyuka/0607/ads1/quicksort.pdf
  82
  83
  84 \s{Vìta:}
  85 Ka¾dý tøídící algoritmus zalo¾ený na porovnávání
  86 (a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì
  87 $\Omega (n \log n)$ porovnání.
  88
  89 \proof
  90 \itemize\ibull
  91   \:BÚNO nejdøíve algoritmus porovnává a potom
  92   prohazuje (algoritmus mù¾eme upravit tak aby
  93   prohazoval a¾ na~konci).
  94
  95   \:BÚNO hledáme vstupy, které jsou permutace na $\{1 - n\}$.
  96
  97   \:Sestrojíme rozhodovací strom na¹eho algoritmu
  98
  99 <!-- obrázek -->
 100
 101   \:Je vidìt, ¾e existence dvou rùzných $\Pi_1$ a $\Pi_2 $,
 102   pøi kterých bychom skonèili ve stejném listu vede ke sporu,
 103   pøitom poèet listù $\geq n!$
 104 \endlist
 105
 106 {\narrower
 107   \s{Pozorování:} Binární strom hloubku $k$ má poèet listù $\leq 2^k$.
 108   Uva¾me binární strom hloubky $k$ s maximálním poètem listù, pak v¹echny listy
 109   le¾í na poslední hladinì. Víme, ¾e na $i$-té hladinì je $2^i$ vrcholù a
 110   poèet listù je $2^k$. Odtud plyne, ¾e v ka¾édém binárním stromu je maximálnì $2^k$ listù
 111
 112 }
 113
 114   pokraèování pùvodního dùkazu...
 115
 116   Z toho co u¾ víme plyne, ¾e hloubka stromu je nejvý¹e $\log(n!)$.
 117
 118   Z diskrétní matematiky víme ¾e: \
 119   ${n^{n / 2} \leq n!} \leq (n / 2)^n$
 120
 121   My potøebujeme jen levou èást, tedy ¾e ${n^{n / 2} \leq n!}$
 122   Toto jde dokázat pou¾ítím "AG Nerovnosti"
 123
 124   ...tedy dostáváme, ¾e hloubka stromu je $\geq \log (n^{n / 2}) = (n / 2)
 125   \log (n) \Longrightarrow \Omega (n \log n)$
 126
 127 \qed
 128
 129 \bye