5-qs/5-qs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{5}{QuickSort a slo¾itost tøídìní}{(Michal Sta¹a, ???)}
   4
   5 Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
   6 nejefektivnìji posloupnost setøídit. Uká¾eme si tøídící algoritmus QuickSort
   7 (pro pøátele QS) zalo¾ený na metodì Rozdìl a panuj:
   8
   9 \s{Algoritmus:} (QuickSort)
  10
  11 \def\concat{\mathop{\hbox{.}}}
  12
  13 \algo
  14 \:Pokud $\vert X\vert \leq 1$, vrátíme~$X$.
  15 \:Vybereme pivota $p \in X$.\foot{pozdìji upøesníme, jak}
  16 \:$M \leftarrow \{x \in X ; x \le p\}$.
  17 \:$P \leftarrow \{x \in X ; x = p\}$.
  18 \:$V \leftarrow \{x \in X ; x \ge p\}$.
  19 \:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$. \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
  20 \endalgo
  21
  22 \s{Rozbor:}
  23 V¹imnìme si, ¾e QS se urèitì zastaví a také ¾e vydá
  24 správný výsledek. To mù¾eme ovìøit napø. indukcí podle $\vert X\vert$.
  25
  26 Podobnì jako u~vybírání $k$-tého nejmen¹ího prvku v~minulých pøedná¹kách
  27 i zde èasová slo¾itost závisí hlavnì na~volbì pivota. Kdybychom za~pivota
  28 zvolili medián, vy¹la by èasová slo¾itost stejnì jako u~MergeSortu:
  29   $$ T(n) = 2T(n/2) + O(n) = O(n\log n). $$
  30 Pokud naopak budeme volit pivota ne¹ikovnì, dostaneme:
  31   $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2). $$
  32 V ideálním pøípadì bychom tedy chtìli za pivota zvolit medián, av¹ak jeho pøímým výpoètem
  33 bychom algoritmus pøíli¹ zpomalili.
  34 Pou¾ívá se proto mnoho zpùsobù, jak vybrat rychle pivota blízkého mediánu.
  35 Èasto pou¾ívanou metodou je náhodný výbìr, v~praxi realizovaný nìjakým pseudonáhodným
  36 generátorem. Uká¾eme, ¾e v~tomto pøípadì je QS v~prùmìrném pøípadì rychlý:
  37
  38 \s{Vìta:} QS s~náhodnou volbou pivota má èasovou slo¾itost v~prùmìru
  39 $\O(n\log n)$.
  40
  41 \s{Poznámka:} Stejnì jako u~výbìru $k$-tého nejmen¹ího prvku bychom také
  42 mohli ukázat, ¾e QS s~pevnou volbou pivota spu¹tìný na~náhodnou permutaci
  43 má tuté¾ èasovou slo¾itost. Detaily nicménì vynecháme.
  44
  45 \noindent {\sl Dùkaz vìty:}
  46
  47 Rozdìlíme bìh algoritmu na~fáze, pøièem¾ fází rozumíme cestu ve~stromu volání,
  48 která sleduje vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián.
  49
  50 \figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize}
  51
  52 Ka¾dá fáze pøitom rozdìlí vstup na~disjunktní èásti $X_1, \ldots, X_k$ ($k\ge 2$)
  53 a pivoty, kteøí je oddìlují. Proto je $\sum_i n_i \leq n$,
  54 kde $n$ znaèí velikost vstupu a~$n_i$ velikost $i$-té èásti. Velikost ka¾dé
  55 èásti je navíc nejvý¹e $3/4 \cdot n$ (na~konci fáze to platí proto, ¾e jsme
  56 zvolili l¾imedián, pøedtím jsme v¾dy oddìlili men¹í z~èástí, èili nejvý¹e $n/2$).
  57
  58 Jedna iterace algoritmu trvá~$\O(n)$ a jeliko¾ l¾imedián vybereme s~pravdìpodobností alespoò $1/2$,
  59 je v~jedné fázi v~prùmìru $\O(1)$ iterací a celá fáze proto v~prùmìru trvá èas~$\O(n)$.
  60 Z~toho dostaneme následující rekurenci pro prùmìrnou èasovou slo¾itost celého algoritmu:
  61 $${\bb E}T(n) = \sum_i {\bb E}T (n_i) + \O(n).$$
  62
  63 Tento typ rekurence jsme je¹tì nepotkali a Kuchaøková vìta na~ni nezabere,
  64 ov¹em mù¾eme si pomoci jednoduchou úvahou. Pøedstavme si, ¾e v~na¹em stromu
  65 rekurzivních volání zkomprimujeme ka¾dou fázi do~jednoho vrcholu. Tím vznikne
  66 strom, který odpovídá algoritmu, jen¾ v~jedné iteraci v~prùmìrnì lineárním
  67 èase rozdìlí vstup na~nìkolik èástí a rekurzivnì se na~nì zavolá.
  68
  69 \s{FIXME:} Obrázek
  70
  71 Nový strom má logaritmickou hloubku, proto¾e na~ka¾dé dal¹í hladinì jsou
  72 délky posloupností nejvý¹e $3/4$ délek z~pøedchozí hladiny. Navíc souèet
  73 délek pøes ka¾dou hladinu je maximálnì~$n$. Proto na~ka¾dé hladinì
  74 trávíme èas v~prùmìru $\O(n)$ a v~celém stromu tedy $\O(n\log n)$.
  75 \qed
  76
  77 \s{Pozorování:} Na¹e první verze QS spotøebuje lineární mno¾ství pamìti
  78 na~pomocné pole a na~zásobník. Na~pøedná¹ce jsme ukazovali rùzná jeho
  79 praktická vylep¹ení, které staèí pomocná pamì» o~velikosti $\O(\log n)$.
  80 Detaily viz webové stránky pøedná¹ky.
  81
  82 Známe u¾ nìkolik tøídících algoritmù s~èasovou slo¾itostí $\O(n\log n)$.
  83 Následující vìta ukazuje, ¾e efektivnìj¹í algoritmus v~obecném pøípadì
  84 nese¾eneme.
  85
  86 \s{Vìta:}
  87 Ka¾dý tøídící algoritmus zalo¾ený na porovnávání a prohazování prvkù
  88 potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání.
  89
  90 \proof
  91 \itemize\ibull
  92   \:BÚNO nejdøíve algoritmus porovnává a potom
  93   prohazuje (algoritmus mù¾eme upravit tak, aby si pamatoval
  94   aktuální permutaci prvkù a podle ní prohazoval a¾ na~konci).
  95
  96   \:BÚNO je vstup algoritmu permutace na~mno¾inì $\{1, \ldots, n\}$.
  97
  98   \:Chování algoritmu popí¹eme rozhodovacím stromem. Jeho vnitøní vrcholy
  99     urèují jednotlivá porovnání prvkù, listy odpovídají okam¾ikùm, kdy
 100     algoritmus pøestal porovnávat a zaèal prohazovat.
 101
 102 \s{FIXME: Obrázek}
 103
 104   \:V¹imneme si, ¾e nemohou existovat dvì vstupní permutace, pro které
 105     by algoritmus skonèil v~tém¾e listu rozhodovacího stromu, jeliko¾
 106     v~okam¾iku, kdy algoritmus dorazí do~listu, nemù¾e u¾ získávat
 107     ¾ádné informace o~vstupu a ¾ádná posloupnost prohození nemù¾e
 108     setøídit jak první, tak druhou permutaci. Listù stromu je tedy
 109     alespoò tolik, kolik je rùzných vstupù, tedy~$n!$.
 110
 111 {\parindent=\leftskip\narrower
 112   \s{Lemmátko:} Binární strom hloubky~$k$ má nejvý¹e $\leq 2^k$ listù.
 113   \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s~maximálním poètem
 114   listù. V~takovém stromu budou v¹echny listy urèitì le¾et na~poslední hladinì
 115   (kdyby nele¾ely, mù¾eme pod nìkterý list na~vy¹¹í hladinì pøidat dal¹í dva vrcholy a získat
 116   tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na~$i$-té hladinì je nejvý¹e $2^i$
 117   vrcholù, v¹ech listù je nejvý¹e~$2^k$.
 118   \qed
 119
 120 }
 121
 122   Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò
 123   $\log n!$.
 124
 125   \:Zbytek je u¾ snadné cvièení z~diskrétní matematiky:
 126
 127 {\parindent=\leftskip\narrower
 128   \s{Lemmátko:} $ n! \ge n^{n / 2} $.
 129   \par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$,
 130   co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$.
 131   Pøitom pro ka¾dé $1\le k\le n$ je $k(n+1-k) = kn + k - k^2 = n + (k-1)n + k(1-k) = n + (k-1)(n-k) \ge n$.
 132   Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$.
 133   \qed
 134
 135 }
 136
 137   Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$,
 138   co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v~nejhor¹ím pøípadì.
 139 \qed
 140
 141 \bye