5-qs/5-qs.tex

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