Teorema principală a relațiilor de recurență

Teorema Master este utilizată în analiza algoritmilor pentru a obține o estimare asimptotică pentru relațiile recursive ( ecuații recursive ), care apar adesea în analiza algoritmilor de tip „ divid și cuceri ” ( divide și cuceri ), de exemplu, la estimarea timpul lor de executare. Teorema a fost introdusă și demonstrată de John Bentley, Doroten Haken și James Haken în 1980. Teorema a fost popularizată în cartea Algorithms: Construction and Analysis ( Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein ) în care a fost dată.

Nu toate relațiile recursive pot fi rezolvate folosind teorema principală. Există mai multe generalizări ale acesteia, inclusiv metoda Akra-Bazzi .

Descriere

Luați în considerare o problemă care poate fi rezolvată printr-un algoritm recursiv :

funcția T(intrare n : dimensiunea sarcinii): dacă n < o constantă k : rezolvați problema pentru n în mod nerecursiv altfel : definiți un set de subsarcini , fiecare cu dimensiunea n/b apelați funcția T în mod recursiv pentru fiecare subsarcină combina solutii Sfârşit

În exemplul de mai sus, algoritmul împarte recursiv sarcina inițială de dimensiunea n în mai multe subsarcini noi, fiecare cu dimensiunea n/b . O astfel de partiție poate fi reprezentată ca un arbore de apeluri, în care fiecare nod corespunde unui apel recursiv, iar ramurile care ies din nod corespund apelurilor ulterioare pentru subsarcini. Fiecare nod va avea o ramuri. De asemenea, fiecare nod produce cantitatea de muncă corespunzătoare mărimii subsarcinii curente n (trecută la acest apel de funcție) conform relației . Cantitatea totală de lucru a algoritmului este definită ca suma tuturor lucrărilor din nodurile arborelui dat. $f(n)$

Complexitatea computațională a unor astfel de algoritmi poate fi reprezentată ca o relație recursivă . Poate fi rezolvată prin substituții multiple ale expresiei . [unu] $T(n)=a\;T\stanga({\frac {n}{b}}\dreapta)+f(n)$ $T\stânga({\frac {n}{b}}\dreapta)$

Cu ajutorul teoremei principale, este posibil să se calculeze rapid astfel de relații, ceea ce face posibilă obținerea unei estimări asimptotice a timpului de rulare a algoritmilor recursivi în notația O(n) ( notația Θ) fără substituții.

Forma generală

Teorema principală ia în considerare următoarele relații de recurență:

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

După cum se aplică analizei algoritmilor, constantele și funcțiile denotă:

n este dimensiunea sarcinii.
a este numărul de subsarcini din recursivitate.
n / b este dimensiunea fiecărei sarcini secundare. (Se presupune că toate subsarcinile din fiecare etapă sunt de aceeași dimensiune.)
f ( n ) este o estimare a complexității muncii efectuate de algoritm în afara apelurilor recursive. De asemenea, include costul de calcul al împărțirii în subprobleme și al combinării rezultatelor rezolvării subproblemelor.

Teorema principală ne permite să obținem o estimare asimptotică pentru următoarele trei cazuri:

Opțiunea 1

Forma generală

Dacă , și relația $f(n)=O\stânga(n^{{c}}\dreapta)$ $c<\log _{b}a$

apoi:

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

Exemplu

T(n)=8T\stânga({\frac {n}{2}}\dreapta)+1000n^{2}

Conform formulei, valorile constantelor și complexitatea părții nerecursive a problemei sunt:

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

f(n)=O\stânga(n^{c}\dreapta)

, Unde

c=2

Apoi, verificăm dacă relația de prima opțiune este îndeplinită:

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

Prin urmare,

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

(Pentru acest exemplu, soluția exactă de recurență oferă , cu condiția ). $T(n)=1001n^{3}-1000n^{2}$ $T(1)=1$

Opțiunea 2

Forma generală

Dacă pentru o constantă k ≥ 0 este valabilă următoarele:

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

Unde

c=\log _{b}a

apoi:

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

Exemplu

$T(n)=2T\stanga({\frac {n}{2}}\dreapta)+10n$

Conform formulei, valorile constantelor și complexitatea părții nerecursive a problemei sunt:

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

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

Unde

c=1,k=0

Verificarea raportului opțiunii 2:

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

, și, prin urmare

c=\log _{b}a

În conformitate cu cea de-a doua versiune a teoremei principale:

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)

Astfel relația de recurență T ( n ) este Θ( n log n ).

(Acest rezultat poate fi verificat prin soluția exactă a relației în care , sub rezerva .) $T(n)=n+10n\log _{2}n$ $T(1)=1$

Opțiunea 3

Forma generală

Dacă este executat:

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

Unde

c>\log _{b}a

si este de asemenea adevarat ca:

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

pentru unele constante și suficient de mari (așa-numita condiție de regularitate )

k<1

n

apoi:

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

Exemplu

T(n)=2T\stânga({\frac {n}{2}}\dreapta)+n^{2}

Valori și funcții constante:

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

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

, Unde

c=2

Verificăm dacă relația de la opțiunea 3 este satisfăcută:

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

, și, prin urmare

c>\log _{b}a

Condiția de regularitate este valabilă și :

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

, la alegere

k=1/2

Prin urmare, conform celei de-a treia versiuni a teoremei principale:

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

Această relație recursivă T ( n ) este egală cu Θ( n 2 ), care este același cu f ( n ) în formula originală.

(Acest rezultat este confirmat de soluția exactă de recurență în care , sub rezerva .) $T(n)=2n^{2}-n$ $T(1)=1$

Expresii nerezolvate de teorema principală

Următoarele relații nu pot fi rezolvate folosind teorema principală: [2]

$T(n)=2^{n}T\stanga({\frac {n}{2}}\dreapta)+n^{n}$ a nu este o constantă, teorema principală necesită un număr constant de subprobleme;
$T(n)=2T\stanga({\frac {n}{2}}\dreapta)+{\frac {n}{\log n}}$ între f(n) și există o dependență nepolinomială; $n^{{\log _{b}a}}$
$T(n)=0,5T\stanga({\frac {n}{2}}\dreapta)+n$ a < 1, dar teorema principală necesită cel puțin o subsarcină;
$T(n)=64T\stanga({\frac {n}{8}}\dreapta)-n^{2}\log n$ f(n) este negativ;
$T(n)=T\stanga({\frac {n}{2}}\dreapta)+n(2-\cos n)$ aproape de varianta 3, dar conditia de regularitate nu este indeplinita .

În al doilea exemplu, diferența dintre și poate fi exprimată ca . Arată că pentru orice constantă . Prin urmare, diferența nu este un polinom și teorema principală nu se aplică. $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$

Aplicarea unor algoritmi

Algoritm	Relație recurentă	Ore de lucru	Notă
Căutare binară	$T(n)=T\stanga({\frac {n}{2}}\dreapta)+O(1)$	$O(\log n)$	Teorema principală, a doua opțiune: , unde [3] $c=\log _{b}a$ $a=1,b=2,c=0,k=0$
Traversarea arborelui binar	$T(n)=2T\stanga({\frac {n}{2}}\dreapta)+O(1)$	$Pe)$	Teorema principală, versiunea 1: unde [3] $c<\log _{b}a$ $a=2,b=2,c=0$
Algoritmul Strassen	$T(n)=7T\left({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\aproximativ O(n^{2,81})$	Teorema principală, versiunea 1: , unde [4] $c<\log _{b}a$ $a=7,b=2,c=2$
Căutare optimă în matrice sortată	$T(n)=2T\stanga({\frac {n}{2}}\dreapta)+O(\log n)$	$Pe)$	Teorema Akra-Bazzi pentru și pentru obținere $p=1$ $g(u)=\log(u)$ $\Theta (2n-\log n)$
Sortare îmbinare	$T(n)=2T\stanga({\frac {n}{2}}\dreapta)+O(n)$	$O(n\log n)$	Teorema principală, a 2-a opțiune: , unde $c=\log _{b}a$ $a=2,b=2,c=1,k=0$

Vezi și

Metoda Akra-Bazzi

Note

↑ Universitatea Duke, „Big-Oh for Recursive Functions: Recurrence Relations”, http://www.cs.duke.edu/~ola/ap/recurrence.html Arhivat la 22 iunie 2012 la Wayback Machine
↑ Massachusetts Institute of Technology (MIT), „Master Theorem: Practice Problems and Solutions”, http://www.csail.mit.edu/~thies/6.046-web/master.pdf (link mort)
↑ 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Arhivat la 21 aprilie 2017 la Wayback Machine
↑ O teoremă principală pentru recurențe discrete de împărțire și cucerire . Preluat la 19 august 2016. Arhivat din original la 18 aprilie 2016. (nedefinit)

Literatură

Kormen, T., Leizerson, C., Rivest, R., Stein, C. Algoritmi: construcție și analiză = Introduction to Algorithms. - al 2-lea. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 . Capitolele 4.3 (teorema principală) și 4.4 (dovada)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introducere în algoritmi. — al 2-lea. - MIT Press și McGraw-Hill, 2001. - ISBN 0-262-53196-8 . Secțiunile 4.3 (Metoda master) și 4.4 (Demonstrarea teoremei master), pp. 73-90. (Engleză)
Michael T. Goodrich și Roberto Tamassia . Proiectare algoritm: fundație, analiză și exemple de internet . Wiley, 2002. ISBN 0-471-38365-1 . Teorema principală (inclusiv versiunea Cazului 2 inclusă aici, care este mai puternică decât cea de la CLRS) este la pp. 268-270. (Engleză)
CAPITOLUL 5. RECURSIE ȘI RECUPERE 5.2 The Master Theorem Arhivat 21 aprilie 2017 la Wayback Machine , CS 21/Math 19 - Note de curs Arhivat 21 iulie 2010 la Wayback Machine , Ken Bogart și Cliff Stein: Discrete Math in Computer Science.