\input ../lecnotes.tex
-\prednaska{3}{Tøídìní}{(N.O.Body)}
+\prednaska{5}{QuickSort a slo¾itost tøídìní}{(Michal Sta¹a, Jan Návrat)}
Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co
-nejefektivnìji posloupnost setøídit. Mù¾eme napøíklad pou¾ít metodu Rozdìl a panuj:
+nejefektivnìji posloupnost setøídit. Uká¾eme si tøídící algoritmus QuickSort
+(pro pøátele QSort nebo QS) zalo¾ený na metodì Rozdìl a panuj:
\s{Algoritmus:} (QuickSort)
-
\def\concat{\mathop{\hbox{.}}}
\algo
\:Pokud $\vert X\vert \leq 1$, vrátíme~$X$.
-\:Vybereme pivota $p \in X$ (pozdìji upøesníme, jak).
-\:$M = \{x \in X ; x \le p\}$
-\:$P = \{x \in X ; x = p\}$
-\:$V = \{x \in X ; x \ge p\}$
-\:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$ \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
+\:Vybereme pivota $p \in X$.\foot{pozdìji upøesníme, jak}
+\:$M \leftarrow \{x \in X ; x \le p\}$.
+\:$P \leftarrow \{x \in X ; x = p\}$.
+\:$V \leftarrow \{x \in X ; x \ge p\}$.
+\:Vrátíme $\<Quicksort>(M) \concat P \concat \<Quicksort>(V)$. \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù}
\endalgo
-\s{Pozorování:}
-\itemize\ibull
-\:zastaví se
-\:vydá správný výsledek (dùkaz napø. indukcí podle $\vert X\vert$)
-\:pivot
- \itemize\istar
- \:pøi ideální volbì: $$ T(n) = 2T(n/2) + O(n) = O(n\log n) $$ (jako u mergesortu)
- \:pøi ¹patné volbì: $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2) $$
- \endlist
-\:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu
-\endlist
+\s{Rozbor:}
+V¹imnìme si, ¾e QS se urèitì zastaví a také ¾e vydá
+správný výsledek. To mù¾eme ovìøit napøíklad indukcí podle $\vert X\vert$.
- \s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$
-\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)$.}
+Podobnì jako u vybírání $k$-tého nejmen¹ího prvku v minulých pøedná¹kách
+i zde èasová slo¾itost závisí hlavnì na volbì pivota. Kdybychom za pivota
+zvolili medián, vy¹la by èasová slo¾itost stejnì jako u MergeSortu:
+ $$ T(n) = 2T(n/2) + O(n) = O(n\log n). $$
+Pokud naopak budeme volit pivota ne¹ikovnì, dostaneme:
+ $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2). $$
+V ideálním pøípadì bychom tedy chtìli za pivota zvolit medián, av¹ak jeho pøímým výpoètem
+bychom algoritmus pøíli¹ zpomalili.
+Pou¾ívá se proto mnoho zpùsobù, jak vybrat rychle pivota blízkého mediánu.
+Èasto pou¾ívanou metodou je náhodný výbìr, v praxi realizovaný nìjakým pseudonáhodným
+generátorem. Uká¾eme, ¾e v tomto pøípadì je QS v prùmìrném pøípadì rychlý:
-\s{Pozorování:}
+\s{Vìta:} QS s náhodnou volbou pivota má èasovou slo¾itost v prùmìru $\O(n\log n)$.
-\itemize\ibull
-\:Ka¾dá fáze rozdìlí vstup na disjunktní èásti + pivoty $X_1, \ldots, X_k$ ($k \geq 2$)
+\s{Poznámka:} Stejnì jako u výbìru $k$-tého nejmen¹ího prvku bychom také
+mohli ukázat, ¾e QS s pevnou volbou pivota spu¹tìný na náhodnou permutaci
+má tuté¾ èasovou slo¾itost. Detaily nicménì vynecháme.
-\:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$
+\noindent {\sl Dùkaz vìty:}
-\:$\sum_i \vert X_i \vert \leq \vert X \vert$
+Dùkaz provádíme rozdìlením algoritmu na fáze.
+Rekurzivní volání QSortu zle zobrazit jako¾to strom, pøièem¾ fází rozumíme cestu ve stromu volání,
+která sleduje vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián.
-\: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$)
+\figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize}
-\:v prùmìru poèítáme jednu fázi v èase $\O(n)$
+\figure{Faze.eps}{Fáze}{0.3\hsize}
-\:Proto $T(n) = \sum_i T (n_i) + \O(n)$, kde $n = \vert X \vert$, $n_i = \vert X_i \vert$.
+Ka¾dá fáze pøitom rozdìlí vstup na disjunktní èásti $X_1, \ldots, X_k$ ($k\ge 2$)
+a pivoty, kteøí je oddìlují.
+Oznaème si $n$ za velikost vstupu (poèet prvkù vstupní posloupnosti) a $n_i$ za velikost $i$-té èásti.
+Nahlédneme, ¾e platí $\sum_i n_i \leq n$.
+Velikost ka¾dé èásti je navíc nejvý¹e $3/4 \cdot n$ (na konci fáze to platí proto, ¾e jsme
+zvolili l¾imedián, pøedtím jsme v¾dy oddìlili men¹í z èástí, èili nejvý¹e $n/2$).
-\endlist
+Jedna iterace algoritmu trvá $\O(n)$ a jeliko¾ l¾imedián vybereme s pravdìpodobností alespoò $1/2$,
+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)$.
+Z toho dostaneme následující rekurenci pro prùmìrnou èasovou slo¾itost celého algoritmu:
+$${\bb E}T(n) = \sum_i {\bb E}T (n_i) + \O(n).$$
-\s{Komprimovaný strom}
+Tento typ rekurence jsme je¹tì nepotkali a Kuchaøková vìta\foot{MasterTheorem} na ni nezabere,
+ov¹em mù¾eme si pomoci jednoduchou úvahou. Pøedstavme si, ¾e v na¹em stromu
+rekurzivních volání zkomprimujeme ka¾dou fázi do jednoho vrcholu. Tím vznikne
+strom, který odpovídá algoritmu, jen¾ v jedné iteraci v prùmìrnì lineárním
+èase rozdìlí vstup na nìkolik èástí a rekurzivnì se na nì zavolá.
-Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost
-fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti
-velikosti~1).
+\figure{KomprimovanyStrom.eps}{Komprimovaný Strom}{0.3\hsize}
-Práce na jedné hladinì je $\O(n)$.
+\figure{Komprimace.eps}{Zpùsob vytvoøení komprimovaného stromu}{0.3\hsize}
-$\Downarrow$
+Nový strom má logaritmickou hloubku, proto¾e na ka¾dé dal¹í hladinì jsou
+délky posloupností nejvý¹e $3/4$ délek z pøedchozí hladiny. Navíc souèet
+délek pøes ka¾dou hladinu je maximálnì $n$. Proto na ka¾dé hladinì
+trávíme èas v prùmìru $\O(n)$ a v celém stromu tedy $\O(n\log n)$.
+\qed
-Celkem je v~prùmìru $\O(n \log n)$.
+\s{Pozorování:} Na¹e první verze QS spotøebuje lineární mno¾ství pamìti
+na pomocné pole a na zásobník. Na pøedná¹ce jsme ukazovali rùzná jeho
+praktická vylep¹ení, které staèí pomocná pamì» o velikosti $\O(\log n)$.
+Detaily viz webové stránky pøedná¹ky.
-\s{Vìta:}
-Ka¾dý tøídící algoritmus zalo¾ený na porovnávání
-(a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì
-$\Omega (n \log n)$ porovnání.
+Známe u¾ nìkolik tøídících algoritmù s èasovou slo¾itostí $\O(n\log n)$.
+Následující vìta ukazuje, ¾e efektivnìj¹í algoritmus v obecném pøípadì
+nese¾eneme.
-\bye
+\s{Vìta:}
+Ka¾dý tøídící algoritmus zalo¾ený na porovnávání a prohazování prvkù
+potøebuje na vstup délky $n$ v nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání.
\proof
- 1) {\tmsamp{BÚNO}} nejdøíve algoritmus porovnává a potom
- prohazuje
-
- {\small{ (algoritmus mù¾eme upravit tak aby
- prohazoval a¾ nakonci)}}
-
- 2) {\tmsamp{BÚNO}} hledáme vstupy, které jsou permutace na \{1 - n\}
-
- 3) Sestrojíme rozhodovací strom ne¹eho algoritmu
-
- \begin{tabular}{l}
- \
- \begin{tabular}{|l|}
- \hline
- $x_1 < x_2$\\
- \hline
- \end{tabular}
- \end{tabular}
-
- $\swarrow
- \searrow$
-
- \begin{tabular}{|l|}
- \hline
- $x_1 < x_3$\\
- \hline
- \end{tabular}
-
- $\swarrow \searrow$ \
- Ka¾dý algoritmus mù¾eme popsat podobným Stromem
-
- \begin{tabular}{|l|}
- \hline
- $x_2 < x_3$\\
- \hline
- \end{tabular}
-
- $\swarrow \searrow$
-
- {\tmstrong{$x_1 < x_2 < x_3$}} $\Leftarrow$ \
- {\tmstrong{Listy}} {\small{- algoritmus u¾ zde dotøídil a u¾ bude jen
- pøehazovat a pak zkonèí}}
-
-
-
- Jde vidìt ¾e $\tmmathbf{}$Existence dvou rùzných $\Pi_1 a \Pi_2 $,
-
- pøi kterých bychom zkonèili ve stejném listu vede ke Sporu
-
-
-
- pøitom {\tmstrong{\# listù $\geqslant$ n!}}
-
-
-
- {\tmstrong{Pozorování:}} Binární strom hloubku {\tmstrong{k}}
- má {\tmstrong{poèet listù $\leq 2^k$ }}
-
- \begin{tmparmod}{0pt}{2cm}{0pt}
- \begin{proof}
- {\small{}}Uva¾me binární strom hloubky k s maximálním
- poètem listù
-
- pak v¹echny listy le¾í na poslední hladinì
-
- víme ¾e na i-té hladinì je $2^i$ vrcholù
-
- $\tmmathbf{\Rightarrow}$ poèet listù je $2^k$
-
- \tmmathbf{$\Rightarrow$} v ka¾édém binárním stromu je
- maximálnì $2^k$ listù
- \end{proof}
- \end{tmparmod}
-
- {\tiny{pokraèování pùvodního dùkazu...}}
-
- Z toho co u¾ víme plyne ¾e $\Rightarrow$\begin{tabular}{l}
-
- \end{tabular}Hloubka stromu je $\geqslant$ log(n!)
-
- {\small{z Diskrétní matematiky víme ¾e: \
- $\tmmathbf{n^{n / 2} \leq n!} \leq (n / 2)^n$}}
-
- {\small{ Udìlá se to pomocí {\tmstrong{AG
- Nerovnosti}}}}
-
- tedy $\Rightarrow$ Hloubka stromu je $\geqslant \log (n^{n / 2}) = (n / 2)
- \log (n) \Longrightarrow \tmmathbf{\Omega (n \log n)}$
-
-
-\end{proof}
-
-\end{document}
+Bez újmy na obecnosti budeme nejdøíve pøedpokládat o algoritmu dvì vìci:
+Jednak to, ¾e algoritmus nejprve porovnává, a teprve potom prohazuje.\foot{Algoritmus
+mù¾eme upravit tak, aby si pamatoval aktuální permutaci prvkù a podle ní prohazoval a¾ na konci.}
+Také pøedpokládáme, ¾e vstup algoritmu je permutace na mno¾inì $\{1, \ldots, n\}$.
+
+Chování tohoto algoritmu popí¹eme rozhodovacím stromem. V rozhodovacím stromu vnitøní vrcholy
+urèují jednotlivá porovnání prvkù a listy odpovídají okam¾ikùm, kdy algoritmus pøestal porovnávat a zaèal prohazovat.
+
+\figure{RozhodovaciStrom.eps}{Rozhodovací Strom}{0.3\hsize}
+
+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ù.
+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.
+Listù stromu je tedy alespoò tolik, kolik je rùzných vstupù, tedy $n!$.
+
+{\narrower
+ \s{Lemmátko:} Binární strom hloubky $k$ má nejvý¹e $2^k$ listù.
+ \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s maximálním poètem
+ listù. V takovém stromu budou v¹echny listy urèitì le¾et na poslední hladinì
+ (kdyby nele¾ely, mù¾eme pod nìkterý list na vy¹¹í hladinì pøidat dal¹í dva vrcholy a získat
+ tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na $i$-té hladinì je nejvý¹e $2^i$
+ vrcholù, v¹ech listù je nejvý¹e $2^k$.
+ \qed
+}
+
+\>Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò $\log n!$.
+
+\>Zbytek je u¾ snadné cvièení z diskrétní matematiky:
+
+{\narrower
+ \s{Lemmátko:} $ n! \ge n^{n / 2}$.
+ \par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$,
+ co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$.
+ 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$.
+ Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$.
+ \qed
+}
+
+\>Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$,
+co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v nejhor¹ím pøípadì.
+\qed
\bye
projects / ads1.git / blobdiff