5-qs/5-qs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{3}{Tøídìní}{(N.O.Body)}
   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 \s{Pozorování:}
  37
  38 \itemize\ibull
  39 \:Ka¾dá fáze rozdìlí vstup na disjunktní èásti + pivoty $X_1, \ldots, X_k$ ($k \geq 2$)
  40
  41 \:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$
  42
  43 \:$\sum_i  \vert X_i \vert \leq \vert X \vert$
  44
  45 \: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$)
  46
  47 \:v prùmìru poèítáme jednu fázi v èase $\O(n)$
  48
  49 \:Proto $T(n) = \sum_i T (n_i) + \O(n)$, kde $n = \vert X \vert$, $n_i = \vert X_i \vert$.
  50
  51 \endlist
  52
  53 \s{Komprimovaný strom}
  54
  55 Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost
  56 fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti
  57 velikosti~1).
  58
  59 Práce na jedné hladinì je $\O(n)$.
  60
  61 $\Downarrow$
  62
  63 Celkem je v~prùmìru $\O(n \log n)$.
  64
  65 \s{Vìta:}
  66 Ka¾dý tøídící algoritmus zalo¾ený na porovnávání
  67 (a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì
  68 $\Omega (n \log n)$ porovnání.
  69
  70 \bye
  71
  72 \proof
  73   1) {\tmsamp{BÚNO}} nejdøíve algoritmus porovnává a potom
  74   prohazuje
  75
  76   {\small{ (algoritmus mù¾eme upravit tak aby
  77   prohazoval a¾ nakonci)}}
  78
  79   2) {\tmsamp{BÚNO}} hledáme vstupy, které jsou permutace na \{1 - n\}
  80
  81   3) Sestrojíme rozhodovací strom ne¹eho algoritmu
  82
  83   \begin{tabular}{l}
  84     \
  85     \begin{tabular}{|l|}
  86       \hline
  87       $x_1 < x_2$\\
  88       \hline
  89     \end{tabular}
  90   \end{tabular}
  91
  92   $\swarrow
  93   \searrow$
  94
  95   \begin{tabular}{|l|}
  96     \hline
  97     $x_1 < x_3$\\
  98     \hline
  99   \end{tabular}
 100
 101   $\swarrow \searrow$ \
 102   Ka¾dý algoritmus mù¾eme popsat podobným Stromem
 103
 104   \begin{tabular}{|l|}
 105     \hline
 106     $x_2 < x_3$\\
 107     \hline
 108   \end{tabular}
 109
 110    $\swarrow \searrow$
 111
 112   {\tmstrong{$x_1 < x_2 < x_3$}} $\Leftarrow$ \
 113   {\tmstrong{Listy}} {\small{- algoritmus u¾ zde dotøídil a u¾ bude jen
 114   pøehazovat a pak zkonèí}}
 115
 116
 117
 118   Jde vidìt ¾e $\tmmathbf{}$Existence dvou rùzných $\Pi_1 a \Pi_2 $,
 119
 120   pøi kterých bychom zkonèili ve stejném listu vede ke Sporu
 121
 122
 123
 124   pøitom {\tmstrong{\# listù $\geqslant$ n!}}
 125
 126
 127
 128   {\tmstrong{Pozorování:}} Binární strom hloubku {\tmstrong{k}}
 129   má {\tmstrong{poèet listù $\leq 2^k$ }}
 130
 131   \begin{tmparmod}{0pt}{2cm}{0pt}
 132     \begin{proof}
 133       {\small{}}Uva¾me binární strom hloubky k s maximálním
 134       poètem listù
 135
 136       pak v¹echny listy le¾í na poslední hladinì
 137
 138       víme ¾e na i-té hladinì je $2^i$ vrcholù
 139
 140       $\tmmathbf{\Rightarrow}$ poèet listù je $2^k$
 141
 142       \tmmathbf{$\Rightarrow$} v ka¾édém binárním stromu je
 143       maximálnì $2^k$ listù
 144     \end{proof}
 145   \end{tmparmod}
 146
 147   {\tiny{pokraèování pùvodního dùkazu...}}
 148
 149   Z toho co u¾ víme plyne ¾e $\Rightarrow$\begin{tabular}{l}
 150
 151   \end{tabular}Hloubka stromu je $\geqslant$ log(n!)
 152
 153   {\small{z Diskrétní matematiky víme ¾e: \
 154   $\tmmathbf{n^{n / 2} \leq n!} \leq (n / 2)^n$}}
 155
 156   {\small{ Udìlá se to pomocí {\tmstrong{AG
 157   Nerovnosti}}}}
 158
 159   tedy $\Rightarrow$ Hloubka stromu je $\geqslant \log (n^{n / 2}) = (n / 2)
 160   \log (n) \Longrightarrow \tmmathbf{\Omega (n \log n)}$
 161
 162
 163 \end{proof}
 164
 165 \end{document}
 166
 167 \bye