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:

:T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n), 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. +more * \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) = \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) = 8 T\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) = 1001 n^3 - 1000 n^2, za předpokladu T(1) = 1.)

Případ 2

Obecný tvar

Pokud platí:

:\exists k\ge 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) = 2 T\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 + 10 n\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í:

:a f\left( \frac{n}{b} \right) \le c f(n) pro nějaké c a dostatečně velké n

tak:

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

Příklad

:T(n) = 2 T\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:

:a f\left( \frac{n}{b} \right) \le c f(n)

Opět dosadíme hodnoty:

:2 \left( \frac{n}{2} \right)^2 \le c n^2 \Leftrightarrow \frac{1}{2} n^2 \le cn^2

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

: \frac{1}{2} n^2 \le \frac{1}{2} n^2 \forall n \ge 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) = 2 n^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^nT\left (\frac{n}{2}\right )+n^n

To protože a (2n) 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 (aT(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

Reference

Literatura

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

Kategorie:Asymptotické chování Kategorie:Třídy složitosti