Master teorém se používá při analýze algoritmů k získání asymptotického odhadu pro rekurzivní vztahy ( rekurzivní rovnice ), které často vznikají při analýze algoritmů typu „ rozděl a panuj “ ( rozděl a panuj ), např. při odhadu doba jejich provedení. Větu představili a dokázali John Bentley, Doroten Haken a James Haken v roce 1980. Tento teorém byl popularizován v knize Algorithms: Construction and Analysis ( Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein ), ve které byl uveden.
Ne všechny rekurzivní vztahy lze vyřešit pomocí hlavní věty. Existuje několik jeho zobecnění, včetně metody Akra-Bazzi .
Zvažte problém, který lze vyřešit rekurzivním algoritmem :
funkce T(vstup n : velikost úlohy): jestliže n < nějaká konstanta k : vyřešit problém pro n nerekurzivně jinak :definovat sadu dílčích úkolů, každou o velikosti n/b volání funkce T rekurzivně pro každý dílčí úkol kombinovat řešení konecVe výše uvedeném příkladu algoritmus rekurzivně rozdělí původní úlohu velikosti n na několik nových dílčích úloh, každou o velikosti n/b . Takový oddíl může být reprezentován jako strom volání, ve kterém každý uzel odpovídá rekurzivnímu volání a větve vycházející z uzlu odpovídají následným voláním dílčích úkolů. Každý uzel bude mít větve . Každý uzel také produkuje množství práce odpovídající velikosti aktuální dílčí úlohy n (předané tomuto volání funkce) podle vztahu . Celkové množství práce algoritmu je definováno jako součet veškeré práce v uzlech daného stromu.
Výpočetní složitost takových algoritmů může být reprezentována jako rekurzivní vztah . Lze to vyřešit vícenásobnými substitucemi výrazu . [jeden]
Pomocí hlavní věty je možné rychle vypočítat takové vztahy, které umožňují získat asymptotický odhad doby běhu rekurzivních algoritmů v notaci O(n) (Θ-notace) bez substitucí.
Hlavní věta uvažuje následující rekurentní vztahy:
Jak je aplikováno na analýzu algoritmů, konstanty a funkce označují:
Hlavní věta nám umožňuje získat asymptotický odhad pro následující tři případy:
Pokud , a vztah
pak:
PříkladPodle vzorce jsou hodnoty konstant a složitost nerekurzivní části problému:
, kdePoté zkontrolujeme, zda je splněn vztah 1. možnosti:
.Tudíž,
(Pro tento příklad přesné řešení opakování dává , za předpokladu ).
Pokud pro nějakou konstantu k ≥ 0 platí:
kdepak:
Příklad
Podle vzorce jsou hodnoty konstant a složitost nerekurzivní části problému:
kdeKontrola poměru možnosti 2:
, a tedyV souladu s 2. verzí hlavní věty:
Rekurentní vztah T ( n ) je tedy Θ( n log n ).
(Tento výsledek lze ověřit přesným řešením vztahu, ve kterém , s výhradou .)
Pokud se provede:
kdea také je pravda, že:
pro nějaké konstantní a dostatečně velké (tzv. podmínka pravidelnosti )pak:
PříkladKonstantní hodnoty a funkce:
, kdeZkontrolujeme, zda je splněn vztah z možnosti 3:
, a tedyPodmínka pravidelnosti také platí :
, při výběruProto podle 3. verze hlavní věty:
Tento rekurzivní vztah T ( n ) je roven Θ( n 2 ), což je stejné jako f ( n ) v původním vzorci.
(Tento výsledek je potvrzen přesným řešením opakování, ve kterém , s výhradou .)
Následující vztahy nelze řešit pomocí hlavní věty: [2]
Ve druhém příkladu lze rozdíl mezi a vyjádřit jako . Ukazuje, že pro jakoukoli konstantu . Rozdíl tedy není polynom a hlavní věta neplatí.
Algoritmus | Opakující se vztah | Pracovní doba | Poznámka |
---|---|---|---|
Binární vyhledávání | Hlavní věta, 2. možnost: , kde [3] | ||
Procházení binárního stromu | Hlavní věta, verze 1: kde [3] | ||
Strassenův algoritmus | Hlavní věta, verze 1: , kde [4] | ||
Optimální vyhledávání v tříděné matici | Akra-Bazziho věta pro a pro získání | ||
Sloučit třídění | Hlavní věta, 2. možnost: , kde |