From ddd5d3cf07b0118fd56d94996cfbfba3702c3cb6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 14 May 2007 10:37:06 +0200 Subject: [PATCH] Vylepseni uvodniho povidani o O-ckach a take sazby. --- 2-rozdel/2-rozdel.tex | 168 ++++++++++++++++-------------------------- 1 file changed, 65 insertions(+), 103 deletions(-) diff --git a/2-rozdel/2-rozdel.tex b/2-rozdel/2-rozdel.tex index a01abbf..48021b3 100644 --- a/2-rozdel/2-rozdel.tex +++ b/2-rozdel/2-rozdel.tex @@ -2,84 +2,60 @@ \prednaska{2}{Rozdìl a panuj}{(zapsali J. Záloha a P. Ba¹ista)} -\s{O èem bude dne¹ní pøedná¹ka?} Pøevá¾nì o metodì Rozdìl a panuj (\>{\sl Divide et Impera}). +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)}. -\noindent -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. - -\s{Definice:} Pøedpokládejme, ¾e funkce, které porovnávame jsou dle následujícího pøedpisu: - -$f:M \rightarrow \bb{R}^{+}$, kde $M \subset \bb{N}$. - -\noindent -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)$. - -\>{\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: - -$2{,}5n^{2} \in \O(n^{2})$ +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. -$2{,}5n^{2}+30n \in \O(n^{2})$. +\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)$. +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.} -\noindent -Pro dvì tøídy funkcí $\O(f)$ a $\O(g)$ platí: +\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ì +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. -$$ -\O(f)+\O(g) \in \O(f+g) -$$ +\s{Pøíklady:} $2{,}5n^{2} = \O(n^{2})$, $2{,}5n^{2}+30n = \O(n^{2})$. -\noindent -proto¾e pro v¹echny funkce $f^{\prime} \in \O(f)$ a $g^{\prime} \in \O(g)$ platí: +\>Také platí: $$ -\eqalign{ -f^{\prime} &\leq c\cdot f \cr -g^{\prime} &\leq d\cdot g \cr -f^{\prime}+g^{\prime} \leq c\cdot f+d\cdot g &\leq (c+d)\cdot (f+g) -} +\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 -\noindent -A zde vidíme, ¾e $(c+d)$ se schová do $\O$. Naprosto stejnì se uká¾e obdobný vztah pro násobení: - -$$ -\O(f) \cdot \O(g)=\O(f \cdot g) -$$ - -\noindent -Rovnì¾ platí: - -$$ -\O(f+g)=\O(\max(f,g)) -$$ - -\noindent -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$. -To nám umo¾nuje zanedbávat pomaleji rostoucí èleny: - -$$ -\O(n^{2})+\O(n)=\O(n^{2}+n)=\O(n^{2}) -$$ - -\noindent -$\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í 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: \s{Definice:} \itemize\ibull -\:$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)$ +\:$f=\Omega(g) \Longleftrightarrow \exists$ $c>0:$ $\exists$ $g(n): \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 \in \O(f)$. -\:$f(n) \in \Theta(g(n)) \Longleftrightarrow f(n) \in O(g(n)) \wedge f(n) \in \Omega(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)$ nebo: -$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)$. +$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)$. \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ì. +$\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) +\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 @@ -115,9 +91,9 @@ $\vdots$ \>{\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í: $$ -\log_k{n}={{\log_c{n}}\over{\log_c{k}}}={{1}\over{\log_c{k}}}\cdot \log_c{n} +\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 zanedbat. +kde ${1}\over{\log_c{k}}$ je jen konstanta, tak¾e ji mù¾eme \uv{schovat do~$\O$.} \>{\sl Pøíklady:} @@ -160,20 +136,18 @@ $T(n)=4\cdot T({{n}/{2}})+O(n)=4\cdot T({{n}/{2}})+c\cdot n=4\cdot (4\cdot T({{n takto bychom mohli pokraèovat dále, a¾ bychom se dostali na: $$ -T(n)=4^{4}\cdot T\left({{n}\over{16}}\right)+15\cdot c\cdot n -$$ -$$ -T(n)=4^{5}\cdot T\left({{n}\over{32}}\right)+31\cdot c\cdot n -$$ -$$ -\vdots +\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 +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: $$ @@ -187,19 +161,16 @@ 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) \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: - -\medskip - -\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\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 -\noalign{\medskip\hrule\bigskip} +\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}} +$k$ & $4^{k}$ & ${n}/{2^{k}}$\cr}}$$ \medskip @@ -218,17 +189,15 @@ 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í: -\medskip - -\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr +$$\vbox{\halign{# \quad \quad & # \quad \quad & #\cr poèet vìtvení & poèet úloh & velikost podúlohy\cr -\noalign{\medskip\hrule\bigskip} +\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}} +k & $3^{k}$ & ${n}/{2^{k}}$\cr}}$$ \medskip @@ -243,7 +212,7 @@ $$ =\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ù. @@ -257,9 +226,9 @@ Na \smallskip \halign{#&#&#\cr -\indent & $\O(n^d)$ & kdy¾ $ab^d$\cr} +\indent & $\O(n^d)$ & kdy¾ $ab^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}: @@ -268,19 +237,15 @@ Na \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í: -\medskip - -\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & #\cr +$$\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}\over{b^1}$ & ${\O(({{n}\over{b^1}})^d) \cdot a^1}$\cr -$a^2$ & ${n}\over{b^2}$ & ${\O(({{n}\over{b^2}})^d) \cdot a^2}$\cr -$a^3$ & ${n}\over{b^3}$ & ${\O(({{n}\over{b^3}})^d) \cdot a^3}$\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 \vdots & \vdots & \vdots\cr -$a^k$ & ${n}\over{b^k}$ & ${\O(({{n}\over{b^k}})^d) \cdot a^k}$\cr}} - -\medskip +$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ì: @@ -301,16 +266,15 @@ V \noindent To sice vypadá jako slo¾itý výraz, ale mù¾eme jej dále upravit: - $$ -\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 \cdot {{1}\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(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(\left(b^{\log_b{n}}\right)^{\log_b{a}} \cdot n^d \cdot {{1}\over{\left(b^{\log_b{n}}\right)^d}}\right)=\O\left(n^{\log_b{a}} \cdot n^d \cdot {{1}\over{n^d}}\right)=\O\left(n^{\log_b{a}}\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). $$ - -\noindent -A nyní vidíme, ¾e vìta v tomto pøípadì platí a ¾e rozdìlení pøípadù je naprosto oprávnìné. +Nyní vidíme, ¾e vìta v tomto pøípadì platí a ¾e rozdìlení pøípadù je naprosto oprávnìné. \>{\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}: -\medskip - -\vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr +$$\vbox{\halign{# \quad \quad & # \quad \quad & # \quad \quad & # \quad \quad & #\cr algoritmus & $a$ & $b$ & $d$ & èasová slo¾itost\cr -\noalign{\medskip\hrule\bigskip} +\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}} +Binární vyhledávání & 1 & 2 & 0 & $\O(\log{n})$\cr}}$$ \medskip -- 2.39.2