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 \h{Lineární èas}
   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 ?
   7
   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 ?
   9
  10 Následující algoritmy vyu¾ívají znalosti rozsahu hodnot na vstupu, a toho, ¾e tento rozsah je malý.
  11
  12 \h{Counting sort}
  13
  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) $.
  15
  16 \s{Algoritmus:} (tøídìní mno¾iny $X$ o velikosti $N$ pomocí {\sc Counting sort}u)
  17
  18 \algo
  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 $
  23 \endalgo
  24
  25 \h{Pøihrádkové tøídìní}
  26
  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 $.
  28
  29 \>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $.
  30
  31 Bucket sort ma je¹tì jednu pøíjemnou vlastnost, jedná se o stabilní tøídìní.
  32
  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.
  34
  35 \s{Algoritmus:} (tøídìní mno¾iny $X$ o velikosti $N$ pomocí {\sc Bucket sort}u)
  36 \algo
  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 $
  48 \endalgo
  49
  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.
  53
  54 Nebo mù¾eme vyu¾ít toho, ¾e bucket-sort je stabilní a tøídit takto:
  55 \algo
  56 \:Pro $ i \leftarrow k $ do $1$ opakuj:
  57 \::BucketSort podle $i$-té souøadnice
  58 \endalgo
  59
  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.
  61
  62 \s{Pozorování:}
  63 po $l$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice.
  64
  65 \proof
  66 Indukcí podle $l$
  67 % FIXME nevim jak presne by mel byt list
  68 \itemize
  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.
  73 \endlist
  74 \qed
  75
  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)$.
  77
  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$?
  81
  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) $.
  84
  85 % FIXME dopsat prepsat..v reseni
  86 \h{Tøídìní øetìzcù}
  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
  89
  90 \h{K èemu je tøídìní dobré?}
  91
  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.
  94
  95 \h{Sorting Zoo}
  96
  97 % FIXME pridat svisle cary..mozna i vodorovne
  98
  99 $$
 100 \vbox {
 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
 107 }
 108 }
 109 $$
 110
 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.
 113
 114 \s{Definice:} {\sc Binární strom} je zakoøenìný strom; ka¾dý vrchol má max. 2 syny, pravého a levého.
 115
 116 Dále budeme pou¾ívat toto znaèení:
 117 $v$ ... vrchol
 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$.
 121
 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 $.
 124
 125 \s{Find($T(v)$,$x$)}
 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$)$.
 128
 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$)$.
 132
 133 \s{Min($T(v)$)}
 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$)$.
 136
 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
 140 \itemize\ibull
 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.
 144 \endlist
 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$)$.
 146
 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
 149 \itemize\ibull
 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ù
 152 \endlist
 153
 154 \h{Vyvá¾ené vyhledávací stromy}
 155
 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$.
 157
 158 \s{Definice:} {\sc Dokonale vyvá¾ení} je takové vyvá¾ení, kde platí $ \forall v: \left \| \|L(v)\| - \|P(v)\| \right \| \leq 1 $
 159
 160 Toto nám jistì zaji¹»uje logaritmickou hloubku, ale je velmi pracné na udr¾ování.
 161
 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 $
 163
 164 Stromùm s hloubkovým vyvá¾ením se øíká AVL stromy. A o nich si doká¾eme následující lemma.
 165
 166 \s{Lemma: } AVL strom o $n$ vrcholech má hloubku $ \O(\log{n}) $.
 167 \proof
 168 Uva¾me $a_k = min \{ \forall \| \{ \forall v: h(v) = k \} \| \} $
 169
 170 Lehce spoèteme:
 171
 172 % FIXME neni spravne a chova se divne
 173 \itemize\ibull
 174 \next $ a_0 = 0 $
 175
 176 \next $ a_1 = 1 $
 177
 178 \next $ a_2 = 2 $
 179
 180 \next $ \vdots $
 181
 182 \next $ a_k = 1 + a_{k - 1} + a_{k - 2} $
 183
 184 \endlist
 185
 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} $
 189
 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})$
 191
 192 \qed
 193
 194 \bye