Masterova věta (analýza algoritmů) - Master theorem (analysis of algorithms)
V analýza algoritmů, hlavní věta o opakování rozděli a panuj poskytuje asymptotická analýza (použitím Velká O notace ) pro relace opakování typů, které se vyskytují v analýza z mnoha algoritmy rozdělení a dobývání. Přístup poprvé představil Jon Bentley, Dorothea Haken, a James B. Saxe v roce 1980, kdy byla popsána jako „sjednocující metoda“ řešení těchto opakování.[1] Název „hlavní věta“ popularizovala široce používaná učebnice algoritmů Úvod do algoritmů podle Cormen, Leiserson, Rivest, a Steine.
Ne všechny relace opakování lze vyřešit pomocí této věty; jeho zevšeobecnění zahrnuje Metoda Akra – Bazzi.
Úvod
Zvažte problém, který lze vyřešit pomocí a rekurzivní algoritmus například následující:
postup p (vstup X velikosti n): -li nk: Řešit X přímo bez rekurze jiný: Vytvořit A dílčí problémy X, z nichž každý má velikost n/b Postup volání p rekurzivně na každém dílčím problému Zkombinujte výsledky dílčích problémů
Výše uvedený algoritmus rozděluje problém na několik dílčích problémů rekurzivně, přičemž každý dílčí problém má velikost n/b. Své strom řešení má uzel pro každé rekurzivní volání, přičemž podřízené prvky tohoto uzlu jsou ostatní volání z tohoto volání. Listy stromu jsou základními případy rekurze, subproblémy (o velikosti menší než k), které se neopakují. Výše uvedený příklad by měl A podřízené uzly v každém nelistovém uzlu. Každý uzel dělá množství práce, které odpovídá velikosti dílčího problému n předán této instanci rekurzivního volání a dán . Celkové množství práce provedené celým algoritmem je součtem práce provedené všemi uzly ve stromu.
Runtime algoritmu, jako je výše uvedené „p“ na vstupu velikosti „n“, obvykle označeno , lze vyjádřit pomocí relace opakování
kde je čas vytvořit dílčí problémy a zkombinovat jejich výsledky do výše uvedeného postupu. Tato rovnice může být postupně nahrazena sama sebou a rozšířena, aby se získal výraz pro celkové množství odvedené práce.[2]Hlavní věta umožňuje převést mnoho relací opakování této formy Θ-notace přímo, aniž by došlo k rozšíření rekurzivního vztahu.
Obecná forma
Hlavní věta se vždy podvolí asymptoticky těsné hranice na recidivy z algoritmy rozděl a panuj které rozdělují vstup na menší dílčí problémy stejné velikosti, řeší dílčí problémy rekurzivně a poté kombinují řešení dílčích problémů, aby poskytly řešení původního problému. Čas pro takový algoritmus lze vyjádřit přidáním práce, kterou provádějí na nejvyšší úrovni jejich rekurze (rozdělit problémy na dílčí problémy a poté kombinovat řešení dílčích problémů) spolu s časem provedeným v rekurzivních voláních algoritmu. Li označuje celkový čas pro algoritmus na vstupu velikosti , a označuje dobu potřebnou na nejvyšší úrovni opakování, pak lze čas vyjádřit a relace opakování který má podobu:
Tady je velikost problému se vstupem, je počet dílčích problémů v rekurzi a je faktor, kterým se velikost dílčího problému zmenší při každém rekurzivním volání. Níže uvedená věta také předpokládá, že jako základní případ opakování když je menší než někteří vázaní , nejmenší velikost vstupu, která povede k rekurzivnímu volání.
Recidivy této formy často uspokojují jeden ze tří následujících režimů, založených na tom, jak práce na rozdělení / rekombinaci problému se vztahuje k kritický exponent (Níže uvedená tabulka používá standard velká O notace.)
Případ | Popis | Podmínka zapnuta ve vztahu k , tj. | Hlavní věta vázána | Notační příklady |
---|---|---|---|---|
1 | Práce na rozdělení / opětovném zkombinování problému je trpasličí podproblémy. tj. rekurzivní strom je listový | Když kde (horní ohraničený polynomem s menším exponentem) | ... pak (Členicí člen se neobjeví; dominuje rekurzivní stromová struktura.) | Li a , pak . |
2 | Práce na rozdělení / rekombinaci problému je srovnatelná s dílčími problémy. | Když pro (rangebound by the critical-exponent polynomial, times zero or more optional s) | ... pak (Vázaný je dělicí člen, kde je protokol rozšířen o jednu mocninu.) | Li a , pak . Li a , pak . |
3 | Práce na rozdělení / rekombinaci problému dominuje dílčím problémům. tj. rekurzivní strom je kořenový. | Když kde (dolní ohraničený polynomem s většími exponenty) | ... to nutně nemusí nic přinést. Pokud je dále známo, že
pak součtu dominuje dělící člen : | Li a a podmínka pravidelnosti tedy platí . |
Užitečné rozšíření pro případ 2 zpracovává všechny hodnoty :[3]
Případ | Podmínka zapnuta ve vztahu k , tj. | Hlavní věta vázána | Notační příklady |
---|---|---|---|
2a | Když pro všechny | ... pak (Vázaný je dělicí člen, kde je protokol rozšířen o jednu mocninu.) | Li a , pak . |
2b | Když pro | ... pak (Vázaný je dělící člen, kde je reciproční protokol nahrazen iterovaným protokolem.) | Li a , pak . |
2c | Když pro všechny | ... pak (Vázaný je dělící člen, kde log zmizí.) | Li a , pak . |
Příklady
Příklad 1
Jak je vidět z výše uvedeného vzorce:
- , tak
- , kde
Dále uvidíme, zda splníme podmínku případu 1:
- .
Z prvního případu hlavní věty to vyplývá
(Tento výsledek je potvrzen přesným řešením relace rekurence, která je , za předpokladu ).
Příklad 2
Jak vidíme ve vzorci výše, proměnné získají následující hodnoty:
- kde
Dále uvidíme, zda splníme podmínku případu 2:
- , a proto,
Vyplývá to z druhého případu hlavní věty:
Tedy daný vztah opakování T(n) byl v Θ (n log n).
(Tento výsledek je potvrzen přesným řešením relace rekurence, která je , za předpokladu .)
Příklad 3
Jak vidíme ve vzorci výše, proměnné získají následující hodnoty:
- , kde
Dále uvidíme, zda splníme podmínku případu 3:
- , a proto ano,
Podmínka pravidelnosti platí také:
- , výběr
Z třetího případu hlavní věty tedy vyplývá:
Tedy daný vztah opakování T(n) byl v Θ (n2), který je v souladu s F (n) původního vzorce.
(Tento výsledek je potvrzen přesným řešením relace rekurence, která je , za předpokladu .)
Nepřípustné rovnice
Následující rovnice nelze vyřešit pomocí hlavní věty:[4]
- A není konstanta; počet dílčích problémů by měl být stanoven
- nepolynomiální rozdíl mezi f (n) a (viz níže; platí rozšířená verze)
- nemůže mít méně než jeden dílčí problém
- f (n), což je čas kombinace, není kladný
- případ 3, ale porušení pravidelnosti.
Ve druhém nepřípustném příkladu výše je rozdíl mezi a lze vyjádřit poměrem . Je jasné že pro jakoukoli konstantu . Rozdíl proto není polynomický a základní forma hlavní věty neplatí. Platí rozšířený formulář (případ 2b), který poskytuje řešení .
Aplikace na běžné algoritmy
Algoritmus | Vztah opakování | Čas běhu | Komentář |
---|---|---|---|
Binární vyhledávání | Použít případ Master theorem , kde [5] | ||
Traverze binárního stromu | Použít případ Master theorem kde [5] | ||
Optimální tříděné maticové vyhledávání | Použijte Věta Akra – Bazzi pro a dostat | ||
Sloučit třídění | Použít případ Master theorem , kde |
Viz také
Poznámky
- ^ Bentley, Jon Louis; Haken, Dorothea; Saxe, James B. (Září 1980), „Obecná metoda řešení opakování rozděl a panuj“, Novinky ACM SIGACT, 12 (3): 36–44, doi:10.1145/1008861.1008865
- ^ Duke University, "Big-Oh pro rekurzivní funkce: rekurentní vztahy", http://www.cs.duke.edu/~ola/ap/recurrence.html
- ^ Chee Yap, Skutečný elementární přístup k opakování a zevšeobecňování mistra, Sborník příspěvků z 8. výroční konference o teorii a aplikacích modelů výpočtu (TAMC'11), strany 14–26, 2011. Online kopie.
- ^ Massachusetts Institute of Technology (MIT), „Master Theorem: Practice Problems and Solutions“, https://people.csail.mit.edu/thies/6.046-web/master.pdf
- ^ A b Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf
Reference
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw – Hill, 2001. ISBN 0-262-03293-7. Sekce 4.3 (Hlavní metoda) a 4.4 (Důkaz hlavní věty), s. 73–90.
- Michael T. Goodrich a Roberto Tamassia. Návrh algoritmu: základy, analýza a příklady internetu. Wiley, 2002. ISBN 0-471-38365-1. Hlavní věta (včetně zde zahrnuté verze případu 2, která je silnější než ta z CLRS) je na str. 268–270.
Externí odkazy
- Teorema Mestre e Exemplos Resolvidos (v portugalštině)