X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=13-trideni%2F13-trideni.tex;h=e2e6bb5f81ddb03a4e2e82001cba614d3db014a8;hb=9576270ec08d72c3b8b22fbc418783def1fe5bdd;hp=46914df401aff413c0bbaf77cd1fcf94035c92a5;hpb=d98289cc52361f3f8881b120272943cfb1b4b9db;p=ads1.git diff --git a/13-trideni/13-trideni.tex b/13-trideni/13-trideni.tex index 46914df..e2e6bb5 100644 --- a/13-trideni/13-trideni.tex +++ b/13-trideni/13-trideni.tex @@ -16,23 +16,27 @@ p pivot. Na toto staèí udr¾ovat si dva indexy $a$ a $b$, které znaèí, jak daleko vlevo (vpravo) u¾ jsou správné prvky. -Rekurzivní programy mohou být pro poèítaè zátì¾í. Proto implementujme vlastní zásobník +Rekurzivní programy mají zbyteènì velkou re¾ii. Proto implementujme vlastní zásobník na hranice úsekù, které zbývá setøídit. V¾dy vìt¹í interval vlo¾íme na zásobník a men¹í -rovnou zpracujeme. Na zásobníku tedy bude maximálnì $\log n$ polo¾ek. +rovnou zpracujeme. Na zásobníku proto bude maximálnì $\log n$ polo¾ek. Malé podproblémy dotøídíme nìjakým triviálním algoritmem napøíklad InsertSortem. -Odhadem pro $n=10$ je to pro dne¹ní poèítaèe výhodné. +Odhadem pro $n=10$ je to pro dne¹ní poèítaèe výhodné (zji¹»uje se experimentálnì). \h{Zoo tøídících algoritmù} Porovnejme nyní známé tøídící algoritmy. -Bude nás zajímat i jejich stabilita, tedy jestli zachovají poøadí polo¾ek se stejným -klíèem. Stabilita je dùle¾itá pøi lexikografickém tøídìní, kde se napøed tøídí podle -nejménì významné slo¾ky a pak podle významìj¹ích. +\smallskip -\s{Definice:} {\it Stabilní tøídìní} øíkáme takovému, které u~prvkù se stejnou hodnotou +\s{Definice:} {\I Stabilní tøídìní} øíkáme takovému, které u~prvkù se stejnou hodnotou klíèe zachová jejich vzájemné poøadí, v~jakém byly na~vstupu. +(To se hodí napøíklad pøi lexikografickém tøídìní, kde se napøed tøídí podle +nejménì významné slo¾ky a pak podle významìj¹ích.) + +\s{Definice:} Pokud tøídíme prvky {\I na místì} (tedy vstup dostaneme zadaný v~poli +a v~tomté¾ poli pak vracíme výstup), za {\I pomocnou pamì»} tøídícího algoritmu prohlásíme +ve¹kerou vyu¾itou pamì» mimo vstupní pole. \medskip @@ -48,67 +52,90 @@ kl \>Poznámky k tabulce: \itemize\ibull -\:QuickSort má jen prùmìrnou èasovou slo¾itost $\Theta (\log n)$. Mù¾eme ale øíct, ¾e +\:QuickSort má jen prùmìrnou èasovou slo¾itost $\Theta (n\log n)$. Mù¾eme ale øíct, ¾e porovnáváme prùmìrné èasové slo¾itosti, proto¾e u ostatních algoritmù vyjdou stejnì jako jejich èasové slo¾itosti v~nejhor¹ím pøípadì. \:HeapSort -- tøídìní pomocí haldy. Do haldy vlo¾íme v¹echny prvky a pak je vybereme. -Celkem $n$ operací s haldou, ka¾dá za $\log n$. Navíc tuto haldu mohu stavìt i boøit -v poli, ve kterém dostanu vstup. -\:MergeSort jde implementovat s konstantní pamì»ovou slo¾itostí. +Celkem $\Theta(n)$ operací s haldou, ka¾dá za $\Theta(\log n)$. Navíc tuto haldu mohu stavìt i +rozebírat v~poli, ve kterém dostanu vstup. +\:MergeSort jde implementovat s konstantní pomocnou pamìtí za cenu konstantního +zpomalení, ov¹em konstanta je neprakticky velká. \:MergeSort je stabilní, kdy¾ dìlím pole na poloviny. Není pøi tøídìní spojových seznamù s~rozdìlováním prvkù na sudé a liché. \:QuickSort se dá naprogramovat stabilnì, ale potøebuje lineárnì pomocné pamìti. \endlist \>®ádný algoritmus v tabulce netøídil rychleji ne¾ $\Theta(n\log n)$. To není náhoda --- nasledující vìta nám øíká, ¾e to nejde: +-- následující vìta nám øíká, ¾e to nejde: -{\bf XXX: Letos jsem vìtu dokazoval trochu jinak, nutno pøedìlat.} +\smallskip \s{Vìta:} -Ka¾dý tøídící algoritmus zalo¾ený na porovnávání a prohazování prvkù -potøebuje na vstup délky $n$ v nejhor¹ím pøípadì $\Omega (n \log n)$ porovnání. - -\proof -Bez újmy na obecnosti budeme nejdøíve pøedpokládat o algoritmu dvì vìci: -Jednak to, ¾e algoritmus nejprve porovnává, a teprve potom prohazuje.\foot{Algoritmus -mù¾eme upravit tak, aby si pamatoval aktuální permutaci prvkù a podle ní prohazoval a¾ na konci.} -Také pøedpokládáme, ¾e vstup algoritmu je permutace na mno¾inì $\{1, \ldots, n\}$. +Ka¾dý deterministický tøídící algoritmus, který tøídìné prvky pouze porovnává a kopíruje, +má èasovou slo¾itost $\Omega(n\log n)$. -Chování tohoto algoritmu popí¹eme rozhodovacím stromem. V rozhodovacím stromu vnitøní vrcholy -urèují jednotlivá porovnání prvkù a listy odpovídají okam¾ikùm, kdy algoritmus pøestal porovnávat a zaèal prohazovat. +(O prùmìrné èasové slo¾itosti pravdìpodobnostních tøídících algoritmù se dá dokázat podobná vìta.) -\figure{RozhodovaciStrom.eps}{Rozhodovací Strom}{0.3\hsize} - -Vstup je permutace $n$ prvkù, a víme ¾e poèet rùzných permutací je $n!$. Existuje tedy právì $n!$ rùzných vstupù. -Dále si v¹imneme, ¾e nemohou existovat dvì vstupní permutace, pro které by algoritmus skonèil v tém¾e listu rozhodovacího stromu. -Listù stromu je tedy alespoò tolik, kolik je rùzných vstupù, tedy $n!$. - -{\narrower - \s{Lemmátko:} Binární strom hloubky $k$ má nejvý¹e $2^k$ listù. - \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s maximálním poètem +\proof +Doká¾eme, ¾e ka¾dý porovnávací tøídící algoritmus potøebuje v~nejhor¹ím +pøípadì provést $\Omega(n\log n)$ porovnání, co¾ dává pøirozený dolní odhad +èasové slo¾itosti. + +Pøesnìji øeèeno, doká¾eme, ¾e pro ka¾dý algoritmus existuje vstup libovolné délky~$n$, +na nìm¾ algoritmus provede $\Omega(n\log n)$ porovnání. Bez újmy na obecnosti se budeme +zabývat pouze vstupy, které jsou permutacemi mno¾iny $\{1,\ldots, n\}$. (Staèí nám +najít jeden \uv{tì¾ký} vstup, pokud ho najdeme mezi permutacemi, úkol jsme splnili.) + +Mìjme tedy deterministický algoritmus a nìjaké pevné~$n$. Sledujme, jak algoritmus +porovnává -- u~ka¾dého porovnání zaznamenáme polohy porovnávaných prvkù tak, jak byly +na vstupu. Jeliko¾ algoritmus je deterministický, porovná na zaèátku v¾dy tuté¾ dvojici +prvkù. Toto porovnání mohlo dopadnout tøemi rùznými zpùsoby (vìt¹í, men¹í, rovno). +Pro ka¾dý z~nich je opìt jednoznaènì urèeno, které prvky algoritmus porovná, a tak +dále. Po provedení posledního porovnání algoritmus vydá jako výstup nìjakou jednoznaènì +urèenou permutaci vstupu. + +Chování algoritmu proto mù¾eme popsat rozhodovacím stromem. Vnitøní vrcholy stromu odpovídají +porovnáním prvkù, listy odpovídají vydaným permutacím. Ze~stromu vynecháme vìtve, které +nemohou nastat (napøíklad pokud u¾ víme, ¾e $x_1Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò $\log n!$. +\>Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò $\log_3 n!$. -\>Zbytek je u¾ snadné cvièení z diskrétní matematiky: +\>Zbytek u¾ je snadné cvièení z diskrétní matematiky: -{\narrower +{\narrower\smallskip \s{Lemmátko:} $ n! \ge n^{n / 2}$. \par\noindent {\sl Dùkazík:} $n! = \sqrt{(n!)^2} = \sqrt{1(n-1)\cdot 2(n-2) \cdot \ldots \cdot n\cdot 1}$, co¾ mù¾eme také zapsat jako $\sqrt{1(n-1)}\cdot \sqrt{2(n-2)} \cdot \ldots \cdot \sqrt{n\cdot 1}$. Pøitom pro ka¾dé $1\le k\le n$ je $k(n+1-k) = kn + k - k^2 = n + (k-1)n + k(1-k) = n + (k-1)(n-k) \ge n$. Proto je ka¾dá z~odmocnin vìt¹í nebo rovna $n^{1/2}$ a $n!\ge (n^{1/2})^n = n^{n/2}$. \qed -} +\smallskip} -\>Hloubka stromu tedy èiní minimálnì $\log n! \ge \log(n^{n/2}) = n/2 \cdot \log n = \Omega(n\log n)$, -co¾ také zdola odhaduje poèet porovnání, který algoritmus provede v nejhor¹ím pøípadì. +\>Hloubka stromu tedy èiní minimálnì $\log_3 n! \ge \log_3(n^{n/2}) = n/2 \cdot \log_3 n = \Omega(n\log n)$, +co¾ jsme chtìli dokázat. \qed Ukázali jsme si tøídìní v èase $ \O(N\log{N}) $ a také dokázali, ¾e líp to v obecném @@ -121,44 +148,47 @@ Co kdy \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) $. +$R$. Tøídí v èase $ \Theta(N + R) $ s~pamì»ovou nároèností $ \Theta(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. +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 postupnì vypí¹e v¹echna èísla z~rozsahu +ve~správném poètu kopií. -\s{Algoritmus:} (tøídìní posloupnosti $\left ( x_i \right )_0^N$ pomocí {\it Counting sort}u) +\s{Algoritmus:} (tøídìní posloupnosti $x_1,\ldots,x_N\in\{1,\ldots,R\}$ pomocí {\I Counting sort}u) \algo -\:Pro $ i \leftarrow 1 $ do $R$ opakuj: +\:Pro $ i = 1 \ldots R$ opakujeme: \::$ p_i \leftarrow 0 $ -\:Pro $ i \leftarrow 1 $ do $N$ opakuj: +\:Pro $ i = 1 \ldots N$ opakujeme: \::$ p_{x_i} \leftarrow p_{x_i} + 1 $ \:$ j \leftarrow 1 $ -\:Pro $ i \leftarrow 1 $ do $R$ opakuj: -\::Pokud $ p_i \neq 0 $ +\:Pro $ i = 1 \ldots R$ opakujeme: +\::Pokud $ p_i \neq 0 $: \:::$ v_j \leftarrow i $ \:::$ j \leftarrow j + 1 $ -\:Vra» $v$ +\:Vrátíme výsledek $v_1,\ldots,v_N$. \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 $. +Counting sort nám moc nepomù¾e, pokud chceme tøídit ne pøímo celá èísla, nýbr¾ +záznamy s~celoèíselnými klíèi. Na ty se bude hodit pøihrádkové tøídìní neboli +{\I Bucket-sort} (\uv{kbelíkové tøídìní}). -\>Potøebuje k tomu èas $ \O(N + R) $ a pamì» $ \O(N + R) $. +Uva¾ujme opìt~$N$ prvkù s~klíèi v~rozsahu $1,\ldots,R$. Poøídíme si~$R$ pøihrádek +$P_1,\ldots,P_R$, prvky do nich roztøídíme a pak postupnì vypí¹eme obsah pøihrádek +v~poøadí podle klíèù. -Bucket sort ma je¹tì jednu pøíjemnou vlastnost: jedná se o stabilní tøídìní. +\>Potøebujeme k tomu èas $ \Theta(N + R) $ a pamì» $ \Theta(N + R) $. Navíc se jedná +o~stabilní algoritmus. -\s{Algoritmus:} (tøídìní mno¾iny $x_1, x_2, \ldots, x_n $ oèíslované $c_1, c_2, \ldots, c_n$ pomocí {\it bucket-sort}u) +\s{Algoritmus:} (tøídìní prvkù $x_1, \ldots, x_n $ s~klíèi $c_1, \ldots, c_n\in\{1,\ldots,R\}$ pomocí {\I bucket-sort}u) \algo -\:$P_1 \dots P_R \leftarrow \emptyset$ -\:Pro $i=1\dots n$: -\::vlo¾ $x_i$ do $P_{x_i}$ -\:Pro $j=1\dots R$ -\::vypi¹ co je v $P_j$ +\:$P_1 \ldots P_R \leftarrow \emptyset$ +\:Pro $i=1\ldots n$: +\::Vlo¾íme $x_i$ do $P_{c_i}$. +\:Pro $j=1\ldots R$ +\::Vypi¹eme obsah $P_j$. \endalgo \h{Lexikografické tøídìní k-tic} @@ -169,48 +199,49 @@ zavol % 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í {\it Bucket-sort}u) +\s{Algoritmus: } (tøídìní $k$-tic $ x_1, \ldots ,x_n $ lexikograficky pomocí {\it 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 $ +\:$ S \leftarrow x_1, \ldots, x_n.$ +\:Pro $ i = k $ a¾ $ 1 $ opakujeme: +\::$ S \leftarrow $ bucket-sort $ S $ podle $i$-té souøadnice. +\:Vydáme výsledek $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. +Pro pøehlednost v následujícím pozorování oznaème $ \ell = 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. +Po $\ell$-tém prùchodu cyklem jsou prvky uspoøádány lexikograficky podle $i$-té a¾ $k$-té souøadnice. \proof -Indukcí podle $l$: +Indukcí podle $\ell$: \itemize\ibull -\:Pro $ l = 1 $ jsou prvky uspoøádány podle poslední souøadnice. -\: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. +\:Pro $ \ell = 1 $ jsou prvky uspoøádány podle poslední souøadnice. +\:Po $\ell$ prùchodech ji¾ máme prvky setøídìny lexikograficky podle $i$-té a¾ $k$-té souøadnice a spou¹tíme $(\ell + 1)$-ní prùchod, tj. budeme tøídit 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. +Z IP tam v¹ak byly seøazeny lexikograficky podle $i$-té a¾ $k$-té souøadnice. Tudí¾ po $(\ell + 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$; pamì»ová slo¾itost èiní $\O(n + R)$. +Èasová slo¾itost je $\Theta( k \cdot (n + R))$, co¾ je lineární s délkou vstupu $(k \cdot n)$ pro pevné $k$ a~$R$; pamì»ová slo¾itost èiní $\Theta(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$? +Díky tomu budeme tøídit v èase $\Theta({\log{R} \over \log{Z}} \cdot (n + Z))$. Jak zvolit vhodné $Z$? -Pokud bychom zvolili $Z$ konstantní, è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 n) $. +Pokud bychom zvolili $Z$ konstantní, èasová slo¾itost bude $\Theta(\log{R} \cdot n) $, co¾ mù¾e být $ n \log{n} $ nebo i víc. +Zvolíme-li $ Z = n $, dostáváme $ \Theta({\log{R} \over \log{n}} \cdot n) $, co¾ pro $ R \leq n^\alpha $ znamená $ \O(\alpha n) $. +Polynomiálnì velká celá èísla jde tedy tøídit v~lineárním èase. \h{Tøídìní øetìzcù} \>{\I (Na pøedná¹ce letos nebylo, ale pro úplnost uvádíme.)} -Mìjme $n$ øetìzcù $ r_1, r_2 \dots r_n $ dlouhých $ l_1, l_2 \dots +Mìjme $n$ øetìzcù $ r_1, r_2 \ldots r_n $ dlouhých $ l_1, l_2 \ldots 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 +dívat jako na $k$-tice, které u¾ tøídit 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(Ln) $, co¾ bohu¾el mù¾e být a¾ kvadratické vzhledem k velikosti vstupu. @@ -290,7 +321,7 @@ Algoritmus: (t \+ HeapSort & $\Theta (n\log n)$ & $\Theta (1)$ & $-$ \cr \+ QuickSort & $\Theta (n\log n)$ & $\Theta (\log n)$ & $-$ \cr \+ BucketSort & $\Theta (n+R)$ & $\Theta (n+R)$ & $+$ \cr -\+ k-tice & $\Theta (k(n+R))$ & $\Theta (n+R)$ & $+$ \cr +\+ $k$-tice & $\Theta (k(n+R))$ & $\Theta (n+R)$ & $+$ \cr \+ RadixSort & $\Theta (n\log _n R)$ & $\Theta (n)$ & $+$ \cr \smallskip @@ -299,7 +330,7 @@ Algoritmus: (t 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. +tak, ¾e hodnoty nejprve setøídíme a poté setøídìnou posloupnost projdeme. \h{Násobení matic n$\times$n a Strassenùv algoritmus}