Hlavní věta o rekurentních vztazích

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 .

Popis

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í konec

Ve 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í.

Obecný formulář

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:

Možnost 1

Obecný formulář

Pokud , a vztah

pak:

Příklad

Podle vzorce jsou hodnoty konstant a složitost nerekurzivní části problému:

, kde

Poté 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 ).

Možnost 2

Obecný formulář

Pokud pro nějakou konstantu k  ≥ 0 platí:

kde

pak:

Příklad

Podle vzorce jsou hodnoty konstant a složitost nerekurzivní části problému:

kde

Kontrola poměru možnosti 2:

, a tedy

V 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 .)

Možnost 3

Obecný formulář

Pokud se provede:

kde

a také je pravda, že:

pro nějaké konstantní a dostatečně velké (tzv. podmínka pravidelnosti )

pak:

Příklad

Konstantní hodnoty a funkce:

, kde

Zkontrolujeme, zda je splněn vztah z možnosti 3:

, a tedy

Podmínka pravidelnosti také platí :

, při výběru

Proto 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 .)

Výrazy neřešené hlavní větou

Následující vztahy nelze řešit pomocí hlavní věty: [2]

  • a není konstanta, hlavní věta vyžaduje konstantní počet dílčích problémů;
  • mezi f(n) a existuje nepolynomiální závislost;
  • a < 1, ale hlavní věta vyžaduje alespoň jeden dílčí úkol;
  • f(n) je záporné;
  • blízko možnosti 3, ale není splněna podmínka pravidelnosti .

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í.

Aplikace na některé algoritmy

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

Viz také

  • Metoda Akra-Bazzi

Poznámky

  1. Duke University, „Big-Oh for Recurrsive Functions: Recurrence Relations“, http://www.cs.duke.edu/~ola/ap/recurrence.html Archivováno 22. června 2012 na Wayback Machine
  2. Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf  (mrtvý odkaz)
  3. 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Archivováno 21. dubna 2017 na Wayback Machine
  4. Hlavní věta pro diskrétní opakování dělení a panování . Získáno 19. srpna 2016. Archivováno z originálu 18. dubna 2016.

Literatura

  • Kormen, T., Leizerson, C., Rivest, R., Stein, C. Algoritmy: konstrukce a analýza = Introduction to Algorithms. - 2. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . Kapitoly 4.3 (hlavní teorém) a 4.4 (důkaz)
    • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Úvod do algoritmů. — 2. - MIT Press a McGraw-Hill, 2001. - ISBN 0-262-53196-8 . Sekce 4.3 (Metoda mistra) a 4.4 (Důkaz hlavního teorému), str. 73-90. (Angličtina)
  • 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. (Angličtina)
  • KAPITOLA 5. REKURZE A OPAKOVÁNÍ 5.2 The Master Theorem Archived 21. dubna 2017 na Wayback Machine , CS 21/Math 19 – Poznámky ke kurzu archivovány 21. července 2010 na Wayback Machine , Ken Bogart a Cliff Stein: Diskrétní matematika v počítačové vědě.