Master theorem

Master theorem (často také Kuchařková věta nebo Mistrovská metoda), což je speciální případ Akra-Bazzi theoremu, poskytuje při analýze složitosti algoritmů kuchařkové řešení asymptotické složitosti pro často používané rekurentní vztahy. Byl popularizován knihou Introduction to Algorithms napsanou Cormenem, Leisersonem, Rivestem a Steinem, kde je uveden a dokázán v sekcích 4.3 a 4.4.

Obecná forma

Master theorem řeší rekurentní vztahy ve tvaru:

$T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)\;\;\;\;{\mbox{kde}}\;\;a\geq 1{\mbox{, }}b>1.$

Při analýze rekurzivních algoritmů mají konstanty a funkce následující význam:

• n je velikost problému.
• a je počet podproblémů v rekurzi.
• n/b je velikost každého z podproblémů. Předpokládá se, že podproblémy jsou víceméně stejně velké.
• f (n) je cena práce mimo rekurzivní volání, zahrnující rozdělení problému na podproblémy a sloučení výsledků podproblémů.

Je možné zjistit asymptotickou složitost v následujících třech případech:

Případ 1

Obecný tvar

Pokud platí, že $f(n)={\mathcal {O}}\left(n^{\log _{b}\left(a\right)-\epsilon }\right)$ pro nějaké $\epsilon >0$

tak:

$T(n)=\Theta \left(n^{\log _{b}a}\right).$

Příklad

$T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$

Z výše uvedené rovnice vidíme, že hodnoty jsou:

$a=8\,$, $b=2\,$, $f(n)=1000n^{2}\,$, $\log _{b}a=\log _{2}8=3\,$

Nyní musíme zkontrolovat, zda platí:

$f(n)={\mathcal {O}}\left(n^{\log _{b}a-\epsilon }\right)$

Po dosazení hodnot dostaneme:

$1000n^{2}={\mathcal {O}}\left(n^{3-\epsilon }\right)$

Pokud zvolíme $\epsilon$ = 1, dostaneme:

$1000n^{2}={\mathcal {O}}\left(n^{3-1}\right)={\mathcal {O}}\left(n^{2}\right)$

Protože rovnost platí, první případ master theoremu lze použít na danou rekurentní rovnost, čímž dostaneme:

$T(n)=\Theta \left(n^{\log _{b}a}\right).$

Po dosazení hodnot:

$T(n)=\Theta \left(n^{3}\right).$

Tedy pro daný rekurentní vztah T(n) je v Θ(n³).

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je $T(n)=1001n^{3}-1000n^{2}$, za předpokladu $T(1)=1$.)

Případ 2

Obecný tvar

Pokud platí:

$\exists k\geq 0,f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)$

tak:

$T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right).$

Příklad

$T(n)=2T\left({\frac {n}{2}}\right)+10n$

Z výše uvedené rovnice vidíme, že hodnoty jsou:

$a=2\,$, $b=2\,$, $k=0\,$, $f(n)=10n\,$, $\log _{b}a=\log _{2}2=1\,$

Nyní ověříme, že následující rovnost platí (v tomto případě k=0):

$f(n)=\Theta \left(n^{\log _{b}a}\right)$

Po dosazení dostaneme:

$10n=\Theta \left(n^{1}\right)=\Theta \left(n\right)$

Protože rovnost platí, druhý případ master theoremu lze aplikovat, čímž dostáváme:

$T(n)=\Theta \left(n^{\log _{b}a}\log n\right).$

Po dosazení:

$T(n)=\Theta \left(n\log n\right).$

Tedy pro daný rekurentní vztah T(n) je v Θ(n log n).

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je $T(n)=n+10n\log _{2}n$, za předpokladu $T(1)=1$.)

Případ 3

Obecný tvar

Pokud platí:

$f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)$ pro nějaké $\epsilon >0$

a také platí:

$af\left({\frac {n}{b}}\right)\leq cf(n)$ pro nějaké $c<1$ a dostatečně velké n

tak:

$T\left(n\right)=\Theta \left(f\left(n\right)\right).$

Příklad

$T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$

Z výše uvedené rovnice vidíme, že hodnoty jsou:

$a=2\,$, $b=2\,$, $f(n)=n^{2}\,$, $\log _{b}a=\log _{2}2=1\,$

Nyní ověříme, že následující rovnost platí:

$f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)$

Pokud dosadíme hodnoty a zvolíme $\epsilon$ = 1, dostaneme:

$n^{2}=\Omega \left(n^{1+1}\right)=\Omega \left(n^{2}\right)$

Protože rovnost platí, ověříme druhou podmínku, konkrétně, že:

$af\left({\frac {n}{b}}\right)\leq cf(n)$

Opět dosadíme hodnoty:

$2\left({\frac {n}{2}}\right)^{2}$$\leq cn^{2}\Leftrightarrow {\frac {1}{2}}n^{2}\leq cn^{2}$

Pokud zvolíme $c={\frac {1}{2}}$, tak platí:

${\frac {1}{2}}n^{2}\leq {\frac {1}{2}}n^{2}$ $\forall n\geq 1$

Tedy:

$T\left(n\right)=\Theta \left(f\left(n\right)\right).$

Opět dosadíme hodnoty a dostaneme:

$T\left(n\right)=\Theta \left(n^{2}\right).$

Tedy pro daný rekurentní vztah T(n) je v Θ(n²), což odpovídá f (n) v původním vzorci.

(Tento výsledek byl potvrzen přesným řešením rekurentního vztahu, které je $T(n)=2n^{2}-n$, za předpokladu $T(1)=1$.)

Nepřípustné rovnice

Následující rovnice nelze vyřešit pomocí master theoremu:

$T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$

To protože a (2ⁿ) není konstanta.

$T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$

Mezi f(n) a $n^{\log _{b}a}$ je nepolynomiální rozdíl.

$T(n)=0.5T\left({\frac {n}{2}}\right)+{\frac {1}{n}}$

Nelze mít méně, než jeden podproblém (a<1).

$T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$

f(n) není kladné.

$T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$

Případ 3, ale porušení regularity.

Reference

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sekce 4.3 (The master method) a 4.4 (Proof of the master theorem), pp.73–90.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. Master theorem (včetně verze případu 2 zde zmíněné, která je silnější než ta z CLRS) je na pp. 268–270.

V tomto článku byl použit překlad textu z článku Master theorem na anglické Wikipedii.