Zjednodusil jsem analyzu algoritmu pro nasobeni a ukazal na ni obe

[ads1.git] / 2-rozdel / 2-rozdel.tex

\input ../lecnotes.tex

\prednaska{2}{Rozdìl a panuj}{(zapsali J. Záloha a P. Ba¹ista)}

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)}.

\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: \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 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})$.

\>Také platí:
$$
\O(f)+\O(g) \in \O(f+g),
$$
èím¾ myslíme, ¾e pokud vezmeme libovolnou $f'=O(f)$ a $g'=O(g)$, bude $f'+g'=O(f+g)$.
To platí, jeliko¾ skoro v¹ude je $f' \leq cf$, $g'\leq dg$, a~tedy $f'+g' \le cf+dg \le (c+d)(f+g)$.

\s{Cvièení:} Uka¾te, ¾e:
\itemize\ibull
\:$\O(f) \cdot \O(g)=\O(f \cdot g)$,
\:$\O(f+g)=\O(\max(f,g))$,
\:$\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2})$.
\endlist

$\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) \equiv \exists c>0:\forall^* n \in {\bb N}: f(n) \geq c\cdot g(n)$.

$\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 výøeènìji:

$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

\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})$ \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})$
\:\dots\ nekoneènì mnoho dal¹ích tøíd (i mezi tìmi vý¹e uvedenými)
\endlist

\>{\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/\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
2 & $4^{2}$ & ${n}/{2^{2}}$\cr
3 & $4^{3}$ & ${n}/{2^{3}}$\cr
\vdots & \vdots & \vdots\cr
$k$ & $4^{k}$ & ${n}/{2^{k}}$\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}}$$
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}}=
$$
$$
=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) =
$$
$$
=\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).
$$
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.

(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.)

\h{Master Theorem}

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

\halign{#&#&#\cr
\indent & $\O(n^d)$ & kdy¾ $a<b^d$,\cr
& $\O(n^d\cdot \log{n})$ & kdy¾ $a=b^d$,\cr
& $\O(n^{\log_b{a}})$ & kdy¾ $a>b^d$.\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
$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).
$$
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, 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 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))$.

\>{\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({ 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).
$$
Tyto tøi pøípady pøesnì odpovídají rozdìlení pøípadu v~tvrzení vìty.

Vra»me se nyní k~mo¾nosti, kdy $n$ není mocnina~$b$.
Tehdy 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} < bn$. Jeliko¾ funkce
$T(n)$ je neklesající, dostaneme $T(n)\le T(n')$ a ve~v¹ech tøech pøípadech
je výsledek pro~$n'$ maximálnì konstanta-krát vìt¹í ne¾ pro~$n$, co¾ se
\uv{schová do~$\O$.} Vìta tedy platí i v~tomto pøípadì.
\qed

\s{Pøíklad:}
Porovnejme si nìkteré známé algoritmy a jejich èasovou slo¾itost pomocí \>{\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}
Mergesort & 2 & 2 & 1 & $\O({n \cdot \log{n}})$\cr
Násobení I. & 4 & 2 & 1 & $\O(n^2)$\cr
Násobení II. & 3 & 2 & 1 & $\O(n^{\log_2{3}})$\cr
Binární vyhledávání & 1 & 2 & 0 & $\O(\log{n})$\cr}}$$

\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