Nova verze Rozdel a panuj.

[ads1.git] / 8-rozdel / 8-rozdel.tex

\input ../lecnotes.tex

\prednaska{8}{Rozdìl a panuj}{}

Známá strategie {\sl Divide et Impera} (nìkdy pøekládáno spí¹e jako \uv {Roze¹tvi a panuj}) pochází z dob antického Øíma\foot{Aè se touto strategií øím¹tí panovníci øídili, není nalezen ¾ádný antický zdroj výroku; ten je pøipisován a¾ renesanènímu N. Machiavellimu.
}, kdy panovník zasel nesvár mezi místní kmeny (èím¾ je rozdìlil a roze¹tval) a následnì pøi¹el, urovnal napìtí, aby je mohl opìt ovládnout a panovat a aby byli v¹ichni spokojení.

Tato strategie ov¹em pøetvrává (aè tøeba v jiných oblastech) a pomáhá øe¹it ty problémy, které se dají rozdìlit na men¹í jednodu¹¹í podproblémky.

Jak tedy algoritmus typu {\it rozdìl a panuj} pracuje? Mìjme problém, který má tu vlastnost, ¾e kdy¾ jej rozdìlíme na nìjaké podproblémy, které mají stejný charakter, a ty vyøe¹íme, slo¾ením jejich øe¹ení mù¾eme získat øe¹ení pùvodního problému. Algoritmus tedy bude rekurzivnì volat sám sebe, ne¾ se dostane k~podproblému
nìjaké konstantní velikosti, který u¾ umí vyøe¹it triviálnì, a pak se zaène z~rekurze vracet a skládat jednotlivá dílèí øe¹ení.

\h{Pøíklad 1 -- MergeSort:}

Tento tøídící algoritmus pracuje na principu, ¾e vstup rozdìlíme na~dvì (skoro) stejnì velké èásti, které rekurzivním voláním setøídíme, a~nakonec výsledné dvì posloupnosti slijeme do~jedné. 

\s{Algoritmus:}

\algo
\algin posloupnost $x_1,\dots, x_n$.
\:Pokud $n \leq 1 \Rightarrow$ vrátíme vstup.
\:$y_1,\dots,y_{\lfloor n/2 \rfloor} \leftarrow$ \<MergeSort> $(x_1,\dots,x_{\lfloor n/2 \rfloor})$.
\:$z_1,\dots,z_{\lceil n/2 \rceil} \leftarrow$ \<MergeSort> $(x_{\lfloor n/2 \rfloor + 1},\dots,x_n)$.
\:Vrátíme Merge$(y_1,\dots,y_{\lfloor n/2 \rfloor}; z_1,\dots,z_{\lceil n/2 \rceil})$.
\endalgo

\noindent
Na slití dvou setøídìných posloupností do jedné pou¾íváme funkci Merge:

{\bo Merge$(y_1, \dots,y_a;z_1, \dots,z_b)$:}
\algo
\:$i \leftarrow 1, j \leftarrow 1, k \leftarrow 1$.
\:Dokud $k \leq a+b$:
\::Je-li $(j>b)$ nebo $(i \leq a) \& (y_i < z_j) \Rightarrow x_k \leftarrow y_i, k|++|, i|++|$.
\::Jinak $\Rightarrow x_k \leftarrow z_j, k|++|, j|++|$.
\:Vrátíme $x_1, \dots,x_n$.
\endalgo

\s{Pozorování:}
Merge trvá $\Theta (n)$, nebo» ka¾dou ze~slévaných posloupností projdeme právì jednou.

\s{Èasová slo¾itost MergeSortu:}

Rozdìlování a slévání nám trvá lineárnì dlouho, tak¾e pro èasovou slo¾itost MergeSortu platí tato rekurentní rovnice: $$T(n)= 2 \cdot T(n/2) + c \cdot n.$$ 
Pøitom $T(n)$ zde znaèí èas strávený na vstup délky $n$ a $c$ je nìjaká vhodná konstanta. Pro jednoduchost BÚNO pøedpokládejme, ¾e $n$ je mocnina dvojky. Zároveò si jednotky zvolme tak, ¾e bude platit $T(1)=1$. Mù¾eme si tedy rekurentní vztah rozepsat následovnì:

$$\eqalign{
T(n) &= 2 \cdot (2T(n/4) + c \cdot n/2) + c \cdot n = 4T(n/4) + 2cn = \cr
                 &= 4(2T(n/8) + c(n/4)) + 2cn = 8T(n/8) + 3cn = \dots\cr
                 &= 2^k T(n/2^k) + kcn.
}$$

Pokud zvolíme $k = \log_2{n}$, získáme:
$$T(n) = 2^{\log_2{n}} \cdot T(n/2^{\log_2{n}}) + \log_2{n} \cdot c \cdot n = n \cdot T(1) + c \cdot n \cdot \log_2{n} = \Theta(n \log{n}). $$

Ke stejnému výsledku mù¾eme ale dojít také úplnì jinou cestou. Pøedstavme si strom rekurzivních volání. Ka¾dý vrchol má dva syny (dìlíme vstup na~dvì èásti), v~nich¾ jsou vstupy polovièní velikosti. V~ka¾dém vrcholu trávíme èas lineární s~velikostí jeho vstupu, souèet velikostí vstupù pøes ka¾dou hladinu je~$n$ a hloubka stromu musí být $\Theta(\log n)$. Vyjde nám tedy, ¾e $T(n)=\Theta(n\log n)$.\foot{Po pozornìj¹ím zamy¹lení si ètenáø mù¾e uvìdomit, ¾e se jedná vlastnì pouze o~jiný pohled na~stejný dùkaz jako rozepisování rekurentního vzorce.}

\s{Pamì»ová slo¾itost MergeSortu:}

$M(n) = d \cdot n + M(n/2) = d \cdot n + d \cdot n/2 + d \cdot n/4 + \dots \leq 2d n = \Theta(n).$

Toto platí pro nìjakou vhodnou konstantu $d$. Tento vztah mù¾eme opìt nahlédnout napøíklad ze stromu rekurzivních volání.

\s{Závìr:}
Mergesort bì¾í v èase $\Theta(n \log{n})$ a pamìti $\Theta(n)$. Lineární pamì»ová slo¾itost není výhodná, ale na druhou stranu se tento algoritmus velmi hodí napøíklad na tøídìní lineárních spojových seznamù.

\h{Pøiklad 2 -- Násobení èísel:} 
Pokud násobíme dvì èísla $X$ a $Y$ (obì délky $n$; pokud bylo jedno krat¹í, tak ho doplníme nulami zleva tak, aby byla obì èísla stejnì dlouhá) zpùsobem, který nás uèili na základní ¹kole, výsledný algoritmus má èasovou slo¾itost $\Theta(n^2)$. Proto¾e se jedná o~dost èastou operaci, zamysleme se, zda by ne¹la zrychlit. Nasmìrujme na¹e úvahy na postup {\it rozdìl a panuj}. Rozdìlíme ka¾dého èinitele na dvì stejnì dlouhé èásti. Pro jednoduchost pøedpokládejme, ¾e toto roz¹tìpení èinitele probìhne v¾dy bez zbytku:
$$
X=A \cdot 10^{{n}/2}+B, \qquad Y=C \cdot10^{{n}/{2}}+D.
$$
Zde $A, B, C, D$ jsou u¾ jen $(n/2)$-ciferná èísla. Pùvodní souèin získáme jako:
$$
XY=(A\cdot 10^{{n}/{2}}+B) (C\cdot 10^{{n}/{2}}+D)=AC \cdot 10^{n}+(AD+BC)\cdot 10^{{n}/{2}}+BD.
$$
Nyní, jak vidíme, staèí spoèítat souèin ètyø $(n/2)$-ciferných èísel a pak výsledky spolu seèíst. Uva¾me,
jakou bude mít tento algoritmus èasovou slo¾itost:
$$T(n) = 4T(n/2) + cn.$$
Toto platí pro nìjakou vhodnou konstantu $c$ (výraz $cn$ je re¾ie na sèítání).  Jednotky si zvolme tak, aby platilo: $$T(1)=1.$$
Jak takovou rekurenci vyøe¹íme? Máme opìt dvì mo¾nosti:

\>{\sl 1. zpùsob: Øe¹ení rozepsáním rekurentního vztahu:}
$$\eqalign{
T(n)&= 4T(n/2)+cn = \cr
    &= 4\cdot (4T(n/4)+cn/2)+cn = 4^2T(n/4)+2cn+cn = 4^2T(n/4)+3cn = \cr
    &= 4^2\cdot (2T(n/8)+cn/4)+3cn = 4^3T(n/8)+4cn+3cn = 4^3T(n/8)+7cn = \cr
    &\dots\cr
}$$
Odtud snadno vypozorujeme, ¾e jednotlivé vztahy se vyvíjejí podle vzorce
$T(n)=4^kT(n/2^k) + (2^k-1)cn.$ Pro $k=\lceil\log_2 n\rceil$ je ov¹em
$2^k\le 1$, tak¾e $T(n/2^k)=\Theta(1)$ a dostaneme (horní celou èást zanedbáme,
ta ovlivní jen konstanty):
$$
T(n) = 4^{\log_2 n}\Theta(1) + (2^{\log_2 n}-1)cn = n^2\Theta(1) + (n-1)cn = \Theta(n^2).
$$

\>{\sl 2. zpùsob: Úvaha o~stromu:} Nakreslíme si strom rekurzivních volání
na¹eho algoritmu:
\fig{figure.eps}{4in}
Na~$i$-té hladinì stromu le¾í $4^i$ vrcholù, v~nich jsou vstupy velikosti
$n/2^i$, tak¾e na~celé hladinì trávíme èas celkem $\Theta(4^i\cdot n/2^i)
= \Theta(2^in)$. Velikosti vstupù klesají exponenciálnì, tak¾e celý strom
je hluboký $k=\log_2 n$ (opìt si dovolíme zapomenout na~horní celou èást).
Celkem tedy spotøebujeme èas $\sum_{i=0}^{k}\Theta(2^in) = \Theta(n\cdot\sum_{i=0}^k 2^i) = \Theta(n^2)$.

Oba zpùsoby analýzy se tedy shodují na tom, ¾e ná¹ algoritmus má kvadratickou èasovou
slo¾itost a ¾e jsme si oproti klasickému algoritmu nikterak nepomohli.
Podívejme se je¹tì jednou na~to, jak se ná¹ algoritmus vìtví:
$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad &\hfil#\hfil\cr
hloubka & poèet úloh & velikost podúlohy\cr
\noalign{\smallskip\hrule\medskip}
0 & $4^{0}$ & ${n}/{2^{0}}$\cr
1 & $4^{1}$ & ${n}/{2^{1}}$\cr
2 & $4^{2}$ & ${n}/{2^{2}}$\cr
3 & $4^{3}$ & ${n}/{2^{3}}$\cr
\vdots & \vdots & \vdots\cr
$k$ & $4^{k}$ & ${n}/{2^{k}}$\cr}}$$
Naskýtá se otázka, jestli bychom nemohli èasovou slo¾itost zlep¹it. Toho bychom
mohli dosáhnout napøíklad zlep¹ením èlenu $cn$ v~na¹í rekurenci, èili zefektivnìním
spojování podúloh. To ov¹em není pøíli¹ nadìjné (pokud ètenáø nevìøí, mù¾e si to dokázat),
tak¾e místo toho vyu¾ijeme druhou ¹anci a~to omezení vìtvení ze~ètyø vìtví na~tøi.
Pøipomeòme si, ¾e potøebujeme spoèítat:
$$
XY=AC\cdot 10^{n}+(AD+BC)\cdot 10^{n/2}+BD.
$$
Pøitom ale nepotøebujeme znát souèiny $AD$ ani $BC$ samostatnì, nám staèí zjistit hodnotu celého výrazu $AD+BC$. Kdy¾ budeme znát hodnotu výrazù: $AC$, $BD$ a $(A + B)(C + D)$ (k tomu nám staèí 3 násobení a 2 sèítání), tak mù¾eme výraz $AD + BC$ získat následovnì:
$$(A + B)(C + D) - AC - BD = AC + AD + BC + BD - AC - BD = AD + BC$$
Nyní nám ji¾ staèí jen tøi násobení, ale potøebujeme dvì sèítání a jedno odèítání navíc. Nicménì tato komplikace je zanedbatelná oproti práci u¹etøené men¹ím vìtvením. (Nová dvì sèítání a jedno odèítání se v èasové slo¾itosti schová do $cn$.) Podívejme se opìt na~tabulku:
$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad &\hfil#\hfil\cr
hloubka & poèet úloh & velikost podúlohy\cr
\noalign{\smallskip\hrule\medskip}
0 & $3^{0}$ & ${n}/{2^{0}}$\cr
1 & $3^{1}$ & ${n}/{2^{1}}$\cr
2& $3^{2}$ & ${n}/{2^{2}}$\cr
3 & $3^{3}$ & ${n}/{2^{3}}$\cr
\vdots & \vdots & \vdots\cr
$k$ & $3^{k}$ & ${n}/{2^{k}}$\cr}}$$
Ná¹ rekurentní vztah po zbavení se jednoho násobení vypadá následovnì:
$$T(n) = 3T(n/2)+ cn.$$

Opìt uva¾me, kolik práce spotøebujeme v~souètu pøes v¹echny hladiny (hloubka stromu
$k$ je opìt $\lceil\log_2 n\rceil$ a horní celou èást zanedbáme):
$$\sum_{i=0}^{k}3^{i}\cdot {{n}\over{2^{i}}}=\sum_{i=0}^{k} \left( {{3}\over{2}} \right) ^{i}\cdot n=n\cdot \sum_{i=0}^{k} \left( {{3}\over{2}} \right) ^{i}=n\cdot {{ \left( {{3}\over{2}} \right) ^{k+1}-1}\over{{{3}\over{2}}-1}}=
$$
$$
=n\cdot {{ \left( {3}\over{2} \right) ^{k+1}-1}\over{{{1}\over{2}}}}=2\cdot n\cdot  \left[ \left( {{3}\over{2}} \right) ^{k+1}-1 \right] = \Theta \left( n\cdot  \left( {{3}\over{2}} \right) ^{\log_2{n}} \right) =
$$
$$
=\Theta \left( n\cdot {{3^{\log_2{n}}}\over{2^{\log_2{n}}}} \right)=\Theta \left( n\cdot {{3^{\log_2{n}}}\over{n}} \right)=\Theta \left( 3^{\log_2{n}} \right)=\Theta \left( (2^{\log_2{3}})^{\log_2{n}} \right)=
$$
$$
=\Theta \left( 2^{(\log_2{n}) \cdot \log_2{3}} \right)=\Theta \left( (2^{\log_2{n}})^{\log_2{3}} \right)=\Theta \left( n^{\log_2{3}} \right) =\Theta \left( n^{1.585} \right).
$$
Upravený algoritmus má u¾ tedy lep¹í èasovou slo¾itost, konkrétnì $\Theta(n^{1.585})$.
V~praxi bychom samozøejmì èinitele ne¹tìpili a¾ na jednociferná èísla,
ale zastavili se u~nìjaké dostateènì malé délky (øeknìme 50~cifer) a tam
pøepnuli na~kvadratický algoritmus, který má men¹í re¾ii.

(Mimochodem, asymptoticky tato slo¾itost není nejlep¹í známá, pro násobení èísel existují efektívnìj¹í algoritmy, které
dosahují èasové slo¾itosti $\Theta(n \log{n})$, ale jednak mají vysoké multiplikativní konstanty a druhak jsou v~nich u¾ potøeba trochu
pokroèilej¹í techniky, jako je diskrétní Fourierova transformace, tak¾e si je necháme na~pøí¹tí semestr.)

\h{Kuchaøková vìta {\it (Master Theorem)}}

Metody øe¹ení rekurentních rovnic z pøedchozích dvou pøíkladù
by jistì fungovaly i na~jiné algoritmy, ale proè poka¾dé zbyteènì upravovat tolik  výrazù? Radìji si doká¾eme obecnou vìtu, která pùjde pou¾ít na~vìt¹inu
takovýchto rekurencí. Øíká se jí {\it Master Theorem} nebo také (vzhledem k~tomu,
jak se pou¾ívá) {\it Kuchaøková vìta}.

\s{Vìta:} \>{\sl (Master Theorem)} 

Pøedpokládejme, ¾e $T(1)=\Theta(1)$ a $T(n)=a\cdot T(\lceil {{n}\over{b}} \rceil)+\Theta(n^d)$, kde $a \geq 1$, $b>1$, $d \geq 0$ a $a,b \in \bb N$. Potom $T(n)$ je:

\smallskip

\halign{#&#&#\cr
\indent & $\Theta(n^d)$ & kdy¾ $a<b^d$,\cr
& $\Theta(n^d\cdot \log{n})$ & kdy¾ $a=b^d$,\cr
& $\Theta(n^{\log_b{a}})$ & kdy¾ $a>b^d$.\cr}

\proof Pøedpokládejme, ¾e $n=b^k, k \in \bb{N}$, aby platilo $\lceil
{{n}\over{b}} \rceil = {{n}\over{b}}$. Pou¾ijeme opìt \uv{dùkaz stromem}.
Strom rekurzivních volání se v¾dy vìtví na stejný poèet vìtví, konkrétnì~$a$,
a~velikosti vstupù klesají $b$-krát. Podívejme se na~tabulku:
$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad & \hfil#\hfil \quad & \hfil#\hfil \cr
poèet vrcholù na hladinì & velikost vstupu & èas ve vrcholu & èas na hladinì \cr
\noalign{\medskip\hrule\medskip}
$1$ & $n$ & $\Theta(n^d)$ & $\Theta(n^d)$\cr
$a$ & $n/{b^1}$ & $\Theta((n/b^1)^d)$ & ${\Theta(a^1 \cdot ({n/{b^1}})^d)}$\cr
$a^2$ & $n/{b^2}$ & $\Theta((n/b^2)^d)$ & ${\Theta(a^2 \cdot ({n/{b^2}})^d)}$\cr
$a^3$ & $n/{b^3}$ & $\Theta((n/b^3)^d)$ & ${\Theta(a^3 \cdot ({n/{b^3}})^d)}$\cr
\vdots & \vdots  & \vdots & \vdots\cr
$a^k$ & $n/{b^k}$  & $\Theta((n/b^k)^d)$ & ${\Theta(a^k \cdot ({n/{b^k}})^d)}$\cr}}$$

\noindent
Celkový èas potøebný na vyøe¹ení v¹ech dílèích podúloh je následovný:
$$
T(n)=\sum_{i=0}^k\Theta \left( a^i \left( {n\over{b^i}} \right) ^d \right)=\sum_{i=0}^k\Theta \left( n^d \left( {a\over{b^d}} \right) ^i \right)=\Theta \left( n^d \cdot \sum_{i=0}^k \left( {a\over{b^d}} \right) ^i \right).
$$
V¹imnìme si sumy $\sum_{i=0}^k \left( {a\over{b^d}} \right) ^i$. Jedná se vlastnì o geometrickou øadu s kvocientem $q={a\over{b^d}}$. Rozli¹me následující pøípady:

\>{\I 1.} $q<1$: Práce na~jednotlivých hladinách exponenciálnì ubývá a souèet øady (i~kdyby byla nekoneèná) se dá omezit nìjakou konstantou, tedy $T(n)=\Theta(n^d)$.

\>{\I 2.} $q=1$: Práce na~jednotlivých hladinách je stejnì, to znamená, ¾e suma je právì $1 + \log_b n$, a tedy $T(n) = \Theta(n^d \cdot \log{n})$.

\>{\I 3.} $q>1$: Práce na~jednotlivých hladinách pøibývá, tak¾e musíme geometrickou øadu seèíst poctivì. Víme, ¾e souèet geometrické øady od $0$ do $k$ s kvocientem $q$ a prvním èlenem $1$ je: ${q^{k+1} - 1}\over{q - 1}$, co¾ pøibli¾ne odpovídá $q^k$. Pak tedy platí: $$T(n) = \Theta(n^d \cdot q^{\log_b{n}}).$$ Tento výraz vypadá ponìkud o¹klivì, ale je¹tì ho trochu (alespoò kosmeticky) upravíme:
$$
\Theta\left(n^d \cdot q^{\log_b{n}}\right)=\Theta\left({ a^{\log_b{n}} \cdot n^d \over (b^d)^{\log_b{n}}}\right)=\Theta\left({\left(b^{\log_b{a}}\right)^{\log_b{n}} \cdot n^d \over{\left(b^d\right)^{\log_b{n}}}}\right)=
$$
$$
=\Theta\left({\left(b^{\log_b{n}}\right)^{\log_b{a}} \cdot n^d \over{\left(b^{\log_b{n}}\right)^d}}\right)
=\Theta\left({n^{\log_b{a}} \cdot n^d \over{n^d}}\right)
=\Theta\left(n^{\log_b{a}}\right).
$$
Tyto tøi pøípady pøesnì odpovídají rozdìlení pøípadù v~tvrzení vìty.

\noindent
Vra»me se nyní k~mo¾nosti, kdy $n$ není mocnina~$b$. Pro obecné $n \geq 1$ zvolme: 

\itemize\ibull
\:$n^+ \dots$ nejbli¾¹í vy¹¹í mocnina $b$
\:$n^-$ \dots nejbli¾¹í ni¾¹í mocnina $b$
\endlist

Platí tedy, ¾e $T(n^-) \le T(n) \le T(n^+)$. Ale $T(n^-) = \Theta((n^-)^c) = \Theta(n^c)$ a $T(n^+) = \Theta((n^+)^c) = \Theta(n^c)$. Pak tedy i $T(n) = \Theta(n^c)$. Vìta tedy platí i v~pøípadì, ¾e $n$ není mocnina~$b$.
\qed

\s{Pøíklad:}
Porovnejme si nìkteré známé algoritmy a jejich èasovou slo¾itost pomocí \>{\sl Master Theoremu}:
$$\vbox{\halign{# \quad  \quad & # \quad  \quad & # \quad  \quad & # \quad  \quad & #\cr
algoritmus & $a$ & $b$ & $d$ & èasová slo¾itost\cr
\noalign{\smallskip\hrule\medskip}
Mergesort & 2 & 2 & 1 & $\Theta({n \cdot \log{n}})$\cr
Násobení I. & 4 & 2 & 1 & $\Theta(n^2)$\cr
Násobení II. & 3 & 2 & 1 & $\Theta(n^{\log_2{3}})$\cr
Binární vyhledávání & 1 & 2 & 0 & $\Theta(\log{n})$\cr}}$$


\h{Hledání $k$-tého nejmen¹ího prvku (mediánu)}

V tomto oddílu se budeme zabývat tím, jak co nejrychleji najít v jakékoli posloupnosti $n$ èísel $k$-tý nejmen¹í prvek, popøípadì medián. Pro ty, kdo medián neznají, tu máme definici:

\s{Definice:}
{\I Medián} posloupnosti $a_1, a_2,\ldots , a_n$ je takové $a_i$, kde nejvý¹e $n/2$ prvkù je men¹ích ne¾ $a_i$ a nejvý¹e $n/2$ prvkù je vìt¹ích ne¾ $a_i$. Platí tedy, ¾e medián je buï $\lfloor n/2\rfloor$-tý, nebo $\lceil n/2\rceil$-tý nejmen¹í prvek posloupnosti.

Nejjednodu¹¹ím øe¹ením by urèitì bylo celou posloupnost nejdøíve setøídit a pak u¾ jednodu¹e vybrat po¾adovaný prvek. To bychom dokázali v celkem slu¹ném èase $\Theta(n\log n)$, ale u¾ teï mù¾eme prozradit, ¾e to jde v èase $\Theta(n)$. Jak?

Pou¾ijme metodu {\it rozdìl a panuj}. Nìjakým zpùsobem si zvolíme jeden prvek posloupnosti a nazveme ho {\it pivot}. Poté rozdìlíme zadanou posloupnost na~tøi disjunktní mno¾iny. Do první dáme v¹echny prvky men¹í ne¾ pivot, do druhé stejné jako pivot a do tøetí vìt¹í ne¾ pivot. Tímto máme zaji¹tìno, ¾e prvky z první mno¾iny jsou urèitì men¹í ne¾ prvky z druhé a ty ne¾ prvky z tøetí.
O tom, jak jsou prvky uspoøádány uvnitø tìchto mno¾in, ale nic nevíme.

V posledním kroku na¹eho algoritmu se pak rozhodneme, na kterou mno¾inu svùj algoritmus rekurzivnì zavoláme. Pokud je $k$ men¹í ne¾ velikost první mno¾iny, pokraèujeme v první mno¾inì, pokud je $k$ men¹í ne¾ souèet velikostí první a druhé mno¾iny, pak hledaným prvkem je právì vybraný pivot a algoritmus skonèí, a nakonec pokud ani jedna podmínka splnìna nebyla, pustíme se do hledání ve tøetí mno¾inì, ov¹em u¾ nehledáme $k$-tý nejmen¹í prvek, ale $l$-tý, kde $l$ se rovná $k$ minus velikost prvních dvou mno¾in. Pro vìt¹í názornost zapí¹eme tento algoritmus formálnìji:

\algo
{\bo Select($k,X$):} (Hledání $k$-tého nejmen¹ího prvku v mno¾ine $X$)
\:Jestli¾e $\vert X\vert \le 1$, vyøe¹íme triviálnì.
\:Zvolíme pivota $p \in X$.
\:Rozdìlíme mno¾inu X na tøi podmno¾iny: $L = \{x \in X; x < p\},$ $ S = \{x \in X; x = p\}, P = \{x \in X; x > p\}$.
\:Jestli¾e $k \le \vert L\vert$, vrátíme výsledek funkce \<Select>($k$, $L$).
\:Jestli¾e $ \vert L\vert < k \le \vert L\vert + \vert S\vert$, vrátíme pivota $p$.
\:Jestli¾e $ \vert L\vert + \vert S\vert < k$, vrátíme výsledek funkce \<Select>($k - \vert L\vert - \vert S\vert, P$).
\endalgo
Na první pohled je vidìt, ¾e se algoritmus zastaví (vstup se v¾dy zmen¹í alespoò o 1) a ¾e vydá v¾dy správný výsledek. Jak je to ov¹em s èasovou slo¾itostí? Rozdìlení do mno¾in a podmínky v druhém a tøetím kroku mají lineární slo¾itost, èemu¾ se nevyhneme. Pøi ne¹»astné volbì pivota se nám mù¾e stát, ¾e poèet rekurentních volání mù¾e být a¾ $n$, tedy celková slo¾itost v nejhor¹ím pøípadì je $\Theta(n^2)$, èím¾ jsme si oproti prostému setøídìní je¹tì pohor¹ili. Co s tím? Jak je vidìt, velmi dùle¾itá je volba pivota. Tu mù¾eme provést nìkolika zpùsoby:

a) Pivot by se v setøídìné posloupnosti vyskytoval uprostøed, vstup by se tedy stále pùlil. Èasovou slo¾itost vypoèteme z rekurentního zápisu:
$$ T(n) = T\left({n \over 2}\right) + \Theta(n) = \Theta\left(n + {n \over 2} + {n \over 4} + \dots\right) = \Theta(n). $$
To by bylo sice skvìlé, ale nalezení takového pivota je vlastnì vyøe¹ení úlohy hledání mediánu, o co¾ se sna¾íme. Tedy jsme si vùbec nepomohli.

b) Pivot by se v setøídìné posloupnosti náchazel v prostøedních dvou ètvrtinách (nazvìme tento prvek \uv{l¾imedián}). Tím bychom v ka¾dém kroku urèitì odstranili mno¾inu velikosti alespoò ètvrtiny vstupu. Èasová slo¾itost tohoto øe¹ení by byla:

$$ T(n) = T\left({3 \over 4}n\right) + \Theta(n) = \Theta\left(n + {3 \over 4}n + {9 \over 16}n + \dots\right) = \Theta(n). $$

Tímto bychom tedy také dosáhli lineární èasové slo¾itosti. Ale jak vybrat pivota tak, aby se nacházel v prostøedních dvou ètvrtinách a aby nám nám to nepokazilo lineární slo¾itost?

Zkusme vybrat pivota náhodnì. Pravdìpodobnost, ¾e vytáhneme zrovna l¾imedián je alespoò $1/2$. (Pokud by se prvky nemohly opakovat a byl jich sudý poèet, byla by to pøesnì $1/2$.) Tuto pravdìpodobnost si oznaème $p$. 

\s{Volba l¾imediánu}
\algo
\:Vybereme rovnomìrnì náhodnì pivota z mno¾iny $X$.
\:Otestujeme, zda je pivot l¾imedián.
\:Pokud není $\Rightarrow$ pokraèuj znovu od zaèátku, jinak konec.
\endalgo

Pivota vybíráme rovnomìrnì náhodnì, tedy ka¾dý prvek posloupnosti má stejnou pravdìpodobnost, ¾e bude vybrán. 

Oznaème si $T$ náhodnou velièinu znaèící dobu bìhu algoritmu. Potom støední hodnota této náhodné velièiny ${\bb E}[T] = \Theta(n) \cdot {\bb E}$[{\I poèet~prùchodù~cyklem}].

Teï si doka¾me, ¾e budeme-li náhodnì vybírat pivota tak dlouho, a¾ se strefíme do l¾imediánu, tak \uv{v prùmìru} budeme muset tahat jen $1/p$-krát.

\s{Lemma: } {\I (O d¾bánu a vodì)}
Èekání na náhodnou událost, která nastává s pravdìpodobností $p$, trvá v prùmìru $1/p$.

\proof
Oznaème $N$ poèet pokusù. Potom støední hodnota poètu pokusù je:
$$\eqalign{
                {\bb E}[N] & = p \cdot 1 +  (1-p) \cdot (1 + {\bb E}[N])\cr
                {\bb E}[N] & = p + 1 +  {\bb E}[N] - p -  p \cdot {\bb E}[N]\cr
    {\bb E}[N] \cdot (1 - 1 + p) & = 1\cr
    {\bb E}[N] & = 1/p\cr
}$$
S pravdìpodobností $p$ událost nastane a s odvrácenou pravdìpodobností ($1-p$) jsme jeden pokus promarnili a musíme celý proces opakovat. Jednoduchými úpravami nám vyjde, ¾e støední hodnota poètu pokusù je $1/p$.

\noindent
\uv{V prùmìru se tedy chodí $1/p$-krát se d¾bánem pro vodu, ne¾ se ucho utrhne...}
\qed

Z lemmatu tedy plyne, ¾e v na¹em pøípadì ${\bb E}$[{\I poèet prùchodù cyklem}]$ \le 2 $. V prùmìru tedy na druhý pokus vytáhneme l¾imedián. Ten pak pou¾ijeme jako pivot. Tímto tudí¾ dosáhneme prùmìrné èasové slo¾itosti $\Theta(n)$.

\s{Vìta: } Pravdìpodobnostním algoritmem lze najít $k$-tý nejmen¹í prvek z $n$ prvkù v prùmìrném èase $\Theta(n)$.

K volbì l¾imediánu jsme volili v¾dy náhodného pivota, jednalo se tedy o randomizovaný algoritmus. Stejný výsledek nám ale vyjde i pøi deterministickém algoritmu, kdy budeme volit pivota v¾dy stejnì (napø. na první pozici ve vstupní posloupnosti), ale budeme mít nìjak zaruèeno, ¾e vstupy budou dostateènì náhodné. U randomizovaného algoritmu se jednalo o prùmìr pøes náhodná èísla, u deterministického algoritmu o prùmìr pøes náhodné vstupy.

U¾ tedy víme, ¾e kdy¾ budeme volit pivota hodnì ¹patnì, tak se mù¾eme dostat a¾ na èasovou slo¾itost $\Theta(n^2)$. Kdy¾ budeme volit o nìco lépe, tak se mù¾eme dosáhnout prùmìrné èasové slo¾itosti $\Theta(n)$. Existuje ale i algoritmus, který pracuje v¾dy (nejen v prùmìrném pøípadì) v èase $\Theta(n)$. Podívejme se, jak bude vypadat\dots

\s{Volba pivota:}
\algo
\:Rozdìlíme vstup na pìtice \dots $\Theta(n)$
\:Spoèteme medián ka¾dé pìtice \dots $\Theta(n)$
\:Spoèteme medián mediánù pìtic tak, ¾e rekurzivnì zavoláme tentý¾ algoritmus \<Select>($n / 10$, {mediány pìtic}) a to je pivot.
\endalgo

Takováto volba pivota nám zaruèí, ¾e jím bude medián - tedy nejlep¹í mo¾ný pivot. Pro úplnost se podívejme, jak bude vypadat celý algoritmus na hledání $k$-tého nejmen¹ího prvku posloupnosti za pou¾ití na¹í nové volby pivota:

\s{Deterministický lineární algoritmus na výbìr mediánu lineárnì}
\algo
\algin $X = x_1 \dots x_n$, $k$ ($1 \le k \le n$)
\:Pokud $n \le 5 \Rightarrow$ hrubá síla
\:Vstup rozdìlíme na pìtice $P_1 \dots P_{\lceil n/5 \rceil}$
\:$\forall i: m_i \leftarrow$ medián($P_i$)
\:$p \leftarrow$ Select($m_1 \dots m{\lceil n/5 \rceil}, \lceil n/10 \rceil$)
\:Rozdìlíme X na L,S,P
\:Rekurzivnì se zavoláme na jednu z L,S,P (tu, ve které se má vyskytovat hledaný prvek)
\endalgo

Ná¹ deterministický algoritmus tedy roz¹iøuje pùvodní algoritmus tak, ¾e v¾dy, kdy¾ je potøeba zvolit pivota z posloupnosti X, tak si posloupnost rozdìlí na pìtice a v ka¾dé spoète medián. Následnì potøebuje medián z tìchto mediánù, co¾ bude výsledný pivot - medián v pùvodní posloupnosti. Ten získá tak, ¾e se znovu zavolá na \<Select> s parametry posloupnost mediánù a èíslo $\lceil n/10 \rceil$, nebo» potøebuje právì prostøední prvek této poslounosti, která má délku $\lceil n/5 \rceil$. Kdy¾ máme koneènì výhodného pivota (medián) nalezeného, tak mù¾eme pokraèovat, ¾e si posloupnost opìt rozdìlíme na tøi hromádky - prvky men¹í (L), stejné (S) a vìt¹í (P) ne¾ pivot. Následnì jen vybereme hromádku, která odpovídá umístìní $k$-tého nejmen¹ího prvku, a na tu se rekurzivnì zavoláme.

Abychom dokázali, ¾e tento algoritmus bude mít opravdu lineární èasovou slo¾itost, musíme si nejdøíve dokázat následující lemma:

\s{Lemma:} V ka¾dém kroku vypadne alespoò ${3/10}\cdot n$ prvkù.

\proof 
V dùkazu budeme trochu ètenáøe ¹idit tím, ¾e budeme pøedpokládat celoèíselné výsledky. Ètenáø si mù¾e jako cvièení dokázat, ¾e kdyby výsledky nevycházely celoèíselnì, tak to nevadí.

Pøedstavme si vybrané pìtice seøazené podle velikosti od nejvìt¹ího prvku a zakresleme je do sloupcù. Jejich mediány tedy vyplòují prostøední øadu. Tyto pìtice pak seøaïme podle velikosti jejich mediánù (nejmen¹í vlevo)\foot{Algoritmus ov¹em nikde takto pìtice neøadí! Jen nám to pomù¾e v úvaze o správnosti.}. Hledaný pivot se tedy nachází (pokud pøedpokládáme pro jednoduchost lichý poèet pìtic) pøesnì uprostøed. O prvcích nad pivotem a napravo od nìj mù¾eme urèitì øíct, ¾e jsou vìt¹í nebo rovny pivotu, prvky pod ním a nalevo od nìj jsou zase urèitì men¹í nebo rovny pivotu.

Podle konstrukce algoritmu tedy zaruèenì vypadne jedna nebo druhá skupina prvkù. Obì tyto skupiny pøitom obsahují, jak je vidìt z obrázku, alespoò $3/10 \cdot n$ prvkù.
\qed

\figure{petice.eps}{Pìtice}{125mm}

Nyní u¾ se tedy mù¾eme pustit do výpoètu èasové slo¾itosti. V ka¾dém kroku funkce zavolá sama sebe nejdøíve na vstup velikosti ${n \over 5}$ a poté na vstup velikosti nejvý¹e ${7 \over 10}n$. Ostatní operace zùstávají lineární. Èasovou slo¾itost v nejhor¹ím pøípadì tedy mù¾eme zapsat rekurentním vzorcem:

$$ T(n) = \Theta(n) + T\left({n \over 5}\right) + T\left({7 \over 10}n\right). $$

Tento rekurentní vzorec ale zatím neumíme obecnì øe¹it. Mohli bychom ho postupnì rozepsat, ale trvalo by dlouho, ne¾ bychom z toho nìco vykoukali. Lep¹í bude rovnou dokázat, ¾e tento rekurentní vzorec odpovídá lineární slo¾itosti, zkusíme tedy dosadit $T(n) = cn$:

$$ cn = n + {1 \over 5}cn + {7 \over 10}cn \quad\Longleftrightarrow\quad c = 10. $$

Tímto jsme tedy dokázali, ¾e èasová slo¾itost tohoto algoritmu v nejhor¹ím pøípadì je $\Theta(n)$.
Jeliko¾ to rychleji urèitì není mo¾né, mù¾eme na závìr této kapitoly zformulovat tuto vìtu:

\s{Vìta:} Hledání k-tého nejmen¹ího prvku v posloupnosti délky $n$ má èasovou slo¾itost v nejhor¹ím pøípadì $\Theta(n)$. \qed

\s{K zamy¹lení:} Proè jsme zvolili zrovna pìtice? Jak by to dopadlo pro trojice? A jak pro sedmice? Fungoval by takový algoritmus? Byl by také lineární?

\h{Quicksort}

Ji¾ jsme se seznámili s tøídícím algoritmem {\it Mergesort}. Podívejme se teï na algoritmus, který je také zalo¾en na metodì {\it Rozdìl a panuj}, ale chová se v podstatì opaènì. Namísto slévání men¹ích setøídìných posloupností posloupnost v¾dy rozdìlí na dvì pokud mo¾no podobnì velké èásti $L$ a $P$, kdy v $L$ jsou èísla men¹í ne¾ nìjaký pivot a v $P$ èísla vìt¹í. Pivot tvoøí samostatnou èást $S$. Obì èásti $L$ i $P$ rekurzivnì setøídí a následnì vrátí posloupnost, kde budou setøídìné prvky z $L$, pak pivot z $S$ a poté setøídìné prvky z $P$. Vyu¾ívá tedy podobnou my¹lenku jako hledání $k$-tého nejmen¹ího prvku.

\s{Algoritmus:}
{\bo QS$(x = x_1, \dots,x_n)$:}
\algo
\:Pokud $n \leq 1 \Rightarrow$ vrátíme $x$.
\:Vybereme pivota.
\:Rozdìlíme posloupnost na podposloupnosti $L,S,P$.
\:$L \leftarrow$ \<QS($L$)>, $P \leftarrow$ \<QS($P$)>
\:Vrátíme $L + S + P$.
\endalgo

\s{Pozorování:}

Kdy¾ bude pivot v¾dy medián: $T(n) = \Theta(n) + 2T(n/2) \Rightarrow T(n) = \Theta(n \cdot log{n})$

Kdy¾ bude pivot v¾dy minimum: $T(n) = \Theta(n) + T(n-1) \Rightarrow T(n) = \Theta(n^2)$

\s{Poznámka:} Hledání mediánu lineárnì je sice hezké a asymptoticky lineární, ale má tak o¹klivé multiplikativní kosntanty, ¾e se v praxi nepou¾ívá. Doka¾me si tedy, ¾e Quicksort s náhodnou volbou pivota má prùmìrnou èasovou slo¾itost také $\Theta(n\cdot log{n})$.

\s{Vìta:} Quicksort s náhodnou volbou pivota provede ve støední hodnotì $\Theta(n\cdot log{n})$ porovnání.

\s{Dùsledek:} Quicksort má prùmìrnou èasovou slo¾iotost  $\Theta(n\cdot log{n})$.

\proof
Nech» $C$ znaèí poèet porovnání, $y_1, \dots, y_n$ je vstup v setøídìném poøadí a $C_{ij}$ znaèí poèet porovnání prvkù $y_i$ s $y_j$ pro $1 \leq i \leq j \leq n$. Uvìdomme si, ¾e dva prvky porovnává algoritmus nejvý¹e jednou, a to pouze tehdy, kdy¾ je jeden z nich pivot. Proto $C_{ij}$ nabývá hodnot $0$ nebo $1$. $C_{ij}$ je tedy indikátor jevu, ¾e byly prvky $y_i$ a $y_j$ porovnány. 

Poèet v¹ech porovnání je pak souèet jednotlivých $C_{ij}$, tedy $$C = \sum_{i,j} C_{ij}.$$ 
Proto platí: $${\bb E}[C] = {\bb E}[\sum_{i,j} C_{ij}].$$ 
Díky linearitì støední hodnoty mù¾eme tvrdit: $${\bb E}[C] = \sum_{i,j} {\bb E}[C_{ij}].$$
Støední hodnota indikátoru jevu, ¾e prvky  $y_i$ a $y_j$ byly porovnány, je rovna pravdìpodobnosti, ¾e $C_{ij}$ je 1. $${\bb E}[C_{ij}] = P[C_{ij} = 1].$$
Aby $C_{ij}$ se rovnalo $1$ pro prvky $y_i$ a $y_j$, tak se musel pro podposloupnost $y_i, \dots, y_j$ stát pivotem jako první jeden z $y_i$ nebo $y_j$. Kdyby se tak nestalo, tak spolu pøi tomto rozdìlování prvky $y_i$ a $y_j$ nebudou porovnány a dostanou se ka¾dý do jiné skupiny ($L$ a $P$), tak¾e u¾ spolu porovnány nikdy ani nebudou.
Pravpodìodobnost, ¾e $y_i$ nebo $y_j$ se staly pivotem pro posloupnost $y_i, \dots, y_j$  je rovna $2 \over {j-i+1}$ (nebo» pivota vybíráme rovnomìrnì náhodnì). Proto mù¾eme koneènì vyjádøit:

$${\bb E}[C] = \sum_{1 \le i \le j \le n} {2\over{j-i+1}} = \sum_{d=1}^{n-1} { \sum_{n=1}^{n-d \le n} {2\over{d + 1}} }\le \sum_{d=1}^{n-1} {2n\over{d + 1}} = 2n\sum_{d=2}^n {1\over d} = \Theta(n \cdot log{n}).$$

\qed


\bye