\input ../lecnotes.tex

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

\h{Lineární èas}
Na minulých pøed¹kách jsme si ukázali tøídìní v èase $ \O(N\log{N}) $, a taky dokázali, ¾e líp to 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 vy¾í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í $ 1 \dots R $ èísel. Tøídí v èase $ \O(N + R) $ s pamì»ovou nároèností $ O(R) $.

\s{Algoritmus:} (tøídìní mno¾iny $X$ o velikosti $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 $
\endalgo

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

Counting sort nám moc nepomù¾e pokud chceme tøídit neco jiného ne¾ èísla, ale i to se dá øe¹it. Pøihrádkové, popøípadì kbelíkové tøídìní, nebo-li 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:} {\sc 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$ o velikosti $N$ pomocí {\sc Bucket sort}u)
\algo
\:Pro $ k \leftarrow 1 $ do $R$ opakuj:
\::$ C[k] \leftarrow 0 $
\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
\::$ C[x[i]] \leftarrow C[X[i]] + 1 $
\:$ b[1] \leftarrow 1 $
\:Pro $ k \leftarrow 2 $ do $R$ opakuj:
\::$ b[k] \leftarrow b[k - 1] + c[b - 1] $
\:Pro $ i \leftarrow 1 $ do $N$ opakuj:
\::$ p \leftarrow X[i] $
\::$ Y[b[p]] \leftarrow p $
\::$ b[p] \leftarrow b[p] + 1 $
\endalgo

\h{Lexikografické tøídìní k-tic}
Mìjme $n$ $k$-tic prvkù z mno¾iny $ \{1 \ldots R \}^k $.Ùkol zní seøadit $k$-tice slovníkovì (lexikograficky).
Mù¾eme pou¾ít metodu rozdìl a panuj, 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.

Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:

\s{Algoritmus:} (tøídìní $k$-tic $ k_1 \ldots k_n $)
\algo
\:$ S \leftarrow \{k_1 \dots k_n\} $
\:Pro $ i \leftarrow k $ do $ 1 $ opakuj:
\::$ S \leftarrow $ BucketSort $ 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øízeny 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 * (n + R))$, co¾ je lineární s délkou vstupu $(k * n)$ a pamì»ová slo¾itost je $\O(n + R)$.

\h{Tøídìní $ 1 \ldots R $ èísel podruhé}
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})} * (n + Z))$. A jak zvolit vhodnì $Z$?

Pokud bychom zvolili $ Z = konstanta $, èasová slo¾itost bude $\O(\log{R} * n) $, co¾ mù¾e být a¾ $ n * \log{n} $.
Zvolíme-li $ Z = n $, dostáváme $ \O({\log{R} \over \log{n}} * n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha * 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} = \max_{1 \leq i \leq n} l_i $ jako délku nejdel¹ího øetìzce a $R$ jako poèet znakù abecedy. Problém je, ¾e øetìzce nemusí být stejnì dlouhé. 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_{max} \cdot 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 doplòující mezery do øetìzù vùbec pøidávat nebudeme.
Nejprve roztøídíme zpùsobem podobným Bucket sortu ø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 \| l_j = i \right\} $. Dále si zavedeme seznam setøízený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_{max} - k + 1 $ (oznaème $l$) a zároveò v nìm tyto øetìzce budou setøízeny lexikograficky od $l$-tého znaku po $ l_{max} $-tý. Z definice tohoto seznamu je patrné, ¾e po $ l_{max} $ 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_{max} $-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.

Algoritmus: (tøídìní øetìzcù)
\algo 
\:$ l_{max} \leftarrow 0 $
\:Pro $ i \leftarrow 1 $ do $ n $ opakuj:
\::$ l_{max} \leftarrow \max(l_{max}, l_i) $
\:Pro $ i \leftarrow 1 $ do $ l_{max} $ opakuj:
\::$ P_i \leftarrow \emptyset $
\::$ p_i \leftarrow 0 $
\:Pro $ i \leftarrow 1 $ do $ n $ opakuj:
\::$ pridej(P_{l_i}, r_i) $
\::$ p_i \leftarrow p_i + 1 $

\:$ S \leftarrow \emptyset $
\:$ s \leftarrow 0 $
\:Pro $ i \leftarrow l_{max} $ do $ 1 $ opakuj:
\::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
\:::$ Q_j \leftarrow \emptyset $
\:::$ q_j \leftarrow 0 $

\::Pro $ j \leftarrow 1 $ do $ p_i $ opakuj:
\:::$ vezmi(P_i, r) $
\:::$ pridej(Q_{r[i]}, r) $
\:::$ q_{r[i]} \leftarrow q_{r[i]} + 1 $
\::Pro $ j \leftarrow 1 $ do $ s $ opakuj:
\:::$ vezmi(S, r) $
\:::$ pridej(Q_{r[i]}, r) $
\:::$ q_{r[i]} \leftarrow q_{r[i]} + 1 $

\:$ S \leftarrow \emptyset $
\:$ s \leftarrow 0 $
\::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
\:::Pro $ k \leftarrow 1 $ do $ q_j $ opakuj:
\::::$ vezmi(Q_j, r) $
\::::$ pridej(S, r) $
\::::$ s \leftarrow s + 1 $

\:vysledek $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¾ hodnoty nejprve setøídit a poté setøizenou posloupnost projít.

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 \| \|L(v)\| - \|P(v)\| \right \| \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 \| h(L(v)) - h(P(v)) \right \| \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 = min \{ \forall \| \{ \forall v: h(v) = 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

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} - 1 > 2^{{k - 1} \over 2} + 2^{{k - 2} \over 2} = 2^{k \over 2} * (2^{-1 \over 2} + 2^{-1}) > 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
