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. $f(n)$

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] $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$ $T\left({\frac {n}{b}}\right)$

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:

T(n)=a\;T\!\left({\frac {n}{b))\right)+f(n),\;\;\;\;{\mbox{where} }\;\;a\geq 1{\mbox{, }}b>1

Jak je aplikováno na analýzu algoritmů, konstanty a funkce označují:

n je velikost úlohy.
a je počet dílčích úkolů v rekurzi.
n / b je velikost každého dílčího úkolu. (Předpokládá se, že všechny dílčí úkoly v každé fázi mají stejnou velikost.)
f ( n ) je odhad složitosti práce vykonávané algoritmem mimo rekurzivní volání. Zahrnuje také výpočetní náklady na rozdělení do dílčích problémů a kombinování výsledků řešení dílčích problémů.

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 $f(n)=O\left(n^{{c}}\vpravo)$ $c<\log _{b}a$

pak:

T(n)=\Theta \left(n^{{\log _{b}a}}\right)

Příklad

T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}

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

a=8,\,b=2,\,f(n)=1000n^{2}

f(n)=O\left(n^{c}\vpravo)

, kde

c=2

Poté zkontrolujeme, zda je splněn vztah 1. možnosti:

\log _{b}a=\log _{2}8=3>c

Tudíž,

T(n)=\Theta \left(n^{{\log _{b}a}}\right)=\Theta \left(n^{{3}}\right)

(Pro tento příklad přesné řešení opakování dává , za předpokladu ). $T(n)=1001n^{3}-1000n^{2}$ $T(1)=1$

Možnost 2

Obecný formulář

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

f(n)=\Theta \left(n^{{c}}\log ^{{k}}n\right)

kde

c=\log _{b}a

pak:

T(n)=\Theta \left(n^{{c}}\log ^{{k+1}}n\right)

Příklad

$T(n)=2T\left({\frac {n}{2}}\vpravo)+10n$

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

a=2,\,b=2,\,c=1,\,f(n)=10n

f(n)=\Theta \left(n^{{c}}\log ^{{k}}n\right)

kde

c=l,k=0

Kontrola poměru možnosti 2:

\log _{b}a=\log _{2}2=1

, a tedy

c=\log _{b}a

V souladu s 2. verzí hlavní věty:

T(n)=\Theta \left(n^{{\log _{b}a}}\log ^{{k+1}}n\right)=\Theta \left(n^{{1}} \log ^{{1}}n\right)=\Theta \left(n\log n\right)

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 .) $T(n)=n+10n\log _{2}n$ $T(1)=1$

Možnost 3

Obecný formulář

Pokud se provede:

f(n)=\Omega \left(n^{{c}}\right)

kde

c>\log _{b}a

a také je pravda, že:

af\left({\frac {n}{b}}\right)\leq kf(n)

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

k<1

n

pak:

T\left(n\right)=\Theta\left(f(n)\right)

Příklad

T(n)=2T\left({\frac {n}{2}}\vpravo)+n^{2}

Konstantní hodnoty a funkce:

a=2,\,b=2,\,f(n)=n^{2}

f(n)=\Omega \left(n^{c}\right)

, kde

c=2

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

\log _{b}a=\log _{2}2=1

, a tedy

c>\log _{b}a

Podmínka pravidelnosti také platí :

2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}

, při výběru

k=1/2

Proto podle 3. verze hlavní věty:

T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).

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 .) $T(n)=2n^{2}-n$ $T(1)=1$

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

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

$T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$ a není konstanta, hlavní věta vyžaduje konstantní počet dílčích problémů;
$T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$ mezi f(n) a existuje nepolynomiální závislost; $n^{{\log _{b}a}}$
$T(n)=0,5T\left({\frac {n}{2}}\vpravo)+n$ a < 1, ale hlavní věta vyžaduje alespoň jeden dílčí úkol;
$T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$ f(n) je záporné;
$T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$ 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í. $f(n)$ $n^{{\log _{b}a}}$ ${\frac {f(n)}{n^{{\log _{b}a))))={\frac ({\frac {n}{\log n))}{n^{{log_{ 2}2))))={\frac {n}{n\log n}}={\frac {1}{\log n}}$ ${\frac {1}{\log n}}<n^{\epsilon }$ $\epsilon > 0$

Aplikace na některé algoritmy

Algoritmus	Opakující se vztah	Pracovní doba	Poznámka
Binární vyhledávání	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Hlavní věta, 2. možnost: , kde [3] $c=\log _{b}a$ $a=1,b=2,c=0,k=0$
Procházení binárního stromu	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$Na)$	Hlavní věta, verze 1: kde [3] $c<\log _{b}a$ $a=2,b=2,c=0$
Strassenův algoritmus	$T(n)=7T\left({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\přibližně O(n^{2,81})$	Hlavní věta, verze 1: , kde [4] $c<\log _{b}a$ $a=7,b=2,c=2$
Optimální vyhledávání v tříděné matici	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$Na)$	Akra-Bazziho věta pro a pro získání $p=1$ $g(u)=\log(u)$ $\Theta (2n-\log n)$
Sloučit třídění	$T(n)=2T\left({\frac {n}{2}}\vpravo)+O(n)$	$O(n\log n)$	Hlavní věta, 2. možnost: , kde $c=\log _{b}a$ $a=2,b=2,c=l,k=0$

Viz také

Metoda Akra-Bazzi

Poznámky

↑ 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
↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (mrtvý odkaz)
↑ 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Archivováno 21. dubna 2017 na Wayback Machine
↑ 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. (neurčitý)

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