Master theorem

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Obecný tvar[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Obecný tvar[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Obecný tvar[editovat | editovat zdroj]

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 < 1 a dostatečně velké n

tak:

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

Příklad[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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

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 (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[editovat | editovat zdroj]

  1. http://www.cag.lcs.mit.edu/~thies/6.046-web/master.pdf

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