From 638c919eaecff186f9b461281bc4b24cc9834bb0 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 14 May 2007 10:06:05 +0200 Subject: [PATCH] Drobne upravy od autoru. --- 2-rozdel/2-rozdel.tex | 52 +++++++++++++++++++++---------------------- 1 file changed, 26 insertions(+), 26 deletions(-) diff --git a/2-rozdel/2-rozdel.tex b/2-rozdel/2-rozdel.tex index 57dcb60..a01abbf 100644 --- a/2-rozdel/2-rozdel.tex +++ b/2-rozdel/2-rozdel.tex @@ -42,7 +42,7 @@ $$ A zde vidíme, ¾e $(c+d)$ se schová do $\O$. Naprosto stejnì se uká¾e obdobný vztah pro násobení: $$ -\O(f).\O(g)=\O(f.g) +\O(f) \cdot \O(g)=\O(f \cdot g) $$ \noindent @@ -82,33 +82,33 @@ $\Theta$ notace tedy vyjad \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á +\:$\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í +\:$\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$ +\:$\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$ +\:$\Theta(k^{n}), k \in \bb{R}^{+},$ $k > 1 \ldots$ exponenciální pøi základu $k$ $\vdots$ -\: $\Theta(n!) \ldots$ faktoriálová +\:$\Theta(n!) \ldots$ faktoriálová $\vdots$ -\: $\Theta(n^{n})$ +\:$\Theta(n^{n})$ $\vdots$ \endlist @@ -207,8 +207,8 @@ k & $4^{k}$ & ${n}/{2^{k}}$\cr}} 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. +\: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 @@ -243,12 +243,12 @@ $$ =\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}.\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ù. \noindent -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. +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. 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}: @@ -274,18 +274,18 @@ Jak vid 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).a^1$\cr -$a^2$ & ${n}\over{b^2}$ & $\O(({{n}\over{b^2}})^d).a^2$\cr -$a^3$ & ${n}\over{b^3}$ & $\O(({{n}\over{b^3}})^d).a^3$\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 \vdots & \vdots & \vdots\cr -$a^k$ & ${n}\over{b^k}$ & $\O(({{n}\over{b^k}})^d).a^k$\cr}} +$a^k$ & ${n}\over{b^k}$ & ${\O(({{n}\over{b^k}})^d) \cdot a^k}$\cr}} \medskip \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.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): $$ @@ -297,16 +297,16 @@ V \>{\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 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}})$. +\>{\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}})$. \noindent To sice vypadá jako slo¾itý výraz, ale mù¾eme jej dále upravit: $$ -\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)= +\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(\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) +=\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) $$ \noindent @@ -323,7 +323,7 @@ Porovnejme si n \vbox{\halign{# \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & # \quad \vrule \quad & #\cr algoritmus & $a$ & $b$ & $d$ & èasová slo¾itost\cr \noalign{\medskip\hrule\bigskip} -Mergesort & 2 & 2 & 1 & $\O(n\log{n})$\cr +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}} -- 2.39.2