Master theorem

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:

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

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

• ${\displaystyle n}$ je velikost problému.
• ${\displaystyle a}$ je počet podproblémů v rekurzi.
• ${\displaystyle {\frac {n}{b}}}$ je velikost každého z podproblémů. Předpokládá se, že podproblémy jsou víceméně stejně velké.
• ${\displaystyle 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 ${\displaystyle f(n)={\mathcal {O}}\left(n^{\log _{b}\left(a\right)-\epsilon }\right)}$ pro nějaké ${\displaystyle \epsilon >0}$

tak:

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

Příklad

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

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

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

Nyní musíme zkontrolovat, zda platí:

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

Po dosazení hodnot dostaneme:

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

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

${\displaystyle 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:

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

Po dosazení hodnot:

${\displaystyle 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 ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$, za předpokladu ${\displaystyle T(1)=1}$.)

Případ 2

Obecný tvar

Pokud platí:

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

tak:

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

Příklad

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

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

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

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

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

Po dosazení dostaneme:

${\displaystyle 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:

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

Po dosazení:

${\displaystyle 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 ${\displaystyle T(n)=n+10n\log _{2}n}$, za předpokladu ${\displaystyle T(1)=1}$.)

Případ 3

Obecný tvar

Pokud platí:

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

a také platí:

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

tak:

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

Příklad

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

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

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

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

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

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

${\displaystyle 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:

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

Opět dosadíme hodnoty:

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

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

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

Tedy:

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

Opět dosadíme hodnoty a dostaneme:

${\displaystyle 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 ${\displaystyle T(n)=2n^{2}-n}$, za předpokladu ${\displaystyle T(1)=1}$.)

Nepřípustné rovnice

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

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

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

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

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

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

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

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

f(n) není kladné.

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

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

Odkazy

Reference

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

Literatura

• 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.

Zdroj