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:
, kde
Při analýze rekurzivních algoritmů mají konstanty a funkce následující význam:
je velikost problému. je počet podproblémů v rekurzi. je velikost každého z podproblémů. Předpokládá se, že podproblémy jsou víceméně stejně velké. 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 pro nějaké
tak:
Příklad
Z výše uvedené rovnice vidíme, že hodnoty jsou:
, , ,
Nyní musíme zkontrolovat, zda platí:
Po dosazení hodnot dostaneme:
Pokud zvolíme = 1, dostaneme:
Protože rovnost platí, první případ master theoremu lze použít na danou rekurentní rovnost, čímž dostaneme:
Po dosazení hodnot:
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 , za předpokladu .)
Případ 2
Obecný tvar Pokud platí:
tak:
Příklad
Z výše uvedené rovnice vidíme, že hodnoty jsou:
, , , ,
Nyní ověříme, že následující rovnost platí (v tomto případě k=0):
Po dosazení dostaneme:
Protože rovnost platí, druhý případ master theoremu lze aplikovat, čímž dostáváme:
Po dosazení:
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 , za předpokladu .)
Případ 3
Obecný tvar Pokud platí:
pro nějaké
a také platí:
pro nějaké a dostatečně velké n
tak:
Příklad
Z výše uvedené rovnice vidíme, že hodnoty jsou:
, , ,
Nyní ověříme, že následující rovnost platí:
Pokud dosadíme hodnoty a zvolíme = 1, dostaneme:
Protože rovnost platí, ověříme druhou podmínku, konkrétně, že:
Opět dosadíme hodnoty:
Pokud zvolíme , tak platí:
Tedy:
Opět dosadíme hodnoty a dostaneme:
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 , za předpokladu .)
Nepřípustné rovnice Následující rovnice nelze vyřešit pomocí master theoremu:
To protože a (2n) není konstanta.
Mezi f(n) a je nepolynomiální rozdíl.
Nelze mít méně, než jeden podproblém (a<1).
f(n) není kladné.
Případ 3, ale porušení regularity.
Odkazy Reference
Literatura Thomas H. 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