[ads1.git] / 6-trideni / 6-trideni.tex

\input ../lecnotes.tex

\prednaska{6}{Tøídìní v lineárním èase}{(zapsal M.~Kupec, J.~Volec, J.~Ivánek)}

Na minulých pøedna¹kách jsme si ukázali tøídìní v èase $ \O(N\log{N}) $ a také dokázali, ¾e líp to v obecném pøípadì nejde. Jak je tedy mo¾né tøídit v lineárním èase?

V¹echny dosud pøedvedené alrogitmy tøídily pouze pomocí porovnávní hodnot na vstupu. Ale co kdy¾ o vstupu víme víc, tøeba rozsah hodnot na vstup, nedá se toho vyu¾ít?

Následující algoritmy vyu¾ívají znalosti rozsahu hodnot na vstupu a toho, ¾e tento rozsah je malý.

\h{Counting sort}

Counting sort je algoritmus pro tøídìní $N$ celých èísel s maximálním rozsahem hodnot $R$. Tøídí v èase $ \O(N + R) $ s~pamì»ovou nároèností $ \O(R) $.

Algoritmus postupnì prochází vstup a poèítá si ke ka¾dému prvku z~rozsahu kolikrát jej vidìl. Poté a¾ projde celý vstup, projde poèítadla a indexy u~tech, kde nìco napoèítal vydá jako výstup.

\s{Algoritmus:} (tøídìní posloupnosti $ \left ( x_i \right )_0^N $ pomocí {\sc Counting sort}u)

\algo
\:Pro $ i \leftarrow 1 $ do $R$ opakuj:
\::$ p_i \leftarrow 0 $
\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
\::$ p_{x_i} \leftarrow p_{x_i} + 1 $
\:$ j \leftarrow 1 $
\:Pro $ i \leftarrow 1 $ do $R$ opakuj:
\::Pokud $ p_i \neq 0 $
\:::$ v_j \leftarrow i $
\:::$ j \leftarrow j + 1 $
\:Vra» $v$
\endalgo

\h{Pøihrádkové tøídìní}

Counting sort nám moc nepomù¾e, pokud chceme tøídit neco jiného ne¾ celá èísla, ale i to se dá øe¹it. Pøihrádkové, popøípadì kbelíkové tøídìní, neboli bucket-sort umí tøídit mno¾inu prvkù oèíslovaných èísly $ 1 \ldots R $.

\>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.

Bucket sort ma je¹tì jednu pøíjemnou vlastnost: jedná se o stabilní tøídìní.

\s{Definice:} {\it Stabilní tøídìní} je takové, ¾e ka¾dé 2 prvky vstupu se stejnou hodnotou klíèe jsou na výstupu ve stejnìm poøadí jako na vstupu.

\s{Algoritmus:} (tøídìní mno¾iny $ x_1,x_2,\ldots,x_n $ oèíslované $ c_1,c_2,\ldots,c_n $ pomocí {\sc bucket-sort}u)
\algo
\:Pro $ k \leftarrow 1 $ do $R$ opakuj:
\::$ p_k \leftarrow 0 $
\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
\::$ p_{c_i} \leftarrow p_{c_i} + 1 $
\:$ b_1 \leftarrow 1 $
\:Pro $ k \leftarrow 2 $ do $R$ opakuj:
\::$ b_k \leftarrow b_{k - 1} + p_{b - 1} $
\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
\::$ t \leftarrow c_i $
\::$ v_{b_t} \leftarrow x_i $
\::$ b_t \leftarrow b_t + 1 $
\:Vra» $v$
\endalgo

\h{Lexikografické tøídìní k-tic}
Mìjme $n$ uspoøádaných $k$-tic prvkù z mno¾iny $ \{1 \ldots R \}^k $. Úkol zní seøadit \hbox{$k$-tice} slovníkovì (lexikograficky).
Mù¾eme pou¾ít metodu rozdìl a panuj, tak¾e prvky setøídíme nejprve podle první souøadnice $k$-tic a pak se rekurzivnì zavoláme na ka¾dou pøihrádku a tøídíme podle následující souøadnice.
% a dal??
Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:

\s{Algoritmus: } (tøídìní $k$-tic $ x_1, x_2, \ldots ,x_n $ lexikograficky pomocí {\sc Bucket-sort}u)
\algo
\:$ S \leftarrow \{x_1, x_2, \dots, x_n\} $
\:Pro $ i \leftarrow k $ do $ 1 $ opakuj:
\::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice
\:vysledek $ S $
\endalgo

Pro pøehlednost v následujícím pozorování oznaème $ l = k - i + 1 $, co¾ pøesnì odpovídá tomu, v kolikátém prùchodu cyklu jsme.

\s{Pozorování:}
Po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.

\proof
Indukcí podle $l$
% FIXME nevim jak presne by mel byt list
\itemize
\next Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice.
\next Po $l$ prùchodech ji¾ máme prvky setøídìny lexikograficky podle $i$-té a¾ $k$-té souøadnice a spou¹tíme $(l + 1)$-ní prùchod, tj. budeme tøídít podle $(i - 1)$-ní souøadnice.
Proto¾e bucket-sort tøídí stabilnì, zùstanou prvky se stejnou $(i - 1)$-ní souøadnicí vùèi sobì seøazeny tak, jak byly seøazeny na vstupu.
Z IP tam v¹ak byly seøazeny lexikograficky podle $i$-té a¾ $k$-té souøadnice. Tudí¾ po $(l + 1)$-ním prùchodu jsou prvky seøazeny podle $(i - 1)$-ní a¾ $k$-té souøadnice.
\endlist
\qed

Èasová slo¾itost je $\O( k \cdot (n + R))$, co¾ je lineární s délkou vstupu $(k \cdot n)$ pro pevné $k$ a pamì»ová slo¾itost je $\O(n + R)$.

\h{Tøídìní èísel $ 1 \ldots R $ podruhé (Radix sort)}
Zvolíme základ $Z$ a èísla zapí¹eme v soustavì o základu $Z$, èím¾ získáme $ ( \lfloor \log_z{R} \rfloor +1) $-tice, na které spustíme pøedcházející algoritmus.
Díky tomu budeme tøídít v èase $\O({\log{R} \over \log{Z}} \cdot (n + Z))$. A jak zvolit vhodnì $Z$?

Pokud bychom zvolili $ Z = konstanta $, èasová slo¾itost bude $\O(\log{R} \cdot n) $, co¾ mù¾e být $ n * \log{n} $ nebo i víc.
Zvolíme-li $ Z = n $, dostáváme $ \O({\log{R} \over \log{n}} \cdot n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha \cdot n) $.

\h{Tøídìní øetìzcù}
Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots l_n $
Oznaème si $ L = \max_{1 \leq i \leq n} l_i $ délku nejdel¹ího øetìzce a $R$ poèet znakù abecedy. Problém je, ¾e øetìzce nemusí být stejnì dlouhé (pokud by byly, lze se na øetìzce dívat jako na $k$-tice, které u¾ tøídít umíme). S tím se mù¾eme pokusit vypoøádat doplnìním øetìzcù mezerami tak, aby mìly v¹echny stejnou délku, a spustit na nìj algoritmus pro $k$-tice. Tím dostaneme algoritmus, který bude mít èasovou slo¾itost $ \O(L * n) $, co¾ bohu¾el mù¾e být a¾ kvadratické vzhledem k velikosti vstupu. 
Pøíklad: na vstupu mìjme k øetìzcù, kde prvních $k-1$ z nich bude mít délku $1$ a poslední øetìzec bude dlouhý pøesnì $k$. Vstup má tedy celkovou délku $2k-1$ a my teï doplníme prvních $k-1$ øetìzcù mezerami. Vidíme, ¾e algoritmus teï bude pracovat v èase $ \O(k^2) $.
To, co nám nejvíce zpùsobovalo problémy u pøedchozího pøíkladu, bylo velké mno¾ství èasu zabraného porovnáváním doplnìných mezer. Zkusíme proto øe¹it ná¹ problem trochu chytøeji a koncové mezery do øetìzù vùbec pøidávat nebudeme.
Nejprve roztøídíme bucket-sortem øetìzce do pøihrádek (mno¾in) $ P_i $ podle jejich délek, kde $i$ znaèí délku øetìzcù v dané pøihrádce, neboli definujme $ P_i = \left\{ r_j \vert l_j = i \right\} $. Dále si zavedeme seznam setøídìných øetìzcù $S$ takový, ¾e v nìm po $k$-tém prùchodu tøídícím cyklem budou øetìzce s délkou alespoò $ L - k + 1 $ (oznaème $l$) a zároveò v nìm tyto øetìzce budou setøídìny lexikograficky od $l$-tého znaku po $L$-tý. Z definice tohoto seznamu je patrné, ¾e po $L$ krocích tøídícího cyklu bude tento seznam obsahovat v¹echny øetìzce a tyto øetìzce v nìm budou lexikograficky seøazeny. Zbývá u¾ jen popsat, jak tento cyklus pracuje. Nejprve vezme $l$-tou mno¾inu $ P_l $ a její øetìzce roztøídí do pøihrádek $ Q_j $ (kde index $j$ znaèí j-tý znak abecedy) podle jejich $l$-tého (neboli posledního) znaku. Dále vezme seznam $S$ a jeho øetìzce pøidá opìt podle jejich $l$-tého znaku do stejných pøihrádek $ Q_j $ za ji¾ døíve pøidané øetìzce z $ P_l $. Na závìr postupnì projde v¹echny pøihrádky $ Q_j $ a øetìzce v nich pøesune do seznamu $S$. Proto¾e øetìzce z pøihrádek $ Q_j $ bude brát ve stejném poøadí, v jakém do nich byly umístìny, a proto¾e ze seznamu $S$, který je setøízený podle $ (l + 1) $-ního znaku po $L$-tý, bude také brát øetìzce postupnì, bude seznam $S$ po $k$-tém prùchodu pøesnì takový, jaký jsme chtìli (indukcí bychom dokázali, ¾e cyklus pracuje skuteènì správnì). Zároveò z popisu algoritmu je jasné, ¾e bìhem tøídìní ka¾dý znak ka¾dého øetìzce pou¾ijeme právì jednou, tudí¾ algoritmus bude lineární s délkou vstupu (pro úplnost dodejme, ¾e popsaný algoritmus funguje v pøípadech, kdy abeceda má pevnou velikost).

Algoritmus: (tøídìní øetìzcù)
\algo 
\:$L \leftarrow \max(l_1, l_2,\ldots,l_n)$
\:Pro $ i \leftarrow 1 $ do $L$ opakuj:
\::$ P_i \leftarrow \emptyset $
\:Pro $ i \leftarrow 1 $ do $ n $ opakuj:
\::$ \<pridej>(P_{l_i}, r_i) $

\:$ S \leftarrow \emptyset $
\:Pro $ i \leftarrow L $ do $ 1 $ opakuj:
\::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
\:::$ Q_j \leftarrow \emptyset $

\::Pro $ j \leftarrow 1 $ do velikost($P_i$) opakuj:
\:::$ \<vezmi>(P_i, r) $
\:::$ \<pridej>(Q_{r[i]}, r) $
\::Pro $ j \leftarrow 1 $ do velikost($S$) opakuj:
\:::$ \<vezmi>(S, r) $
\:::$ \<pridej>(Q_{r[i]}, r) $

\::$ S \leftarrow \emptyset $
\::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
\:::Pro $ k \leftarrow 1 $ do velikost($Q_j$) opakuj:
\::::$ \<vezmi>(Q_j, r) $
\::::$ \<pridej>(S, r) $

\:výsledek $S$
\endalgo

Èasová slo¾itost tohoto algoritmu tedy bude $ \O(RN) $, kde $N$ je délka vstupu a $R$ poèet znakù abecedy.

\h{Sorting Zoo}

% FIXME pridat svisle cary..mozna i vodorovne

$$
\vbox {
\halign{$#$ \hfil & \quad \hfil $#$ & \quad \hfil $#$ & \quad \hfil $#$ \cr
& \O(1) & \O(\log{N}) & \O(N) \cr
\noalign{\medskip\hrule\bigskip}
\O(N^2) & Buble &   & \cr
\O(N\log{N}) & Heap & Quick & Merge \cr
\O(N) &   &   & Bucket \cr
}
}
$$

\h{K èemu je vlastnì tøídìní dobré?}
Díky nìmu mù¾eme rychle vyhledávat prvky v mno¾inì, konkrétnì v èase $ \O(\log(n)) $ napø. pomocí pùlení intervalù.
Dal¹ím problémem, na který se hodí pou¾ít tøídìní, je zji¹tìní, zda se v posloupnosti nìjaké její hodnoty opakují. Dá se dokázat, ¾e tuto úlohu nelze vyøe¹it lépe (rychleji), ne¾ tak, ¾e hodnoty nejprve setøídíme a poté setøidìnou posloupnost projdeme.

Ukázali jsme si tedy, ¾e v se setøízené mno¾inì jsme schopni vyhledávat prvky v èase $ \O(\log(n)) $. Bohu¾el do ní v èase $ \O(\log(n)) $ neumíme prvky pøidávat. 
Jedním ze zpùsobu, jak zrychlit pøidávání nových prvkù a zároveò nepøijít o logaritmické vyhledávání, je pou¾ít dal¹í datouvou strukturu, vyhledávací stromy.

\h{Vyhledávací stromy}
Problém: chceme udr¾ovat nìjaká data setøízená. To znamená, ¾e chceme udr¾ovat mno¾inu $X$ prvkù z lineárnì uspoøádaného universa $U$ s operacemi Find (najdi prvek), Insert (vlo¾ prvek), Delete (sma¾ prvek). K tomu se nám bude hodit reprezentace dat pomocí stromu.

\s{Definice:} {\sc Binární strom} je zakoøenìný strom; ka¾dý vrchol má max. 2 syny, pravého a levého.

Dále budeme pou¾ívat toto znaèení:
$v$ ... vrchol
$l(v)$ ... levý syn, $p(v)$ ... pravý syn
$L(v)$ ... levý podstrom, $p(v)$ ... pravý podstrom
$T(v)$ ... podstrom s koøenem $v$.

\s{Definice:} {\sc Binární vyhledávací strom} je takový binární strom, ¾e ka¾dý vrchol obsahuje prvek z $U$
a pro $ \forall v: \forall x \in L(v): x < v,  \forall x \in P(v): x > v $.

\s{Find($T(v)$,$x$)}
Procházíme strom od koøene, na ka¾dém vrcholu se podle hodnoty $x$ rozhodneme jak budeme pokraèovat. Buï se hodnota vrcholu rovná $x$, pak konèíme (nalezli jsme hledaný prvek). V opaèném pøípadì pokraèujeme v hledání v levém podstromu ($x$ je men¹í ne¾ hodnota vrcholu), nebo v pravém podstromu ($x$ je vìt¹í ne¾ hodnota vrcholu). Pokud dojdeme do listu a prvek jsme nena¹li, znamená to ¾e tento prvek ve stromì není.
Toto nám zabere $\O($Hloubka stromu$)$.

\s{Insert($T(v)$,$x$)}
Nejprve najdeme místo kam je potøeba prvek vlo¾it, k tomu pou¾ijeme operaci Find. Pokud Find najde $x$ neprovedeme nic (máme strom s jedineènými hodnotami). Jinak vlo¾íme prvek na místo, kde by mìl být (jako syna vrcholu ve kterém skonèil Find).
Nejslo¾itìj¹í je operace Find, která trvá $\O($Hloubka stromu$)$.

\s{Min($T(v)$)}
Minimum se nachází v nejlevìj¹ím listu stromu. Jdeme tedy z koøene poøád doleva, dokud nenarazíme na list.
Èasová slo¾itost je $\O($hloubka stromu$)$.

\s{Delete($T(v)$,$x$)}
Opìt pou¾ijeme Find, zjistíme zda prvek vùbec existuje a kde se nachází. Pokud existuje mù¾ou nastat tyto pøípady:
% FIXME nevim jak presne by mel byt list
\itemize\ibull
\next $x$ je list: Prostì ho sma¾eme.
\next $x$ má jednoho syna: Zru¹íme $x$ a syna pøipojíme na uzel, který ukazoval na $x$.
\next $x$ má dva syny: Najdeme minimum $P(v)$, toto minimum pøehodíme s $x$ a $x$ sma¾eme.
\endlist
Èas je tentokrát malièko slo¾itìj¹í, Find nám trvá $\O($Hloubka stromu$)$ a v posledním pøípadì nalezení Min($P(v)$) trvá taky a¾ $\O($Hloubka stromu$)$, co¾ nám dohromady dává pìkných $\O($Hloubka stromu$)$.

Strom se mù¾e pou¾íváním operací "kazit", napø. opakováním Insert na max. hodnotu co¾ vede a¾ k hloubce $\sim n$. Mù¾eme
% FIXME nevim jak presne by mel byt list
\itemize\ibull
\next vyka¹lat se na to $\rightarrow$ potøeba dokázat prùmìrný pøípad
\next vylep¹it Insert a Delete $\rightarrow$ vyva¾ování stromù
\endlist

\h{Vyvá¾ené vyhledávací stromy}

Pøi vyva¾ování si musíme polo¾it cíl, èeho by jsme chteli dosahnout. Vhodné by bylo, aby stromu zùstala logaritmická hloubka a my se u toho moc nenadøeli. Hloubku stromu budeme znaèit $h$.

\s{Definice:} {\sc Dokonale vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left\vert \vert L(v)\vert - \vert P(v)\vert \right \vert \leq 1 $

Toto nám jistì zaji¹»uje logaritmickou hloubku, ale je velmi pracné na udr¾ování.

\s{Definice:} {\sc Hloubkové vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left \vert h(L(v)) - h(P(v)) \right \vert \leq 1 $

Stromùm s hloubkovým vyvá¾ením se øíká AVL stromy. A o nich si doká¾eme následující lemma.

\s{Lemma: } AVL strom o $n$ vrcholech má hloubku $ \O(\log{n}) $.

\proof
Uva¾me $a_k = $ minimální poèet vrcholù stromu o~hloubce $k$.

Lehce spoèteme:

% FIXME neni spravne a chova se divne
\itemize\ibull
\next $ a_0 = 0 $

\next $ a_1 = 1 $

\next $ a_2 = 2 $

\next $ \vdots $

\next $ a_k = 1 + a_{k - 1} + a_{k - 2} $

\endlist

Rekurentní vzorec jsme dostali rekurzivním stavìním stromu hloubky $k$: nový koøen a 2 podstromy o hloubce $k - 1$ a $k - 2$.

Indukcí doká¾eme, ¾e $ a_k \geq 2^{k \over 2} $.
První indukèní krok jsme si u¾ ukázali, teï pro $ k \geq 2 $ platí:
$ a_k = 1 + a_{k - 1} + a_{k - 2} > 2^{{k - 1} \over 2} + 2^{{k - 2} \over 2} = 2^{k \over 2} \cdot (2^{-{1 \over 2}} + 2^{-1}) \cong 2^{k \over 2} \cdot 1.21 > 2^{k \over 2} $

Tímto jsme dokázali, ¾e na ka¾dé hladinì je minimálnì exponenciálnì vrcholù, co¾ nám zaruèuje hloubku $ \O(\log{n})$

\qed

\bye