2007/6-trideni/6-trideni.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{6}{Tøídìní v lineárním èase}{(zapsal M.~Kupec, J.~Volec, J.~Ivánek)}
   4
   5 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?
   6
   7 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?
   8
   9 Následující algoritmy vyu¾ívají znalosti rozsahu hodnot na vstupu a toho, ¾e tento rozsah je malý.
  10
  11 \h{Counting sort}
  12
  13 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) $.
  14
  15 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.
  16
  17 \s{Algoritmus:} (tøídìní posloupnosti $ \left ( x_i \right )_0^N $ pomocí {\sc Counting sort}u)
  18
  19 \algo
  20 \:Pro $ i \leftarrow 1 $ do $R$ opakuj:
  21 \::$ p_i \leftarrow 0 $
  22 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
  23 \::$ p_{x_i} \leftarrow p_{x_i} + 1 $
  24 \:$ j \leftarrow 1 $
  25 \:Pro $ i \leftarrow 1 $ do $R$ opakuj:
  26 \::Pokud $ p_i \neq 0 $
  27 \:::$ v_j \leftarrow i $
  28 \:::$ j \leftarrow j + 1 $
  29 \:Vra» $v$
  30 \endalgo
  31
  32 \h{Pøihrádkové tøídìní}
  33
  34 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 $.
  35
  36 \>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.
  37
  38 Bucket sort ma je¹tì jednu pøíjemnou vlastnost: jedná se o stabilní tøídìní.
  39
  40 \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.
  41
  42 \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)
  43 \algo
  44 \:Pro $ k \leftarrow 1 $ do $R$ opakuj:
  45 \::$ p_k \leftarrow 0 $
  46 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
  47 \::$ p_{c_i} \leftarrow p_{c_i} + 1 $
  48 \:$ b_1 \leftarrow 1 $
  49 \:Pro $ k \leftarrow 2 $ do $R$ opakuj:
  50 \::$ b_k \leftarrow b_{k - 1} + p_{b - 1} $
  51 \:Pro $ i \leftarrow 1 $ do $N$ opakuj:
  52 \::$ t \leftarrow c_i $
  53 \::$ v_{b_t} \leftarrow x_i $
  54 \::$ b_t \leftarrow b_t + 1 $
  55 \:Vra» $v$
  56 \endalgo
  57
  58 \h{Lexikografické tøídìní k-tic}
  59 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).
  60 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.
  61 % a dal??
  62 Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:
  63
  64 \s{Algoritmus: } (tøídìní $k$-tic $ x_1, x_2, \ldots ,x_n $ lexikograficky pomocí {\sc Bucket-sort}u)
  65 \algo
  66 \:$ S \leftarrow \{x_1, x_2, \dots, x_n\} $
  67 \:Pro $ i \leftarrow k $ do $ 1 $ opakuj:
  68 \::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice
  69 \:vysledek $ S $
  70 \endalgo
  71
  72 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.
  73
  74 \s{Pozorování:}
  75 Po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
  76
  77 \proof
  78 Indukcí podle $l$
  79 % FIXME nevim jak presne by mel byt list
  80 \itemize
  81 \next Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice.
  82 \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.
  83 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.
  84 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.
  85 \endlist
  86 \qed
  87
  88 È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)$.
  89
  90 \h{Tøídìní èísel $ 1 \ldots R $ podruhé (Radix sort)}
  91 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.
  92 Díky tomu budeme tøídít v èase $\O({\log{R} \over \log{Z}} \cdot (n + Z))$. A jak zvolit vhodnì $Z$?
  93
  94 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.
  95 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) $.
  96
  97 \h{Tøídìní øetìzcù}
  98 Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots l_n $
  99 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.
 100 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) $.
 101 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.
 102 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).
 103
 104 Algoritmus: (tøídìní øetìzcù)
 105 \algo
 106 \:$L \leftarrow \max(l_1, l_2,\ldots,l_n)$
 107 \:Pro $ i \leftarrow 1 $ do $L$ opakuj:
 108 \::$ P_i \leftarrow \emptyset $
 109 \:Pro $ i \leftarrow 1 $ do $ n $ opakuj:
 110 \::$ \<pridej>(P_{l_i}, r_i) $
 111
 112 \:$ S \leftarrow \emptyset $
 113 \:Pro $ i \leftarrow L $ do $ 1 $ opakuj:
 114 \::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
 115 \:::$ Q_j \leftarrow \emptyset $
 116
 117 \::Pro $ j \leftarrow 1 $ do velikost($P_i$) opakuj:
 118 \:::$ \<vezmi>(P_i, r) $
 119 \:::$ \<pridej>(Q_{r[i]}, r) $
 120 \::Pro $ j \leftarrow 1 $ do velikost($S$) opakuj:
 121 \:::$ \<vezmi>(S, r) $
 122 \:::$ \<pridej>(Q_{r[i]}, r) $
 123
 124 \::$ S \leftarrow \emptyset $
 125 \::Pro $ j \leftarrow 1 $ do $ R $ opakuj:
 126 \:::Pro $ k \leftarrow 1 $ do velikost($Q_j$) opakuj:
 127 \::::$ \<vezmi>(Q_j, r) $
 128 \::::$ \<pridej>(S, r) $
 129
 130 \:výsledek $S$
 131 \endalgo
 132
 133 Èasová slo¾itost tohoto algoritmu tedy bude $ \O(RN) $, kde $N$ je délka vstupu a $R$ poèet znakù abecedy.
 134
 135 \h{Sorting Zoo}
 136
 137 % FIXME pridat svisle cary..mozna i vodorovne
 138
 139 $$
 140 \vbox {
 141 \halign{$#$ \hfil & \quad \hfil $#$ & \quad \hfil $#$ & \quad \hfil $#$ \cr
 142 & \O(1) & \O(\log{N}) & \O(N) \cr
 143 \noalign{\medskip\hrule\bigskip}
 144 \O(N^2) & Buble &   & \cr
 145 \O(N\log{N}) & Heap & Quick & Merge \cr
 146 \O(N) &   &   & Bucket \cr
 147 }
 148 }
 149 $$
 150
 151 \h{K èemu je vlastnì tøídìní dobré?}
 152 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ù.
 153 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.
 154
 155 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.
 156 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.
 157
 158 \h{Vyhledávací stromy}
 159 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.
 160
 161 \s{Definice:} {\sc Binární strom} je zakoøenìný strom; ka¾dý vrchol má max. 2 syny, pravého a levého.
 162
 163 Dále budeme pou¾ívat toto znaèení:
 164 $v$ ... vrchol
 165 $l(v)$ ... levý syn, $p(v)$ ... pravý syn
 166 $L(v)$ ... levý podstrom, $p(v)$ ... pravý podstrom
 167 $T(v)$ ... podstrom s koøenem $v$.
 168
 169 \s{Definice:} {\sc Binární vyhledávací strom} je takový binární strom, ¾e ka¾dý vrchol obsahuje prvek z $U$
 170 a pro $ \forall v: \forall x \in L(v): x < v,  \forall x \in P(v): x > v $.
 171
 172 \s{Find($T(v)$,$x$)}
 173 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í.
 174 Toto nám zabere $\O($Hloubka stromu$)$.
 175
 176 \s{Insert($T(v)$,$x$)}
 177 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).
 178 Nejslo¾itìj¹í je operace Find, která trvá $\O($Hloubka stromu$)$.
 179
 180 \s{Min($T(v)$)}
 181 Minimum se nachází v nejlevìj¹ím listu stromu. Jdeme tedy z koøene poøád doleva, dokud nenarazíme na list.
 182 Èasová slo¾itost je $\O($hloubka stromu$)$.
 183
 184 \s{Delete($T(v)$,$x$)}
 185 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:
 186 % FIXME nevim jak presne by mel byt list
 187 \itemize\ibull
 188 \next $x$ je list: Prostì ho sma¾eme.
 189 \next $x$ má jednoho syna: Zru¹íme $x$ a syna pøipojíme na uzel, který ukazoval na $x$.
 190 \next $x$ má dva syny: Najdeme minimum $P(v)$, toto minimum pøehodíme s $x$ a $x$ sma¾eme.
 191 \endlist
 192 È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$)$.
 193
 194 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
 195 % FIXME nevim jak presne by mel byt list
 196 \itemize\ibull
 197 \next vyka¹lat se na to $\rightarrow$ potøeba dokázat prùmìrný pøípad
 198 \next vylep¹it Insert a Delete $\rightarrow$ vyva¾ování stromù
 199 \endlist
 200
 201 \bye