From 1f344f8b3c8e57d59411daa6f51d63a32133f563 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 May 2007 13:26:34 +0200 Subject: [PATCH] Zjednodusil jsem analyzu algoritmu pro nasobeni a ukazal na ni obe metody reseni rekurenci. Jinak tez spousta drobnych korektur. --- 2-rozdel/2-rozdel.tex | 356 +++++++++++++++++++++--------------------- 1 file changed, 177 insertions(+), 179 deletions(-) diff --git a/2-rozdel/2-rozdel.tex b/2-rozdel/2-rozdel.tex index 37fd513..c1289b2 100644 --- a/2-rozdel/2-rozdel.tex +++ b/2-rozdel/2-rozdel.tex @@ -2,23 +2,29 @@ \prednaska{2}{Rozdìl a panuj}{(zapsali J. Záloha a P. Ba¹ista)} -Dne¹ní pøedná¹ka se bude týkat analýzy slo¾itosti algoritmù -a zejména metody Rozdìl a panuj {\sl (Divide et Impera)}. +Na~minulé pøedná¹ce jsme si zavedli výpoèetní model a èasovou slo¾itost. +Nyní se pustíme do~analýzy slo¾itosti rùzných algoritmù, zejména rekurzivních +zalo¾ených na metodì Rozdìl a panuj {\sl (Divide et Impera)}. -Pro porovnávání algoritmù si musíme zavést nìjaké kritérium. Vìt¹inou se zajímáme o èas a pamì», které spotøebují pro svùj bìh. Proto, abychom mohli takto algoritmy porovnávat bez ohledu na prostøedí, poèítaè a podobné vìci, zavádíme takzvanou $\O$-notaci. +\h{Asymptotická notace} + +Jak u¾ víme, pøi porovnávání algoritmù je obvykle rozhodující asymptotické +chování a multiplikativní konstanty mù¾eme zanedbávat (beztak závisí na~konkrétním +poèítaèi). Proto si zavedeme takzvanou asymptotickou notaci, která slou¾í +pro právì takové porovnávání rùstu funkcí: \s{Definice:} Pro funkce $f,g: {\bb N} \rightarrow {\bb R}^+$ øekneme, -¾e $f$ je $\O(g)$ právì tehdy kdy¾ $\exists c>0, c \in {\bb R}: \forall ^{*} n \in {\bb N}: f(n) \leq c \cdot g(n)$. +¾e $f$ je $\O(g)$ právì tehdy, kdy¾ $\exists c>0: \forall ^{*} n \in {\bb N}: f(n) \leq c \cdot g(n)$. Zde $\forall^* n \in {\bb N}$ je zkratka za \uv{$\exists n_0 \in {\bb N}: \forall n \geq n_0$}, tedy \uv{pro v¹echna~$n$ a¾ na~koneènì mnoho výjimek.} -\s{Poznámka:} $\O$-notace tedy vyjadøuje, ¾e funkce~$f$ je men¹í nebo nejvý¹e rovná -nìjakému reálnému násobku funkce~$g$ skoro v¹ude. Aèkoliv zápis vypadá jako rovnost, rozhodnì +\s{Poznámka:} $\O$-notace tedy vyjadøuje, ¾e funkce~$f$ je skoro v¹ude men¹í nebo nejvý¹e rovná +nìjakému reálnému násobku funkce~$g$. Aèkoliv zápis vypadá jako rovnost, rozhodnì není symetrický: napøíklad platí $\log n=\O(n)$, ale neplatí $n=\O(\log n)$. Formálnì by bylo lep¹í pova¾ovat $\O(g)$ za tøídu funkcí, pro které platí, ¾e se dají shora odhadnout kladným násobkem funkce~$g$, a~psát tedy~$f\in\O(g)$, ale zvyk je bohu¾el ¾elezná ko¹ile. -\s{Pøíklady:} $2{,}5n^{2} = \O(n^{2})$, $2{,}5n^{2}+30n = \O(n^{2})$. +\s{Pøíklady:} $2.5n^{2} = \O(n^{2})$, $2.5n^{2}+30n = \O(n^{2})$. \>Také platí: $$ @@ -34,136 +40,122 @@ To plat \:$\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})$. \endlist -$\O$-notace popisuje horní odhad asymptotického chování algoritmù. Mnohdy v¹ak -potøebujeme také urèit jeho spodní hranici, popøípadì je odhadnout obì. -U~nìkterých algoritmù sice splývají, ale u nìkterých ne, tak¾e zavádíme dal¹í -notace: +$\O$-notace popisuje horní odhad asymptotického chování funkce. Mnohdy v¹ak +potøebujeme také odhandout funkci zespodu (chceme-li øíci, ¾e algoritmus potøebuje +{\I alespoò} nìjaké mno¾ství èasu nebo pamìti), pøípadnì z~obou stran: \s{Definice:} \itemize\ibull -\:$f=\Omega(g) \Longleftrightarrow \exists$ $c>0:$ $\exists$ $g(n): \forall ^{*} n \in {\bb N}: f(n) \geq c\cdot g(n)$ +\:$f=\Omega(g) \equiv \exists c>0:\forall^* n \in {\bb N}: f(n) \geq c\cdot g(n)$. -$\Omega$-notace øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾ nìjaký $c$-násobek funkce $g$, a tedy $g=\O(f)$. -\:$f=\Theta(g) \Longleftrightarrow f=O(g) \wedge f=\Omega(g)$ +$\Omega$-notace tedy øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾ nìjaký $c$-násobek funkce $g$, a tedy $g=\O(f)$. +\:$f=\Theta(g) \equiv f=O(g) \wedge f=\Omega(g)$ -nebo: +nebo výøeènìji: -$f=\Theta(g) \Longleftrightarrow \exists$ $c_{1},c_{2} > 0:\exists$ $g(n) : c_{1}\cdot g(n) \leq f(n) \leq c_{2}\cdot g(n)$ To znamená, ¾e existují nezáporné reálne konstanty $c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranièit $c_{1}$ a $c_{2}$ násobky funkce $g(n)$. +$f=\Theta(g) \equiv \exists$ $c_{1},c_{2} > 0: c_{1}\cdot g(n) \leq f(n) \leq c_{2}\cdot g(n)$ To znamená, ¾e existují nezáporné reálne konstanty $c_{1},c_{2}$ takové, ¾e se funkce $f(n)$ dá ohranièit $c_{1}$- a $c_{2}$-násobkem funkce $g(n)$. \endlist -\noindent -$\Theta$-notace tedy vyjadøuje, ¾e chování algoritmu je shora i zespoda odhadnuto nìjakými kladnými rálnymi násobky funkce $g$. Proto je zøejmé, ¾e se v¾dy bude asymptoticky chovat stejnì. - \s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich chování od~nejlep¹ích k~nejhor¹ím) \itemize\ibull \:$\Theta(1) \ldots$ funkce zespoda i shora ohranièené konstantami \:$\Theta(\log{( \log{n} )})$ -\:$\Theta(\log{n}) \ldots$logaritmická -\:$\Theta(n^{\varepsilon}), \varepsilon \in (0,1) \ldots$ sublineární -\:$\Theta(n) \ldots$ lineární -\:$\Theta(n^{2}) \ldots$ kvadratická - -$\vdots$ - -\:$\Theta(n^{k}), k \in {\bb N} \ldots$ polynomiální - -$\vdots$ - -\:$\Theta(2^{n}) \ldots$ exponenciální pøi základu $2$ -\:$\Theta(3^{n}) \ldots$ exponenciální pøi základu $3$ - -$\vdots$ - -\:$\Theta(k^{n}), k \in \bb{R}^{+},$ $k > 1 \ldots$ exponenciální pøi základu $k$ - -$\vdots$ - -\:$\Theta(n!) \ldots$ faktoriálová - -$\vdots$ - +\:$\Theta(\log{n})$ \dots\ logaritmická +\:$\Theta(n^{\varepsilon}), \varepsilon \in (0,1)$ \dots\ sublineární +\:$\Theta(n)$ \dots\ lineární +\:$\Theta(n^{2})$ \dots\ kvadratická +\:$\Theta(n^{k})$ \dots\ polynomiální +\:$\Theta(2^{n})$ \dots\ exponenciální pøi základu $2$ +\:$\Theta(3^{n})$ \dots\ exponenciální pøi základu $3$ +\:$\Theta(k^{n})$ \dots\ exponenciální pøi základu $k>1$ +\:$\Theta(n!)$ \dots\ faktoriálová \:$\Theta(n^{n})$ - -$\vdots$ +\:\dots\ nekoneènì mnoho dal¹ích tøíd (i mezi tìmi vý¹e uvedenými) \endlist -\>{\sl Poznámka:} Pøi logaritmech a odhadech slo¾itosti se dá v¾dy hovoøit o logaritmu s~libovolným základem, proto¾e~platí: +\>{\sl Poznámka:} Pokud se v~odhadu slo¾itosti vyskytne logaritmus (jinde ne¾ +v~exponentu), nezále¾í na tom, jaký má základ, proto¾e platí: $$ \log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n}, $$ -kde ${1}\over{\log_c{k}}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$.} - -\>{\sl Pøíklady:} - -\s{Eukleidùv algoritmus:} Pokud jej pustíme na $2$ èísla o $n$ bitech, poèet iterací bude $\O(n)$, ka¾dá iterace trvá $\O(n^{2})$ krokù. Tak¾e celkovì má tento algoritmus èasovou slo¾itost $\O(n^{3})$. - -\s{Rozdìl a panuj:} A nyní pøestaòme chodit kolem horké ka¹e a øekòeme si, co to ono vý¹e zmiòované \uv {rozdìl a panuj} znamená. Mìjme nìjaký problém, který má tu vlastnost, ¾e kdy¾ jej rozdìlíme na nìjaké podproblémy, které mají stejný charakter a ty vyøe¹íme, tak slo¾ením jejich øe¹ení získáme øe¹ení pùvodního problému. Po¾adavek na stejný charakter podproblémù je podstatný, nebo» nám umo¾ní se podívat na tyto podproblémy pod stejným úhlem a opìt je rozdìlit na \uv {podpodproblémy} a tak dále, a¾ se dostaneme na úroveò, kterou je mo¾né vyøe¹it triviálnì, popøípadì jiným, ménì nároèným, zpùsobem. (V této chvíli je dokonèena èást rozdìlování.) Po jejich vyøe¹ení se zaèneme vynoøovat z rekurze a na jednotlivých hladinách skládat øe¹ení, a¾ se ocitneme na hladinì pùvodního problému. Po~posledním slo¾ení je pùvodní úloha vyøe¹ena. - -\s{Odboèka:} \>{\sl (Mergesort)} Pøi prùbìhu algoritmu mergesort nejprve rozdìlujeme vstup na dvì \uv{stejnì} (v hor¹ím pøípadì a¾ na jednotku) velké èásti. To nám zabere na ka¾dé hladinì konstantní práci $\O(1)$. - -\noindent -Kdy¾ se v¹ak vynoøujeme z rekurze, musíme na ka¾dé hladinì strávit linárnì èasu sluèováním: - -$T(n)=2 \cdot T({{n}/{2}})+\O(n)$. - -\noindent -Souèet práce pøes jednu hladinu stromu je $\O(n)$. Víme, ¾e celkový poèet hladin je $\O(\log{n})$, a tudí¾ jsme ukázali, ¾e~èasová slo¾itost algoritmu je $\O(n \cdot \log n)$. - -\s{Rychlej¹í algoritmus pro násobení:} \>{\sl (rychlej¹í ne¾ $\O(n^{2})$)} Pokud násobíme dvì èísla $X$ a $Y$ zpùsobem, který nás uèili na základní ¹kole, dostaneme se na èasovou slo¾itost $\O(n^2)$. Proto¾e se jedná o dost èastou operaci, zamysleme se, jestli by ne¹la zrychlit. Nasmìrujme na¹e úvahy na postup \uv{rozdìl a panuj}. Rozdìlíme ka¾dého èinitele na dvì stejnì dlouhé èásti a pro jednoduchost pøedpokládejme, ¾e toto roz¹tìpení èinitele probìhne v¾dy bez zbytku: - -$$ -X=A \cdot 10^{{n}/2}+B -$$ -$$ -Y=C \cdot10^{{n}/{2}}+D -$$ - -\noindent -Zde $A, B, C, D$ jsou u¾ jen $n/2$ ciferná èísla. Potom získáme pùvodní souèin $X \cdot Y$ jako: - -\noindent -$X \cdot Y=(A\cdot 10^{{n}/{2}}+B)\cdot (C\cdot 10^{{n}/{2}}+D)=A\cdot C\cdot 10^{n}+A\cdot D\cdot 10^{{n}/{2}}+B\cdot C\cdot 10^{{n}/{2}}+B\cdot D=A\cdot C\cdot 10^{n}+(A\cdot D+B\cdot C)\cdot 10^{{n}/{2}}+B\cdot D$ - -\noindent -Nyní, jak vidíme, staèí spoèítat souèin ètyø ${n}/{2}$ ciferných císel. Uva¾me, jak se tím zmìní celková èasová slo¾itost: - -\noindent -$T(n)=4\cdot T({{n}/{2}})+O(n)=4\cdot T({{n}/{2}})+c\cdot n=4\cdot (4\cdot T({{n}/{4}})+c\cdot {{n}/{2}})+c\cdot n=4^{2}\cdot T({{n}\over{4}})+2\cdot c\cdot n+c\cdot n=4^{2}\cdot T({{n}/{4}})+3\cdot c\cdot n=4^{2}\cdot (4\cdot T({{n}/{8}})+c\cdot {{n}/{4}})+3\cdot c\cdot n=4^{3}\cdot T({{n}/{8}})+4\cdot c\cdot n+3\cdot c\cdot n=4^{3}\cdot T({{n}/{8}})+7\cdot c\cdot n=\ldots$ - -\noindent -takto bychom mohli pokraèovat dále, a¾ bychom se dostali na: - -$$ -\eqalign{ -T(n) &= 4^{4}\cdot T\left({{n}\over{16}}\right)+15\cdot c\cdot n \cr -T(n) &= 4^{5}\cdot T\left({{n}\over{32}}\right)+31\cdot c\cdot n \cr -&\vdots \cr -} -$$ -Odtud mù¾eme vypozorovat, ¾e se vztah pro $T(n)$ vyvíjí zøejmì podle vzorce: -$$ -T(n)=4^{k}\cdot T\left({{n}\over{2^{k}}}\right)+2^{k-1}\cdot c\cdot n+2^{k-2}\cdot c\cdot n+2^{k-3}\cdot c\cdot n+2^{k-4}\cdot c\cdot n+\ldots+2^{0}\cdot c\cdot n, -$$ -$$ -T(n)=4^{k}\cdot T\left({{n}\over{2^{k}}}\right)+(2^{k}-1)\cdot c\cdot n, -$$ -kde $k$ je poèet vìtvení a $n$ je velikost úlohy. Kdy¾ uvá¾íme, ¾e se strom volaní v¾dy vìtví pravidelnì na dva podstromy, tak platí: $k =\left\lceil \log{n} \right\rceil$. Dosadíme: -$$ -\eqalign{ -T(n)&=4^{\log{n}}\cdot T\left({{n}\over{2^{\log{n}}}}\right)+\left(2^{\log{n}}-1\right)\cdot c\cdot n\cr -T(n)&=2^{\log{n}}\cdot 2^{\log{n}}\cdot T\left({{n}\over{2^{\log{n}}}}\right)+\left(2^{\log{n}}-1\right)\cdot c\cdot n\cr -T(n)&=n\cdot n\cdot T\left({{n}\over{n}}\right)+(n-1)\cdot c\cdot n\cr -T(n)&=n^{2}\cdot T(1)+(n-1)\cdot n\cdot c\cr -T(n)&=n^{2}\cdot T(1)+(n^{2}-n) \cdot c\cr -T(n)&=n^{2}\cdot T(1)+n^{2} \cdot c-n \cdot c\cr -T(n)&=n^{2}\cdot (T(1)+c)-c \cdot n\cr -} -$$ -Pokud $T(1)$ a $c$ jsou konstanty, mù¾eme psát: $T(n)=\O(n^{2})$. Tak¾e jsme si pøíli¹ nepomohli, proto¾e i klasický algoritmus na násobení má kvadratickou èasovou slo¾itost. Podívejme se v¹ak, jak vypadá tabulka vìtvení pro daný algoritmus: -$$\vbox{\halign{# \quad \quad & # \quad \quad & #\cr -poèet vìtvení & poèet úloh & velikost podúlohy\cr +kde $1/\log_c{k}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$.} + +\s{Pøíklad:} Eukleidùv algoritmus: +Pokud jej pustíme na $2$ èísla o $n$ bitech, poèet iterací bude $\O(n)$, ka¾dá +iterace trvá $\O(n^{2})$ krokù. Tak¾e celkovì má tento algoritmus èasovou +slo¾itost $\O(n^{3})$. + +\h{Metoda Rozdìl a panuj} + +Nyní pøestaòme chodit kolem horké ka¹e a øekòeme si, co to ono vý¹e zmiòované +\uv {rozdìl a panuj} znamená. Mìjme nìjaký problém, který má tu vlastnost, ¾e +kdy¾ jej rozdìlíme na nìjaké podproblémy, které mají stejný charakter, a ty +vyøe¹íme, slo¾ením jejich øe¹ení mù¾eme získat øe¹ení pùvodního problému. +Algoritmus tedy bude rekurzivnì volat sám sebe, ne¾ se dostane k~podproblému +nìjaké konstantní velikosti, který u¾ umí vyøe¹it triviálnì, a pak se zaène +z~rekurze vracet a skládat jednotlivá dílèí øe¹ení. + +\s{Pøíklad 1 -- MergeSort:} Algoritmus {\I MergeSort} pro tøídìní posloupnosti vypadá takto: +vstup rozdìlíme na~dvì (skoro) stejné èásti, ty rekurzivním voláním setøídíme, +a~nakonec výsledné dvì posloupnosti slijeme do~jedné. Rozdìlování a slévání nám +trvá lineárnì dlouho, tak¾e pro èasovou slo¾itost MergeSortu platí tato +rekurentní rovnice: $$T(n)=2 \cdot T({{n}/{2}})+\O(n).$$ Jak ji vyøe¹íme? Tøeba +tak, ¾e si pøedstavíme strom rekurzivních volání. Ka¾dý vrchol má dva syny +(dìlíme vstup na~dvì èásti), v~nich¾ jsou vstupy polovièní velikosti. V~ka¾dém +vrcholu trávíme èas lineární s~velikostí jeho vstupu, souèet velikostí vstupù +pøes ka¾dou hladinu je~$n$ a hloubka stromu musí být $\O(\log n)$. Vyjde nám +tedy, ¾e $T(n)=\O(n\log n)$. + +\s{Pøiklad 2 -- násobení èísel:} Pokud násobíme dvì èísla $X$ a $Y$ zpùsobem, +který nás uèili na základní ¹kole, dostaneme se na èasovou slo¾itost $\Theta(n^2)$. +Proto¾e se jedná o~dost èastou operaci, zamysleme se, jestli by ne¹la zrychlit. +Nasmìrujme na¹e úvahy na postup \uv{rozdìl a panuj}. Rozdìlíme ka¾dého èinitele +na dvì stejnì dlouhé èásti a pro jednoduchost pøedpokládejme, ¾e toto +roz¹tìpení èinitele probìhne v¾dy bez zbytku: +$$ +X=A \cdot 10^{{n}/2}+B, \qquad Y=C \cdot10^{{n}/{2}}+D. +$$ +Zde $A, B, C, D$ jsou u¾ jen $n/2$-ciferná èísla. Pùvodní souèin získáme jako: +$$ +XY=(A\cdot 10^{{n}/{2}}+B) (C\cdot 10^{{n}/{2}}+D)=AC \cdot 10^{n}+(AD+BC)\cdot 10^{{n}/{2}}+BD. +$$ +Nyní, jak vidíme, staèí spoèítat souèin ètyø $n/2$-ciferných èísel. Uva¾me, +jakou bude mít tento algoritmus èasovou slo¾itost: +$$T(n) = 4T(n/2)+\Theta(n).$$ +Jak takovou rekurenci vyøe¹íme? + +\>{\sl 1. zpùsob: Øe¹ení pomocí rozepisování:} +$$\eqalign{ +T(n)&= 4T(n/2)+\Theta(n) = \cr + &= 4T(n/2)+cn = \cr + &= 4\cdot (4T(n/4)+cn/2)+cn = 4^2T(n/4)+2cn+cn = 4^2T(n/4)+3cn = \cr + &= 4^2\cdot (2T(n/8)+cn/4)+3cn = 4^3T(n/8)+4cn+3cn = 4^3T(n/8)+7cn = \cr + &\ldots\cr +}$$ +Odtud snadno vypozorujeme, ¾e jednotlivé vztahy se vyvíjí podle vzorce +$T(n)=4^kT(n/2^k) + (2^k-1)cn.$ Pro $k=\lceil\log_2 n\rceil$ je ov¹em +$2^k\le 1$, tak¾e $T(n/2^k)=\Theta(1)$ a dostaneme (horní celou èást zanedbáme, +ta ovlivní jen konstanty): +$$ +T(n) = 4^{\log_2 n}\Theta(1) + (2^{\log_2 n}-1)cn = n^2\Theta(1) + (n-1)cn = \Theta(n^2). +$$ + +\>{\sl 2. zpùsob: Úvaha o~stromu:} Nakreslíme si strom rekurzivních volání +na¹eho algoritmu: +\fig{figure.eps}{4in} +Na~$i$-té hladinì stromu máme $4^i$ vrcholù, v~nich jsou vstupy velikosti +$n/2^i$, tak¾e na~celé hladinì trávíme èas celkem $\Theta(4^i\cdot n/2^i) += \Theta(2^in)$. Velikosti vstupù klesají exponenciálnì, tak¾e celý strom +je hluboký $k=\log_2 n$ (opìt si dovolíme zapomenout na~horní celou èást). +Celkem tedy trávíme èas $\sum_{i=0}^k \Theta(2^in) = \Theta(n\cdot\sum_{i=0}^k 2^i) = \Theta(n^2)$. + +Oba zpùsoby analýzy se tedy shodují, ¾e ná¹ algoritmus má kvadratickou èasovou +slo¾itost a ¾e jsme si oproti klasickému algoritmu nikterak nepomohli. +Podívejme se je¹tì jednou na~to, jak se ná¹ algoritmus vìtví: +$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad &\hfil#\hfil\cr +hloubka & poèet úloh & velikost podúlohy\cr \noalign{\smallskip\hrule\medskip} 0 & $4^{0}$ & ${n}/{2^{0}}$\cr 1 & $4^{1}$ & ${n}/{2^{1}}$\cr @@ -171,38 +163,32 @@ po 3 & $4^{3}$ & ${n}/{2^{3}}$\cr \vdots & \vdots & \vdots\cr $k$ & $4^{k}$ & ${n}/{2^{k}}$\cr}}$$ - -\medskip - -\noindent -Naskýtá se otázka, jestli bychom nemohli, èasovou slo¾itost zlep¹it. Existuje nìkolik mo¾ností: - -\itemize\ibull -\:zlep¹it èlen $c \cdot n$, to znamená zlep¹it èas spojování podúloh. Toto v¹ak rychleji nejde (pokud ètenáø nevìøí, mù¾e si to dokázat). -\:sní¾it poèet vìtvení. Nech» se tedy algoritmus nevìtví na $4$ vìtve, ale na ménì. To, ale jak dále uvidíme, u¾ mo¾né je. -\endlist - -\noindent -Staèí si uvìdomit, ¾e vlastnì potøebujeme spoèítat: -$$ -X\cdot Y=A\cdot C\cdot 10^{n}+(A\cdot D+B\cdot C)\cdot 10^{{n}\over{2}}+B\cdot D -$$ -Pøitom ale nepotøebujeme znát souèiny $A\cdot D$ ani $B\cdot C$ samostatnì, nebo» nám staèí zjistit èlen $A\cdot D+B\cdot C$. Kdybychom poèítali $A\cdot C$, $B\cdot D$ a potom $(A+B)\cdot (C+D)=A\cdot C+A\cdot D+B\cdot C+B\cdot D$, tak odèítáním $(A\cdot C+B\cdot D)$ od $A\cdot C+A\cdot D+B\cdot C+B\cdot D$ dostaneme hledaný prostøední èlen: $A\cdot D+B\cdot C$. Nyní nám ji¾ staèí jen tøi násobení, ale potøebujeme tøi sèítání a jedno odèítání navíc. Otázka je, zda-li to bude výhodné. Sèítání i~odèítání nám zaberou nanejvý¹e lineární èas, tak¾e to skuteènì je výhodná úprava. Jak se tím zmìní výsledný èas? Podívejme se opìt na tabulku vìtvení: - -$$\vbox{\halign{# \quad \quad & # \quad \quad & #\cr -poèet vìtvení & poèet úloh & velikost podúlohy\cr +Naskýtá se otázka, jestli bychom nemohli èasovou slo¾itost zlep¹it. Toho bychom +mohli dosáhnout buïto zlep¹ením èlenu $cn$ v~na¹í rekurenci, èili zefektivnìním +spojování podúloh. To ov¹em není pøíli¹ nadìjné (pokud ètenáø nevìøí, mù¾e si to dokázat), +tak¾e místo toho vyu¾ijeme druhou ¹anci, a~to omezení vìtvení ze~ètyø vìtví na~tøi. +Pøipomeòme si, ¾e potøebujeme spoèítat: +$$ +XY=AC\cdot 10^{n}+(AD+BC)\cdot 10^{n/2}+BD. +$$ +Pøitom ale nepotøebujeme znát souèiny $AD$ ani $BC$ samostatnì, nebo» nám staèí +zjistit celý èlen $AD+BC$. Kdybychom poèítali $AC$, $BD$ +a potom $(A+B)(C+D)=AC+AD+BC+BD$, tak odèítáním $(AC+BD)$ od $AC+AD+BC+BD$ dostaneme +hledaný prostøední èlen $AD+BC$. Nyní nám ji¾ staèí jen tøi +násobení, ale potøebujeme tøi sèítání a jedno odèítání navíc. +Uká¾eme, ¾e tato komplikace je zanedbatelná oproti práci u¹etøené +men¹ím vìtvením. Podívejme se opìt na~tabulku: +$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad &\hfil#\hfil\cr +hloubka & poèet úloh & velikost podúlohy\cr \noalign{\smallskip\hrule\medskip} 0 & $3^{0}$ & ${n}/{2^{0}}$\cr 1 & $3^{1}$ & ${n}/{2^{1}}$\cr 2& $3^{2}$ & ${n}/{2^{2}}$\cr 3 & $3^{3}$ & ${n}/{2^{3}}$\cr \vdots & \vdots & \vdots\cr -k & $3^{k}$ & ${n}/{2^{k}}$\cr}}$$ - -\medskip - -\noindent -Spoèítejme si práci, která se musí udìlat na jedné hladinì. Pøedpokládejme, ¾e $k= \lceil \log_2{n} \rceil$. Dostávame: +$k$ & $3^{k}$ & ${n}/{2^{k}}$\cr}}$$ +Opìt uva¾me, kolik práce spotøebujeme v~souètu pøes v¹echny hladiny (hloubka stromu +$k$ je opìt $\lceil\log_2 n\rceil$ a horní celou èást zanedbáme): $$\sum_{i=0}^{k}3^{i}\cdot {{n}\over{2^{i}}}=\sum_{i=0}^{k} \left( {{3}\over{2}} \right) ^{i}\cdot n=n\cdot \sum_{i=0}^{k} \left( {{3}\over{2}} \right) ^{i}=n\cdot {{ \left( {{3}\over{2}} \right) ^{k+1}-1}\over{{{3}\over{2}}-1}}= $$ $$ @@ -212,16 +198,27 @@ $$ =\O \left( n\cdot {{3^{\log_2{n}}}\over{2^{\log_2{n}}}} \right)=\O \left( n\cdot {{3^{\log_2{n}}}\over{n}} \right)=\O \left( 3^{\log_2{n}} \right)=\O \left( (2^{\log_2{3}})^{\log_2{n}} \right)= $$ $$ -=\O \left( 2^{(\log_2{n}) \cdot \log_2{3}} \right)=\O \left( (2^{\log_2{n}})^{\log_2{3}} \right)=\O \left( n^{\log_2{3}} \right) =\O \left( n^{1{,}585} \right). +=\O \left( 2^{(\log_2{n}) \cdot \log_2{3}} \right)=\O \left( (2^{\log_2{n}})^{\log_2{3}} \right)=\O \left( n^{\log_2{3}} \right) =\O \left( n^{1.585} \right). $$ -Z toho vyplývá, ¾e jsme na¹li algoritmus s èasovou slo¾itostí men¹í ne¾ $\O(n^{2})$. \uv{Rozumné} implementace tohoto algoritmu jsou v¹ak trochu modifikované. A to tak, ¾e rekuzivnì ne¹tìpí èinitele a¾ na jednociferná èísla, ale konèí asi na 50 ciferných, a ty se u¾ vynásobí standardním zpùsobem, nebo» re¾ie rekurzivního algoritmu není nulová a~takto se dosahuje nejlep¹ích výsledkù. +Upravený algoritmus u¾ tedy má lep¹í èasovou slo¾itost, konkrétnì $\O(n^{1.585})$. +V~praxi bychom samozøejmì pro èinitele ne¹tìpili a¾ na jednociferná èísla, +ale zastavili se u~nìjaké dostateènì malé délky (øeknìme 50~cifer) a tam +pøepnuli na~kvadratický algoritmus, který má men¹í re¾ii. -\noindent -Pro násobení èísel existuje je¹tì efektívnìj¹í algoritmus, který má èasovou slo¾itost $\O(n \cdot \log{n})$, av¹ak tento u¾ vyu¾ívá rùzné pokroèilé techniky jako diskrétní Fourierova transformace a podobnì, tak¾e jej zde nebudeme rozebírat. +(Mimochodem, pro násobení èísel existuje je¹tì efektívnìj¹í algoritmus, který +dosahuje èasové slo¾itosti $\O(n \log{n})$, av¹ak na~to u¾ jsou potøeba trochu +pokroèilej¹í techniky, jako je diskrétní Fourierova transformace, tak¾e +si jej necháme na~pøí¹tí semestr.) -Na¹e pozorování se nyní pokusíme shrnout ve vìtì Master Theorem, èesky tì¾ nazývané (ne náhodou) \uv{Kuchaøková vìta}: +\h{Master Theorem} -\s{Vìta:} \>{\sl (Master Theorem)} Pøedpokládejme, ¾e $T(1) \in \O(1)$ a $T(n)=a\cdot T(\lceil {{n}\over{b}} \rceil)+\O(n^d)$, kde $a \geq 1$, $b>1$ a $d \geq 0$. Potom $T(n)$ je: +Metody øe¹ení rekurentních rovnic pro slo¾itosti rozdìlovacích a panovacích algoritmù +by asi fungovaly i na~jiné algoritmy ne¾ jen na¹e dva pøíklady, ale proè se poka¾dé +moøit upravováním výrazù? Radìji si doká¾eme obecnou vìtu, která pùjde na~vìt¹inu +takových rekurencí nasadit. Øíká se jí Master Theorem nebo také (vzhledem k~tomu, +jak se pou¾ívá) Kuchaøková vìta. + +\s{Vìta:} \>{\sl (Master Theorem)} Pøedpokládejme, ¾e $T(1)=\O(1)$ a $T(n)=a\cdot T(\lceil {{n}\over{b}} \rceil)+\O(n^d)$, kde $a \geq 1$, $b>1$ a $d \geq 0$. Potom $T(n)$ je: \smallskip @@ -230,58 +227,61 @@ Na & $\O(n^d\cdot \log{n})$ & kdy¾ $a=b^d$,\cr & $\O(n^{\log_b{a}})$ & kdy¾ $a>b^d$.\cr} -\proof \>{\sl 1. pøípad: }Pøedpokládejme nejdøíve, ¾e $n=b^m, m \in \bb{N}$, aby platilo $\lceil {{n}\over{b}} \rceil = {{n}\over{b}}$. Uká¾eme si \uv{dùkaz stromem}: - -\figure{figure.eps}{}{4in} - -\noindent -Jak vidíme, strom sa v¾dy vìtví na stejný poèet vìtví - oznaème si jejich poèet $a$ a sestavme si tabulku vìtvení: - -$$\vbox{\halign{# \quad \quad & # \quad \quad & #\cr -poèet vìtvení & velikost podúlohy & èas potøebný na vyøe¹ení v¹ech podúloh\cr -\noalign{\medskip\hrule\bigskip} -$1$ & $n$ & $\O(n^d)$\cr -$a$ & $n/{b^1}$ & ${\O(({n/{b^1}})^d) \cdot a^1}$\cr -$a^2$ & $n/{b^2}$ & ${\O(({n/{b^2}})^d) \cdot a^2}$\cr -$a^3$ & $n/{b^3}$ & ${\O(({n/{b^3}})^d) \cdot a^3}$\cr +\proof Pøedpokládejme nejdøíve, ¾e $n=b^m, m \in \bb{N}$, aby platilo $\lceil +{{n}\over{b}} \rceil = {{n}\over{b}}$. Pou¾ijeme opìt \uv{dùkaz stromem}. +Strom rekurzivních volání se v¾dy vìtví na stejný poèet vìtví, konkrétnì~$a$, +a~velikosti vstupù klesají $b$-krát. Podívejme se na~tabulku: +$$\vbox{\halign{\hfil#\hfil \quad & \hfil#\hfil \quad & \hfil#\hfil & \hfil#\hfil \cr +hloubka & poèet podúloh & velikost podúlohy & èas na hladinì \cr +\noalign{\medskip\hrule\medskip} +0 & $1$ & $n$ & $\O(n^d)$\cr +1 & $a$ & $n/{b^1}$ & ${\O(({n/{b^1}})^d) \cdot a^1}$\cr +2 & $a^2$ & $n/{b^2}$ & ${\O(({n/{b^2}})^d) \cdot a^2}$\cr +3 & $a^3$ & $n/{b^3}$ & ${\O(({n/{b^3}})^d) \cdot a^3}$\cr \vdots & \vdots & \vdots\cr -$a^k$ & $n/{b^k}$ & ${\O(({n/{b^k}})^d) \cdot a^k}$\cr}}$$ +$k$ & $a^k$ & $n/{b^k}$ & ${\O(({n/{b^k}})^d) \cdot a^k}$\cr}}$$ \noindent Zkoumejme èas potøebný na vyøe¹ení v¹ech podúloh na jedné hladinì: $$ -\O \left( \left( {{n}\over{b^k}} \right) ^d \right) \cdot a^k=\O \left( a^k\cdot n^d \left( {{1}\over{b^k}} \right) ^d \right)=\O \left( a^k \cdot n^d \left( {{1}\over{b^d}} \right) ^k \right)=\O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right) +\O \left( \left( {{n}\over{b^k}} \right) ^d \right) \cdot a^k=\O \left( a^k\cdot n^d \left( {{1}\over{b^k}} \right) ^d \right)=\O \left( a^k \cdot n^d \left( {{1}\over{b^d}} \right) ^k \right)=\O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right). $$ -Celkem je tedy èas potøebný na vyøe¹ení v¹ech podúloh na v¹ech hladinách (to znamená celé úlohy): +Celkem je tedy èas potøebný na vyøe¹ení v¹ech podúloh na v¹ech hladinách (to +znamená celé úlohy): $$ T(n)=\sum_{k=0}^{\log_b{n}}\O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right)=\O \left( n^d \sum_{k=0}^{\log_b{n}} \left( {{a}\over{b^d}} \right) ^k \right) $$ V¹imnìme si èlenu ${a}\over{b^d}$. Na jeho hodnotì závisí hodnota výsledné sumy, proto¾e se vlastnì jedná o kvocient geometrické øady. Proto rozli¹me následující pøípady: -\>{\I 1.} ${{a}\over{b^d}}<1$ --- jinými slovy, práce na jednotlivých hladinách exponenciálnì ubývá a souèet sumy se dá omezit nìjakou konstantou, která se schová do $\O$, a tak mù¾eme psát $T(n) \in \O(n^d)$. - -\>{\I 2.} ${{a}\over{b^d}}=1$ --- práce na jednotlivých hladinách je stejnì, to znamená, ¾e ¾e souèet sumy je právì $\log_b(n)$ a tedy: $T(n) \in \O(n^d \cdot \log_b(n))$. +\>{\I 1.} ${{a}\over{b^d}}<1$ -- jinými slovy, práce na jednotlivých hladinách exponenciálnì ubývá a souèet sumy, i kdyby +byla nekoneèná, se dá omezit nìjakou konstantou, která se schová do $\O$, a tak je $T(n)=\O(n^d)$. -\>{\I 3.} ${{a}\over{b^d}}>1$ --- to znamená, ¾e práce na jednotlivých hladinách pøibývá, a potom musíme psát: $T(n) \in \O(n^d \cdot ({{a}\over{b^d}})^{\log_b{n}})$. +\>{\I 2.} ${{a}\over{b^d}}=1$ -- práce na jednotlivých hladinách je stejnì, to znamená, ¾e souèet sumy je právì $\log_b n$, a tedy $T(n) = \O(n^d \cdot \log_b(n))$. -\noindent -To sice vypadá jako slo¾itý výraz, ale mù¾eme jej dále upravit: +\>{\I 3.} ${{a}\over{b^d}}>1$ -- to znamená, ¾e práce na jednotlivých hladinách +pøibývá, tak¾e musíme geometrickou øadu seèíst poctivì: $T(n) = \O(n^d \cdot +({{a}\over{b^d}})^{\log_b{n}})$. Tento výraz vypadá ponìkud o¹klivì, +ale je¹tì ho trochu (alespoò kosmeticky) upravíme: $$ -\O\left(n^d \cdot \left({{a}\over{b^d}}\right)^{\log_b{n}}\right)=\O\left(n^d \cdot a^{\log_b{n}} \cdot \left({{1}\over{b^d}}\right)^{\log_b{n}}\right)=\O\left({\left(b^{\log_b{a}}\right)^{\log_b{n}} \cdot n^d \over{\left(b^d\right)^{\log_b{n}}}}\right)= +\O\left(n^d \cdot \left({{a}\over{b^d}}\right)^{\log_b{n}}\right)=\O\left({ a^{\log_b{n}} \cdot n^d \over (b^d)^{\log_b{n}}}\right)=\O\left({\left(b^{\log_b{a}}\right)^{\log_b{n}} \cdot n^d \over{\left(b^d\right)^{\log_b{n}}}}\right)= $$ $$ =\O\left({\left(b^{\log_b{n}}\right)^{\log_b{a}} \cdot n^d \over{\left(b^{\log_b{n}}\right)^d}}\right) =\O\left({n^{\log_b{a}} \cdot n^d \over{n^d}}\right) =\O\left(n^{\log_b{a}}\right). $$ -Nyní vidíme, ¾e vìta v tomto pøípadì platí a ¾e rozdìlení pøípadù je naprosto oprávnìné. +Tyto tøi pøípady pøesnì odpovídají rozdìlení pøípadu v~tvrzení vìty. -\>{\sl 2. pøípad: }Vra»me se k mo¾nosti $n \neq b^m, m \in \bb{N}$. Potom ale platí: $b^l{\sl Master Theoremu}: - $$\vbox{\halign{# \quad \quad & # \quad \quad & # \quad \quad & # \quad \quad & #\cr algoritmus & $a$ & $b$ & $d$ & èasová slo¾itost\cr \noalign{\smallskip\hrule\medskip} @@ -290,8 +290,6 @@ N Násobení II. & 3 & 2 & 1 & $\O(n^{\log_2{3}})$\cr Binární vyhledávání & 1 & 2 & 0 & $\O(\log{n})$\cr}}$$ -\medskip - \s{Domácí úkol nakonec:} Vymyslete algoritmus, který by z $n$ zadaných bodù v rovinì (prostoru) na¹el takové dva, které~jsou od sebe nejménì vzdálené (zde existuje takový algoritmus s èasovou slo¾itostí $\O(n \cdot \log{n})$). \bye -- 2.39.2