3 \prednaska{6}{Tøídìní v lineárním èase}{(zapsal M.~Kupec, J.~Volec, J.~Ivánek)}
6 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 ?
8 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 ?
10 Následující algoritmy vyu¾ívají znalosti rozsahu hodnot na vstupu, a toho, ¾e tento rozsah je malý.
14 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) $.
16 \s{Algoritmus:} (tøídìní mno¾iny $X$ o velikosti $N$ pomocí {\sc Counting sort}u)
19 \:Pro $ i \leftarrow 1 $ do $R$ opakuj:
20 \::$ P[i] \leftarrow 0 $
21 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
22 \::$ P[X[i]] \leftarrow P[X[i] + 1 $
25 \h{Pøihrádkové tøídìní}
27 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 $.
29 \>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.
31 Bucket sort ma je¹tì jednu pøíjemnou vlastnost, jedná se o stabilní tøídìní.
33 \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.
35 \s{Algoritmus:} (tøídìní mno¾iny $X$ o velikosti $N$ pomocí {\sc Bucket sort}u)
37 \:Pro $ k \leftarrow 1 $ do $R$ opakuj:
38 \::$ C[k] \leftarrow 0 $
39 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
40 \::$ C[x[i]] \leftarrow C[X[i]] + 1 $
41 \:$ b[1] \leftarrow 1 $
42 \:Pro $ k \leftarrow 2 $ do $R$ opakuj:
43 \::$ b[k] \leftarrow b[k - 1] + c[b - 1] $
44 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
45 \::$ p \leftarrow X[i] $
46 \::$ Y[b[p]] \leftarrow p $
47 \::$ b[p] \leftarrow b[p] + 1 $
50 \h{Lexikografické tøídìní k-tic}
51 Mìjme $n$ $k$-tic z $ \{1 \ldots R \}^k $ (prvky $k$-tice jsou $ 1 \ldots R $), seøazení $k$-tic slovníkovì (lexikograficky).
52 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.
54 Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:
56 \:Pro $ i \leftarrow k $ do $1$ opakuj:
57 \::BucketSort podle $i$-té souøadnice
60 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.
63 po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
67 % FIXME nevim jak presne by mel byt list
69 \next Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice
70 \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.
71 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.
72 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.
76 È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)$.
78 \h{Tøídìní $ 1 \ldots R $ èísel podruhé}
79 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.
80 Díky tomu budeme tøídít v èase $\O({\log{R} \over (\log{Z})} * (n + Z))$. A jak zvolit vhodnì $Z$?
82 Pokud bychom zvolili $ Z = konstanta $, èasová slo¾itost bude $\O(\log{R} * n) $, co¾ mù¾e být a¾ $ n * \log{n} $.
83 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) $.
85 % FIXME dopsat prepsat..v reseni
87 Mìjme $n$ øetìzcù dlouhých $ l_1, l_2, \ldots, l_n $ tøídíme $ O(n + \sum_{i}{l_i}) $
88 Problém: øetìzce nejsou stejnì dlouhé, je potøeba se vyhnout pøehazování mezer
90 \h{K èemu je tøídìní dobré?}
92 Abychom mohli rychleji hledat - v logaritmickém èase pùlením intervalù.
93 Pokud chceme zjistit, zda se nìjaké hodnoty opakují, nejde to udìlat lépe ne¾ data setøídít.
97 % FIXME pridat svisle cary..mozna i vodorovne
101 \halign{$#$ \hfil & \quad \hfil $#$ & \quad \hfil $#$ & \quad \hfil $#$ \cr
102 & \O(1) & \O(\log{N}) & \O(N) \cr
103 \noalign{\medskip\hrule\bigskip}
104 \O(N^2) & Buble & & \cr
105 \O(N\log{N}) & Heap & Quick & Merge \cr
106 \O(N) & & & Bucket \cr
111 \h{Vyhledávací stromy}
112 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.
114 \s{Definice:} {\sc Binární strom} je zakoøenìný strom; ka¾dý vrchol má max. 2 syny, pravého a levého.
116 Dále budeme pou¾ívat toto znaèení:
118 $l(v)$ ... levý syn, $p(v)$ ... pravý syn
119 $L(v)$ ... levý podstrom, $p(v)$ ... pravý podstrom
120 $T(v)$ ... podstrom s koøenem $v$.
122 \s{Definice:} {\sc Binární vyhledávací strom} je takový binární strom, ¾e ka¾dý vrchol obsahuje prvek z $U$
123 a pro $ \forall v: \forall x \in L(v): x < v, \forall x \in P(v): x > v $.
126 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í.
127 Toto nám zabere $\O($Hloubka stromu$)$.
129 \s{Insert($T(v)$,$x$)}
130 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).
131 Nejslo¾itìj¹í je operace Find, která trvá $\O($Hloubka stromu$)$.
134 Minimum se nachází v nejlevìj¹ím listu stromu. Jdeme tedy z koøene poøád doleva, dokud nenarazíme na list.
135 Èasová slo¾itost je $\O($hloubka stromu$)$.
137 \s{Delete($T(v)$,$x$)}
138 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:
139 % FIXME nevim jak presne by mel byt list
141 \next $x$ je list: Prostì ho sma¾eme.
142 \next $x$ má jednoho syna: Zru¹íme $x$ a syna pøipojíme na uzel, který ukazoval na $x$.
143 \next $x$ má dva syny: Najdeme minimum $P(v)$, toto minimum pøehodíme s $x$ a $x$ sma¾eme.
145 È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$)$.
147 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
148 % FIXME nevim jak presne by mel byt list
150 \next vyka¹lat se na to $\rightarrow$ potøeba dokázat prùmìrný pøípad
151 \next vylep¹it Insert a Delete $\rightarrow$ vyva¾ování stromù
154 \h{Vyvá¾ené vyhledávací stromy}
156 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$.
158 \s{Definice:} {\sc Dokonale vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left \| \|L(v)\| - \|P(v)\| \right \| \leq 1 $
160 Toto nám jistì zaji¹»uje logaritmickou hloubku, ale je velmi pracné na udr¾ování.
162 \s{Definice:} {\sc Hloubkové vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left \| h(L(v)) - h(P(v)) \right \| \leq 1 $
164 Stromùm s hloubkovým vyvá¾ením se øíká AVL stromy. A o nich si doká¾eme následující lemma.
166 \s{Lemma: } AVL strom o $n$ vrcholech má hloubku $ \O(\log{n}) $.
168 Uva¾me $a_k = min \{ \forall \| \{ \forall v: h(v) = k \} \| \} $
172 % FIXME neni spravne a chova se divne
182 \next $ a_k = 1 + a_{k - 1} + a_{k - 2} $
186 Indukcí doká¾eme, ¾e $ a_k \geq 2^{k \over 2} $.
187 První indukèní krok jsme si u¾ ukázali, teï pro $ k \geq 2 $ platí:
188 $ 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} $
190 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})$