3 \prednaska{2}{Rozdìl a panuj}{(zapsali J. Záloha a P. Ba¹ista)}
5 \s{O èem bude dne¹ní pøedná¹ka?} Pøevá¾nì o metodì Rozdìl a panuj (\>{\sl Divide et Impera}).
8 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.
10 \s{Definice:} Pøedpokládejme, ¾e funkce, které porovnávame jsou dle následujícího pøedpisu:
12 $f:M \rightarrow \bb{R}^{+}$, kde $M \subset \bb{N}$.
15 Potom øekneme, ¾e $f(n)$ je $\O(g(n))$ právì tehdy kdy¾: $\exists$ $c>0, c \in \bb{R}:$ $\forall ^{*} n \in \bb{N}:$ $f(n) \leq c \cdot g(n)$.
17 \>{\sl Poznámka:} $ \forall ^{*} n \in \bb{N}$ $\Longleftrightarrow \exists$ $n_{0} \in \bb{N}:$ $\forall n \geq n_{0}, n \in \bb{N}$. Tedy $ \forall ^{*} n \in \bb{N}$ znamená, ¾e výrok platí pro v¹echna $n \in \bb{N}$ a¾ na koneèný poèet vyjímek. $\O$ notace tedy vyjadøuje, ¾e funkce $f(n)$ je men¹í nejvý¹e rovná nìjakému reálnému násobku funkce $g(n)$ pro $\forall ^{*} n \in \bb{N}$. Tento fakt se zapisuje takto: $f(n)=\O(g(n))$. Zde se jedná o za¾itou vìc, ale~je nutné si uvìdomit, ¾e tento zápis neoznaèuje rovnost! Je to proto, ¾e napøíklad platí: $\log{n}=\O(n)$, ale neplatí $n=\O(\log{n})$. To znamená, ¾e neplatí symetrie, a tudí¾ nemù¾e jít o rovnost ve smyslu ekvivalnece. \uv{Je to èuòaèina.} Formálnì tuto skuteènost poipsujeme, ¾e jde o nìjakou mno¾inu nebo tøídu funkcí $f(n)$, pro které platí, ¾e se dají shora ohranièit kladným reálným násobkem funkce $g(n)$. A potom zapisujeme $f \in \O(g)$. Napøíklad:
19 $2{,}5n^{2} \in \O(n^{2})$
21 $2{,}5n^{2}+30n \in \O(n^{2})$.
24 Pro dvì tøídy funkcí $\O(f)$ a $\O(g)$ platí:
27 \O(f)+\O(g) \in \O(f+g)
31 proto¾e pro v¹echny funkce $f^{\prime} \in \O(f)$ a $g^{\prime} \in \O(g)$ platí:
34 f^{\prime} &\leq c\cdot f \cr
35 g^{\prime} &\leq d\cdot g \cr
36 f^{\prime}+g^{\prime} \leq c\cdot f+d\cdot g &\leq (c+d)\cdot (f+g)
42 A zde vidíme, ¾e $(c+d)$ se schová do $\O$. Naprosto stejnì se uká¾e obdobný vztah pro násobení:
56 nebo» libovolný kladný $c_1$-násobek funkce s exponentem $k$ je v¾dy asymptoticky men¹í ne¾ $c_2$-násobek funkce s~exponentem $l>k$.
57 To nám umo¾nuje zanedbávat pomaleji rostoucí èleny:
60 \O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})
64 $\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:
69 \:$f(n) \in \Omega(g(n)) \Longleftrightarrow \exists$ $c>0:$ $\exists$ $g(n): \forall ^{*} n \in {\bb N}: f(n) \geq c\cdot g(n)$
71 $\Omega$ notace øíká, ¾e hodnota funkce $f$ je v¾dy stejná nebo vy¹¹í ne¾ nìjaký $c$-násobek funkce $g$, a tedy $g \in \O(f)$.
72 \:$f(n) \in \Theta(g(n)) \Longleftrightarrow f(n) \in O(g(n)) \wedge f(n) \in \Omega(g(n))$
76 $f(n) \in \Theta(g(n)) \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)$.
80 $\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ì.
82 \s{Porovnání rùstu funkcí:} (aneb jak moc máme algoritmy rádi podle jejich chování od nejlep¹ích k nejhor¹ím)
85 \: $\Theta(1) \ldots$ funkce zespoda i shora ohranièené konstantami
86 \: $\Theta(\log{( \log{n} )})$
87 \: $\Theta(\log{n}) \ldots$logaritmická
88 \: $\Theta(n^{\varepsilon}), \varepsilon \in (0,1) \ldots$ sublineární
89 \: $\Theta(n) \ldots$ lineární
90 \: $\Theta(n^{2}) \ldots$ kvadratická
94 \: $\Theta(n^{k}), k \in {\bb N} \ldots$ polynomiální
98 \: $\Theta(2^{n}) \ldots$ exponenciální pøi základu $2$
99 \: $\Theta(3^{n}) \ldots$ exponenciální pøi základu $3$
103 \: $\Theta(k^{n}), k \in \bb{R}^{+},$ $k > 1 \ldots$ exponenciální pøi základu $k$
107 \: $\Theta(n!) \ldots$ faktoriálová
116 \>{\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í:
118 \log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n}
120 kde ${1}\over{\log_c{k}}$ je jen konstanta, tak¾e ji mù¾eme zanedbat.
124 \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})$.
126 \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.
128 \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)$.
131 Kdy¾ se v¹ak vynoøujeme z rekurze, musíme na ka¾dé hladinì strávit linárnì èasu sluèováním:
133 $T(n)=2 \cdot T({{n}/{2}})+\O(n)$.
136 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)$.
138 \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:
141 X=A \cdot 10^{{n}/2}+B
144 Y=C \cdot10^{{n}/{2}}+D
148 Zde $A, B, C, D$ jsou u¾ jen $n/2$ ciferná èísla. Potom získáme pùvodní souèin $X \cdot Y$ jako:
151 $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$
154 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:
157 $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$
160 takto bychom mohli pokraèovat dále, a¾ bychom se dostali na:
163 T(n)=4^{4}\cdot T\left({{n}\over{16}}\right)+15\cdot c\cdot n
166 T(n)=4^{5}\cdot T\left({{n}\over{32}}\right)+31\cdot c\cdot n
171 Odtud mù¾eme vypozorovat, ¾e se vztah pro $T(n)$ vyvíjí zøejmì podle vzorce:
173 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,
176 T(n)=4^{k}\cdot T\left({{n}\over{2^{k}}}\right)+(2^{k}-1)\cdot c\cdot n
178 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:
181 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
182 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
183 T(n)&=n\cdot n\cdot T\left({{n}\over{n}}\right)+(n-1)\cdot c\cdot n\cr
184 T(n)&=n^{2}\cdot T(1)+(n-1)\cdot n\cdot c\cr
185 T(n)&=n^{2}\cdot T(1)+(n^{2}-n) \cdot c\cr
186 T(n)&=n^{2}\cdot T(1)+n^{2} \cdot c-n \cdot c\cr
187 T(n)&=n^{2}\cdot (T(1)+c)-c \cdot n\cr
190 Pokud $T(1)$ a $c$ jsou konstanty, mù¾eme psát: $T(n) \in \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:
194 \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
195 poèet vìtvení & poèet úloh & velikost podúlohy\cr
196 \noalign{\medskip\hrule\bigskip}
197 0 & $4^{0}$ & ${n}/{2^{0}}$\cr
198 1 & $4^{1}$ & ${n}/{2^{1}}$\cr
199 2 & $4^{2}$ & ${n}/{2^{2}}$\cr
200 3 & $4^{3}$ & ${n}/{2^{3}}$\cr
201 \vdots & \vdots & \vdots\cr
202 k & $4^{k}$ & ${n}/{2^{k}}$\cr}}
207 Naskýtá se otázka, jestli bychom nemohli, èasovou slo¾itost zlep¹it. Existuje nìkolik mo¾ností:
210 \: 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).
211 \: 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.
215 Staèí si uvìdomit, ¾e vlastnì potøebujeme spoèítat:
217 X\cdot Y=A\cdot C\cdot 10^{n}+(A\cdot D+B\cdot C)\cdot 10^{{n}\over{2}}+B\cdot D
219 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í:
223 \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
224 poèet vìtvení & poèet úloh & velikost podúlohy\cr
225 \noalign{\medskip\hrule\bigskip}
226 0 & $3^{0}$ & ${n}/{2^{0}}$\cr
227 1 & $3^{1}$ & ${n}/{2^{1}}$\cr
228 2& $3^{2}$ & ${n}/{2^{2}}$\cr
229 3 & $3^{3}$ & ${n}/{2^{3}}$\cr
230 \vdots & \vdots & \vdots\cr
231 k & $3^{k}$ & ${n}/{2^{k}}$\cr}}
236 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:
237 $$\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}}=
240 =n\cdot {{ \left( {3}\over{2} \right) ^{k+1}-1}\over{{{1}\over{2}}}}=2\cdot n\cdot \left[ \left( {{3}\over{2}} \right) ^{k+1}-1 \right] = \O \left( n\cdot \left( {{3}\over{2}} \right) ^{\log_2{n}} \right) =
243 =\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)=
246 =\O \left( 2^{\log_2{n}.\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)
248 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ù.
251 Pro násobení èísel existuje je¹tì efektívnìj¹í algoritmus, který má èasovou slo¾itost $\O(n.\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.
253 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}:
255 \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:
260 \indent & $\O(n^d)$ & kdy¾ $a<b^d$\cr
261 & $\O(n^d\cdot \log{n})$ & kdy¾ $a=b^d$\cr
262 & $\O(n^{\log_a{b}})$ & kdy¾ $a>b^d$\cr}
264 \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}:
266 \figure{figure.eps}{}{4in}
269 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í:
273 \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr
274 poèet vìtvení & velikost podúlohy & èas potøebný na vyøe¹ení v¹ech podúloh\cr
275 \noalign{\medskip\hrule\bigskip}
276 $1$ & $n$ & $\O(n^d)$\cr
277 $a$ & ${n}\over{b^1}$ & $\O(({{n}\over{b^1}})^d).a^1$\cr
278 $a^2$ & ${n}\over{b^2}$ & $\O(({{n}\over{b^2}})^d).a^2$\cr
279 $a^3$ & ${n}\over{b^3}$ & $\O(({{n}\over{b^3}})^d).a^3$\cr
280 \vdots & \vdots & \vdots\cr
281 $a^k$ & ${n}\over{b^k}$ & $\O(({{n}\over{b^k}})^d).a^k$\cr}}
286 Zkoumejme èas potøebný na vyøe¹ení v¹ech podúloh na jedné hladinì:
288 \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.n^d \left( {{1}\over{b^d}} \right) ^k \right)=\O \left( n^d \left( {{a}\over{b^d}} \right) ^k \right)
290 Celkem je tedy èas potøebný na vyøe¹ení v¹ech podúloh na v¹ech hladinách (to znamená celé úlohy):
292 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)
294 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:
296 \>{\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)$.
298 \>{\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))$.
300 \>{\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.({{a}\over{b^d}})^{\log_b{n}})$.
303 To sice vypadá jako slo¾itý výraz, ale mù¾eme jej dále upravit:
306 \O\left(n^d.\left({{a}\over{b^d}}\right)^{\log_b{n}}\right)=\O\left(n^d.a^{\log_b{n}}\left({{1}\over{b^d}}\right)^{\log_b{n}}\right)=\O\left(\left(b^{\log_b{a}}\right)^{\log_b{n}}.n^d.{{1}\over{\left(b^d\right)^{\log_b{n}}}}\right)=
309 =\O\left(\left(b^{\log_b{n}}\right)^{\log_b{a}}.n^d.{{1}\over{\left(b^{\log_b{n}}\right)^d}}\right)=\O\left(n^{\log_b{a}}.n^d.{{1}\over{n^d}}\right)=\O\left(n^{\log_b{a}}\right)
313 A nyní vidíme, ¾e vìta v tomto pøípadì platí a ¾e rozdìlení pøípadù je naprosto oprávnìné.
315 \>{\sl 2. pøípad: }Vra»me se k mo¾nosti $n \neq b^m, m \in \bb{N}$. Potom ale platí: $b^l<n<b^{l+1}$ pro nìjaké $l \in \bb{N}$. V tomto pøípadì zaokrouhleme $n$ a~poèítejme s $n^{\prime}=b^{l+1}$. Potom platí $n^{\prime}=b^{l+1}=b\cdot b^l<b\cdot n$, a odtud je hned vidìt, ¾e $n^{\prime}<b\cdot n$, a odtud vyplývá, ¾e vstup se nám zvìt¹í pøinejhor¹ím $konstanta$-krát, co¾ je z asymtotického hlediska, které nás zajímá nejvíce, nedùle¾ité, a tak tuto konstantu \uv{schováme} do $\O$ a máme algoritmus stejné slo¾itosti. Vidíme tedy, ¾e vìta platí i v tomto pøípadì.
319 Porovnejme si nìkteré známé algoritmy a jejich èasovou slo¾itost pomocí \>{\sl Master Theoremu}:
323 \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr
324 algoritmus & $a$ & $b$ & $d$ & èasová slo¾itost\cr
325 \noalign{\medskip\hrule\bigskip}
326 Mergesort & 2 & 2 & 1 & $\O(n\log{n})$\cr
327 Násobení I. & 4 & 2 & 1 & $\O(n^2)$\cr
328 Násobení II. & 3 & 2 & 1 & $\O(n^{\log_2{3}})$\cr
329 Binární vyhledávání & 1 & 2 & 0 & $\O(\log{n})$\cr}}
333 \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})$).