Master theorem

Šablona:Upravit Master theorem (také Kuchařková věta nebo Mistrovská metoda) 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)=aT\left(\frac{n}{b}\right)+f(n)$, kde $a\ge 1\text{, }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.
• $\frac{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)=𝒪\left(n^{{\log }_b\left(a\right)-ϵ}\right)$ pro nějaké $ϵ>0$

tak:

$T(n)=\mathrm{\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)=𝒪\left(n^{{\log }_{b}a-ϵ}\right)$

Po dosazení hodnot dostaneme:

$1000n^2=𝒪\left(n^{3-ϵ}\right)$

Pokud zvolíme $ϵ$ = 1, dostaneme:

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

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

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

Po dosazení hodnot:

$T(n)=\mathrm{\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í:

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

tak:

$T(n)=\mathrm{\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$

Po dosazení dostaneme:

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

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

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

Po dosazení:

$T(n)=\mathrm{\Theta }(n\log n).$

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)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$ pro nějaké $ϵ>0$

a také platí:

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

tak:

$T\left(n\right)=\mathrm{\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)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$

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

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

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

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

Opět dosadíme hodnoty:

$2{\left(\frac{n}{2}\right)}^2$$\le c{n}^2\iff \frac{1}{2}{n}^2\le c{n}^2$

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

$\frac{1}{2}{n}^2\le \frac{1}{2}{n}^2$ $\mathrm{\forall }n\ge 1$

Tedy:

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

Opět dosadíme hodnoty a dostaneme:

$T\left(n\right)=\mathrm{\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.

Odkazy

Literatura

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Šablona:ISBN. 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. Šablona:ISBN. 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.