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:

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 pro nějaké

tak:

Příklad[editovat | editovat zdroj]

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

Obecný tvar[editovat | editovat zdroj]

Pokud platí:

tak:

Příklad[editovat | editovat zdroj]

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

Obecný tvar[editovat | editovat zdroj]

Pokud platí:

pro nějaké

a také platí:

pro nějaké a dostatečně velké n

tak:

Příklad[editovat | editovat zdroj]

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

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

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.

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.