From 71c0feb91ee3e70ba5c45e4589c116f45d45709d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 16 Jun 2007 23:22:14 +0200 Subject: [PATCH] Dostal jsem novou verzi zapisku o QuickSortu a jeste jsem ji trochu vylepsil. --- 5-qs/5-qs.tex | 186 +++++++++++++++++++++++++++----------------------- 1 file changed, 99 insertions(+), 87 deletions(-) diff --git a/5-qs/5-qs.tex b/5-qs/5-qs.tex index c9828f9..7a14e59 100644 --- a/5-qs/5-qs.tex +++ b/5-qs/5-qs.tex @@ -1,9 +1,10 @@ \input ../lecnotes.tex -\prednaska{5}{Tøidìní a QuickSort}{(???)} +\prednaska{5}{QuickSort a slo¾itost tøídìní}{(Michal Sta¹a, ???)} Dostaneme posloupnost, její¾ prvky dovedeme porovnávat, a sna¾íme se co -nejefektivnìji posloupnost setøídit. Mù¾eme napøíklad pou¾ít metodu Rozdìl a panuj: +nejefektivnìji posloupnost setøídit. Uká¾eme si tøídící algoritmus QuickSort +(pro pøátele QS) zalo¾ený na metodì Rozdìl a panuj: \s{Algoritmus:} (QuickSort) @@ -11,119 +12,130 @@ nejefektivn \algo \:Pokud $\vert X\vert \leq 1$, vrátíme~$X$. -\:Vybereme pivota $p \in X$ (pozdìji upøesníme, jak). -\:$M = \{x \in X ; x \le p\}$ -\:$P = \{x \in X ; x = p\}$ -\:$V = \{x \in X ; x \ge p\}$ -\:Vrátíme $\(M) \concat P \concat \(V)$ \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù} +\:Vybereme pivota $p \in X$.\foot{pozdìji upøesníme, jak} +\:$M \leftarrow \{x \in X ; x \le p\}$. +\:$P \leftarrow \{x \in X ; x = p\}$. +\:$V \leftarrow \{x \in X ; x \ge p\}$. +\:Vrátíme $\(M) \concat P \concat \(V)$. \foot{Operátor \uv{$\concat$} znaèí zøetìzení seznamù} \endalgo -\s{Pozorování:} -\itemize\ibull -\:zastaví se -\:vydá správný výsledek (dùkaz napø. indukcí podle $\vert X\vert$) -\:pivot - \itemize\istar - \:pøi ideální volbì: $$ T(n) = 2T(n/2) + O(n) = O(n\log n) $$ (jako u mergesortu) - \:pøi ¹patné volbì: $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2) $$ - \endlist -\:chová se v prùmìru dobøe, a¾ na multiplikativní konstantu -\endlist - -\s{Vìta:} QS s náhodnou volbou pivota má slo¾itost prùmìrnì $\O(n\log n)$ -\foot{Vìta': QS s pevnou volbou pivota má v prùmìru pøes v¹echny permutace na vstupu èasovou slo¾itost $\O(n\log n)$.} - -\proof - -\figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize} - -Provedeme rozdìlováním na fáze, pøi¾em¾ fází rozumíme cestu ve stromu, která sleduje -vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián. -\qed - -\s{Pozorování:} - -\itemize\ibull -\:Ka¾dá fáze rozdìlí vstup na disjunktní èásti a pivoty $X_1, \ldots, X_k$ ($k \geq 2$) - -\:$\forall i: \vert X_i \vert \leq {3\over 4} \vert X \vert$ +\s{Rozbor:} +V¹imnìme si, ¾e QS se urèitì zastaví a také ¾e vydá +správný výsledek. To mù¾eme ovìøit napø. indukcí podle $\vert X\vert$. -\:$\sum_i \vert X_i \vert \leq \vert X \vert$ +Podobnì jako u~vybírání $k$-tého nejmen¹ího prvku v~minulých pøedná¹kách +i zde èasová slo¾itost závisí hlavnì na~volbì pivota. Kdybychom za~pivota +zvolili medián, vy¹la by èasová slo¾itost stejnì jako u~MergeSortu: + $$ T(n) = 2T(n/2) + O(n) = O(n\log n). $$ +Pokud naopak budeme volit pivota ne¹ikovnì, dostaneme: + $$ T(n) = T(n - 1) + \Theta(n) = \Theta(n^2). $$ +V ideálním pøípadì bychom tedy chtìli za pivota zvolit medián, av¹ak jeho pøímým výpoètem +bychom algoritmus pøíli¹ zpomalili. +Pou¾ívá se proto mnoho zpùsobù, jak vybrat rychle pivota blízkého mediánu. +Èasto pou¾ívanou metodou je náhodný výbìr, v~praxi realizovaný nìjakým pseudonáhodným +generátorem. Uká¾eme, ¾e v~tomto pøípadì je QS v~prùmìrném pøípadì rychlý: -\:prùmìrná délka fáze je nejvý¹e~2 (proto¾e pravdìpodobnost na vybrání l¾imediánu je alespoò $1/2$) +\s{Vìta:} QS s~náhodnou volbou pivota má èasovou slo¾itost v~prùmìru +$\O(n\log n)$. -\:v prùmìru poèítáme jednu fázi v èase $\O(n)$ +\s{Poznámka:} Stejnì jako u~výbìru $k$-tého nejmen¹ího prvku bychom také +mohli ukázat, ¾e QS s~pevnou volbou pivota spu¹tìný na~náhodnou permutaci +má tuté¾ èasovou slo¾itost. Detaily nicménì vynecháme. -\:Proto $T(n) = \sum_i T (n_i) + \O(n)$, kde $n = \vert X \vert$, $n_i = \vert X_i \vert$. +\noindent {\sl Dùkaz vìty:} -\endlist +Rozdìlíme bìh algoritmu na~fáze, pøièem¾ fází rozumíme cestu ve~stromu volání, +která sleduje vìt¹í díl a konèí, kdy¾ se povede vybrat za pivota l¾imedián. -\s{Komprimovaný strom} - - - -Hloubka je logaritmická $\Rightarrow$ $\O(log n)$ (proto¾e velikost -fáze klesá exponencálnì, a tak po $\O(\log n)$ krocích dostaneme posloupnosti -velikosti~1). - -Práce na jedné hladinì je $\O(n)$. - -$\Downarrow$ - -Celková èasová slo¾itost je tedy v~prùmìru $\O(n \log n)$. - -Pamì»ové nároky jsou: -$\O(n)$ na pomocné pole -$\O(n)$ na zásobníku +\figure{strom-dukaz.eps}{Dùkaz rozdìlením na fáze}{0.3\hsize} +Ka¾dá fáze pøitom rozdìlí vstup na~disjunktní èásti $X_1, \ldots, X_k$ ($k\ge 2$) +a pivoty, kteøí je oddìlují. Proto je $\sum_i n_i \leq n$, +kde $n$ znaèí velikost vstupu a~$n_i$ velikost $i$-té èásti. Velikost ka¾dé +èásti je navíc nejvý¹e $3/4 \cdot n$ (na~konci fáze to platí proto, ¾e jsme +zvolili l¾imedián, pøedtím jsme v¾dy oddìlili men¹í z~èástí, èili nejvý¹e $n/2$). + +Jedna iterace algoritmu trvá~$\O(n)$ a jeliko¾ l¾imedián vybereme s~pravdìpodobností alespoò $1/2$, +je v~jedné fázi v~prùmìru $\O(1)$ iterací a celá fáze proto v~prùmìru trvá èas~$\O(n)$. +Z~toho dostaneme následující rekurenci pro prùmìrnou èasovou slo¾itost celého algoritmu: +$${\bb E}T(n) = \sum_i {\bb E}T (n_i) + \O(n).$$ + +Tento typ rekurence jsme je¹tì nepotkali a Kuchaøková vìta na~ni nezabere, +ov¹em mù¾eme si pomoci jednoduchou úvahou. Pøedstavme si, ¾e v~na¹em stromu +rekurzivních volání zkomprimujeme ka¾dou fázi do~jednoho vrcholu. Tím vznikne +strom, který odpovídá algoritmu, jen¾ v~jedné iteraci v~prùmìrnì lineárním +èase rozdìlí vstup na~nìkolik èástí a rekurzivnì se na~nì zavolá. + +\s{FIXME:} Obrázek + +Nový strom má logaritmickou hloubku, proto¾e na~ka¾dé dal¹í hladinì jsou +délky posloupností nejvý¹e $3/4$ délek z~pøedchozí hladiny. Navíc souèet +délek pøes ka¾dou hladinu je maximálnì~$n$. Proto na~ka¾dé hladinì +trávíme èas v~prùmìru $\O(n)$ a v~celém stromu tedy $\O(n\log n)$. +\qed -Dal¹í modifikace QSortu mù¾ete najít na: -http://mj.ucw.cz/vyuka/0607/ads1/quicksort.pdf +\s{Pozorování:} Na¹e první verze QS spotøebuje lineární mno¾ství pamìti +na~pomocné pole a na~zásobník. Na~pøedná¹ce jsme ukazovali rùzná jeho +praktická vylep¹ení, které staèí pomocná pamì» o~velikosti $\O(\log n)$. +Detaily viz webové stránky pøedná¹ky. +Známe u¾ nìkolik tøídících algoritmù s~èasovou slo¾itostí $\O(n\log n)$. +Následující vìta ukazuje, ¾e efektivnìj¹í algoritmus v~obecném pøípadì +nese¾eneme. \s{Vìta:} -Ka¾dý tøídící algoritmus zalo¾ený na porovnávání -(a prohazování) potøebuje na~vstup délky~$n$ v~nejhor¹ím pøípadì -$\Omega (n \log n)$ porovnání. +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 \itemize\ibull \:BÚNO nejdøíve algoritmus porovnává a potom - prohazuje (algoritmus mù¾eme upravit tak aby - prohazoval a¾ na~konci). + prohazuje (algoritmus mù¾eme upravit tak, aby si pamatoval + aktuální permutaci prvkù a podle ní prohazoval a¾ na~konci). - \:BÚNO hledáme vstupy, které jsou permutace na $\{1 - n\}$. + \:BÚNO je vstup algoritmu permutace na~mno¾inì $\{1, \ldots, n\}$. - \:Sestrojíme rozhodovací strom na¹eho algoritmu + \:Chování algoritmu popí¹eme rozhodovacím stromem. Jeho vnitøní vrcholy + urèují jednotlivá porovnání prvkù, listy odpovídají okam¾ikùm, kdy + algoritmus pøestal porovnávat a zaèal prohazovat. - +\s{FIXME: Obrázek} - \:Je vidìt, ¾e existence dvou rùzných $\Pi_1$ a $\Pi_2 $, - pøi kterých bychom skonèili ve stejném listu vede ke sporu, - pøitom poèet listù $\geq n!$ -\endlist + \:V¹imneme si, ¾e nemohou existovat dvì vstupní permutace, pro které + by algoritmus skonèil v~tém¾e listu rozhodovacího stromu, jeliko¾ + v~okam¾iku, kdy algoritmus dorazí do~listu, nemù¾e u¾ získávat + ¾ádné informace o~vstupu a ¾ádná posloupnost prohození nemù¾e + setøídit jak první, tak druhou permutaci. Listù stromu je tedy + alespoò tolik, kolik je rùzných vstupù, tedy~$n!$. -{\narrower - \s{Pozorování:} Binární strom hloubku $k$ má poèet listù $\leq 2^k$. - Uva¾me binární strom hloubky $k$ s maximálním poètem listù, pak v¹echny listy - le¾í na poslední hladinì. Víme, ¾e na $i$-té hladinì je $2^i$ vrcholù a - poèet listù je $2^k$. Odtud plyne, ¾e v ka¾édém binárním stromu je maximálnì $2^k$ listù +{\parindent=\leftskip\narrower + \s{Lemmátko:} Binární strom hloubky~$k$ má nejvý¹e $\leq 2^k$ listù. + \par\noindent {\sl Dùkazík:} Uva¾me binární strom hloubky $k$ s~maximálním poètem + listù. V~takovém stromu budou v¹echny listy urèitì le¾et na~poslední hladinì + (kdyby nele¾ely, mù¾eme pod nìkterý list na~vy¹¹í hladinì pøidat dal¹í dva vrcholy a získat + tak \uv{listnatìj¹í} strom stejné hloubky). Jeliko¾ na~$i$-té hladinì je nejvý¹e $2^i$ + vrcholù, v¹ech listù je nejvý¹e~$2^k$. + \qed } - pokraèování pùvodního dùkazu... + Z~tohoto lemmátka plyne, ¾e rozhodovací strom musí být hluboký alespoò + $\log n!$. - Z toho co u¾ víme plyne, ¾e hloubka stromu je nejvý¹e $\log(n!)$. + \:Zbytek je u¾ snadné cvièení z~diskrétní matematiky: - Z diskrétní matematiky víme ¾e: \ - ${n^{n / 2} \leq n!} \leq (n / 2)^n$ - - My potøebujeme jen levou èást, tedy ¾e ${n^{n / 2} \leq n!}$ - Toto jde dokázat pou¾ítím "AG Nerovnosti" - - ...tedy dostáváme, ¾e hloubka stromu je $\geq \log (n^{n / 2}) = (n / 2) - \log (n) \Longrightarrow \Omega (n \log n)$ +{\parindent=\leftskip\narrower + \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 + +} + 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ì. \qed \bye -- 2.39.2