Teorema principală

Teorema principală (în engleză master theorem), cunoscută și sub numele de master teorema și teorema profesorului, este o teoremă referitoare la „ analiza algoritmilor care oferă o soluție asimptotică unei familii de relații de recurență . A fost expusă pentru prima dată de Jon Bentley , Dorothea Haken și James B. Saxe în 1980, unde a fost descrisă ca o metodă unificată ^[1] pentru o familie de recurență. ^[2] Numele acestei teoreme a fost popularizat de celebrul manual Introducere în algoritmi de către Cormen , Leiserson , Rivest și Stein . Nu oferă o soluție la toate relațiile posibile de recurență, iar generalizarea acesteia este teorema Akra-Bazzi .

În mod informal, teorema afirmă că dat o relație de recurență în formă $T(n)=aT\left({\frac {n}{b}}\right)+f(n)$ ${\ displaystyle T (n) = aT \ left ({\ frac {n} {b}} \ right) + f (n)}$ ${\ displaystyle T (n) = aT \ left ({\ frac {n} {b}} \ right) + f (n)}$ cu $a\geq 1$ ${\ displaystyle a \ geq 1}$ $a \ geq 1$ Și $b>1$ ${\ displaystyle b> 1}$ $b> 1$ , în unele cazuri se poate obține o soluție prin comparare $f$ ${\ displaystyle f}$ $f$ cu funcție $n^{\log _{b}a}$ ${\ displaystyle n ^ {\ log _ {b} a}}$ $n ^ {{\ log _ {b} a}}$ . De sine $f$ ${\ displaystyle f}$ $f$ este asimptotic polinomial mai mic (adică mai mic cu cel puțin un factor polinomial $n^{\varepsilon }$ ${\ displaystyle n ^ {\ varepsilon}}$ ${\ displaystyle n ^ {\ varepsilon}}$ ) asa de $T(n)=\Theta (n^{\log _{b}a})$ ${\ displaystyle T (n) = \ Theta (n ^ {\ log _ {b} a})}$ ${\ displaystyle T (n) = \ Theta (n ^ {\ log _ {b} a})}$ ; dacă cele două funcții au asimptotic aceeași magnitudine atunci $T(n)=\Theta (n^{\log _{b}a}\log(n))=\Theta \left(f(n)\log(n)\right)$ ${\ displaystyle T (n) = \ Theta (n ^ {\ log _ {b} a} \ log (n)) = \ Theta \ left (f (n) \ log (n) \ right)}$ ${\ displaystyle T (n) = \ Theta (n ^ {\ log _ {b} a} \ log (n)) = \ Theta \ left (f (n) \ log (n) \ right)}$ ; în cele din urmă, dacă $f$ ${\ displaystyle f}$ $f$ este suficient de regulat și polinomial mai mare atunci $T(n)=\Theta \left(f(n)\right)$ ${\ displaystyle T (n) = \ Theta \ left (f (n) \ right)}$ ${\ displaystyle T (n) = \ Theta \ left (f (n) \ right)}$ . Cazurile în care $f$ ${\ displaystyle f}$ $f$ este asimptotic mai mare sau mai mic decât $n^{\log _{b}a}$ ${\ displaystyle n ^ {\ log _ {b} a}}$ $n ^ {{\ log _ {b} a}}$ într-un mod non-polinomial. ^[3]

Afirmație

Se dă o relație de recurență $T(n)$ ${\ displaystyle T (n)}$ $T (n)$ sub forma ^[4]

T(n)=aT\left({\frac {n}{b}}\right)+f(n)

{\ displaystyle T (n) = aT \ left ({\ frac {n} {b}} \ right) + f (n)}

{\ displaystyle T (n) = aT \ left ({\ frac {n} {b}} \ right) + f (n)}

unde este $a\geq 1$ ${\ displaystyle a \ geq 1}$ $a \ geq 1$ Și $b>1$ ${\ displaystyle b> 1}$ $b> 1$ sunt constante și $\;{\frac {n}{b}}\;$ ${\ displaystyle \; {\ frac {n} {b}} \;}$ $\; {\ frac {n} {b}} \;$ poate fi interpretat ca fie $\;\left\lfloor {\frac {n}{b}}\right\rfloor \;$ ${\ displaystyle \; \ left \ lfloor {\ frac {n} {b}} \ right \ rfloor \;}$ $\; \ left \ lfloor {\ frac {n} {b}} \ right \ rfloor \;$ ( partea întreagă ) este la fel $\;\left\lceil {\frac {n}{b}}\right\rceil \;$ ${\ displaystyle \; \ left \ lceil {\ frac {n} {b}} \ right \ rceil \;}$ $\; \ left \ lceil {\ frac {n} {b}} \ right \ rceil \;$ ( toată partea superioară ).

Apoi funcția $\,T(n)$ ${\ displaystyle \, T (n)}$ ${\ displaystyle \, T (n)}$ este delimitat asimptotic conform unuia dintre următoarele trei cazuri:

dacă există o constantă $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ astfel încât $f(n)=O\left(n^{\log _{b}a-\varepsilon }\right)$ ${\ displaystyle f (n) = O \ left (n ^ {\ log _ {b} a- \ varepsilon} \ right)}$ ${\ displaystyle f (n) = O \ left (n ^ {\ log _ {b} a- \ varepsilon} \ right)}$ , asa de $T(n)=\Theta \left(n^{\log _{b}a}\right)$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ ;
de sine $f(n)=\Theta \left(n^{\log _{b}a}\right)$ ${\ displaystyle f (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ ${\ displaystyle f (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ asa de $T(n)=\Theta \left(n^{\log _{b}a}\log n\right)$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log n \ right)}$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log n \ right)}$ ;
dacă există o constantă $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ astfel încât $f(n)=\Omega \left(n^{\log _{b}a+\varepsilon }\right)$ ${\ displaystyle f (n) = \ Omega \ left (n ^ {\ log _ {b} a + \ varepsilon} \ right)}$ ${\ displaystyle f (n) = \ Omega \ left (n ^ {\ log _ {b} a + \ varepsilon} \ right)}$ și există o constantă $0<c<1$ ${\ displaystyle 0 <c <1}$ ${\ displaystyle 0 <c <1}$ și un întreg $n_{0}$ ${\ displaystyle n_ {0}}$ $n_ {0}$ astfel încât $\forall n\geq n_{0}\colon af\left({\frac {n}{b}}\right)\leq cf(n)$ ${\ displaystyle \ forall n \ geq n_ {0} \ colon af \ left ({\ frac {n} {b}} \ right) \ leq cf (n)}$ ${\ displaystyle \ forall n \ geq n_ {0} \ colon af \ left ({\ frac {n} {b}} \ right) \ leq cf (n)}$ , asa de $T(n)=\Theta (f(n))$ ${\ displaystyle T (n) = \ Theta (f (n))}$ ${\ displaystyle T (n) = \ Theta (f (n))}$ . ^[5]

Demonstrație

Lemă

Suma $s(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)$ ${\ displaystyle s (n) = \ sum _ {i = 0} ^ {\ log _ {b} n} a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ dreapta)}$ ${\ displaystyle s (n) = \ sum _ {i = 0} ^ {\ log _ {b} n} a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ dreapta)}$ definit pe puterile de $b$ ${\ displaystyle b}$ $b$ , unde este $a\geq 1$ ${\ displaystyle a \ geq 1}$ $a \ geq 1$ Și $b>1$ ${\ displaystyle b> 1}$ $b> 1$ sunt constante și $f$ ${\ displaystyle f}$ $f$ este non-negativ, are respectiv un comportament asimptotic:

sub ipoteza cazului 1 al teoremei principale, $s(n)=\Theta \left(n^{\log _{b}a}\right)$ ${\ displaystyle s (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ ${\ displaystyle s (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ right)}$ ;
sub ipoteza cazului 2 al teoremei principale, $s(n)=\Theta \left(n^{\log _{b}a}\log n\right)$ ${\ displaystyle s (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log n \ right)}$ ${\ displaystyle s (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log n \ right)}$ ;
sub ipoteza cazului 3 al teoremei principale, dacă există o constantă $0<c<1$ ${\ displaystyle 0 <c <1}$ ${\ displaystyle 0 <c <1}$ și un întreg $n_{0}$ ${\ displaystyle n_ {0}}$ $n_ {0}$ astfel încât $\forall n\geq n_{0}\colon af\left({\frac {n}{b}}\right)\leq cf(n)\;$ ${\ displaystyle \ forall n \ geq n_ {0} \ colon af \ left ({\ frac {n} {b}} \ right) \ leq cf (n) \;}$ ${\ displaystyle \ forall n \ geq n_ {0} \ colon af \ left ({\ frac {n} {b}} \ right) \ leq cf (n) \;}$ , asa de $s(n)=\Theta \left(f(n)\right)$ ${\ displaystyle s (n) = \ Theta \ left (f (n) \ right)}$ ${\ displaystyle s (n) = \ Theta \ left (f (n) \ right)}$ .

Demonstrație

Cazul 1

Pentru cazul 1, ipoteza implică

f\left({\frac {n}{b^{j}}}\right)=O\left(\left({\frac {n}{b^{j}}}\right)^{\log _{b}a-\varepsilon }\right)

{\ displaystyle f \ left ({\ frac {n} {b ^ {j}}} \ right) = O \ left (\ left ({\ frac {n} {b ^ {j}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ right)}

{\ displaystyle f \ left ({\ frac {n} {b ^ {j}}} \ right) = O \ left (\ left ({\ frac {n} {b ^ {j}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ right)}

care a înlocuit în $s$ ${\ displaystyle s}$ $s$ conduce la

s(n)=O\left(\sum _{i=0}^{\log _{b}n-1}a^{i}\left({\frac {n}{b^{i}}}\right)^{\log _{b}a-\varepsilon }\right)

{\ displaystyle s (n) = O \ left (\ sum _ {i = 0} ^ {\ log _ {b} n-1} a ^ {i} \ left ({\ frac {n} {b ^ { i}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ right)}

{\ displaystyle s (n) = O \ left (\ sum _ {i = 0} ^ {\ log _ {b} n-1} a ^ {i} \ left ({\ frac {n} {b ^ { i}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ right)}

.

Colectând factorii comuni, simplificând și însumând seriile geometrice trunchiate rezultate, avem

s(n)=O\left(n^{\log _{b}a-\varepsilon }\left({\frac {n^{\varepsilon }-1}{b^{\varepsilon }-1}}\right)\right)

{\ displaystyle s (n) = O \ left (n ^ {\ log _ {b} a- \ varepsilon} \ left ({\ frac {n ^ {\ varepsilon} -1} {b ^ {\ varepsilon} - 1}} \ right) \ right)}

{\ displaystyle s (n) = O \ left (n ^ {\ log _ {b} a- \ varepsilon} \ left ({\ frac {n ^ {\ varepsilon} -1} {b ^ {\ varepsilon} - 1}} \ right) \ right)}

.

Atâta timp cât $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ Și $b$ ${\ displaystyle b}$ $b$ sunt constante, da

n^{\log _{b}a-\varepsilon }\left({\frac {n^{\varepsilon }-1}{b^{\varepsilon }-1}}\right)=n^{\log _{b}a-\varepsilon }O\left(n^{\varepsilon }\right)=O\left(n^{log_{b}a}\right)

{\ displaystyle n ^ {\ log _ {b} a- \ varepsilon} \ left ({\ frac {n ^ {\ varepsilon} -1} {b ^ {\ varepsilon} -1}} \ right) = n ^ {\ log _ {b} a- \ varepsilon} O \ left (n ^ {\ varepsilon} \ right) = O \ left (n ^ {log_ {b} a} \ right)}

{\ displaystyle n ^ {\ log _ {b} a- \ varepsilon} \ left ({\ frac {n ^ {\ varepsilon} -1} {b ^ {\ varepsilon} -1}} \ right) = n ^ {\ log _ {b} a- \ varepsilon} O \ left (n ^ {\ varepsilon} \ right) = O \ left (n ^ {log_ {b} a} \ right)}

,

și prin faptul că, din moment ce $f(1)$ ${\ displaystyle f (1)}$ ${\ displaystyle f (1)}$ este o constantă,

s(n)\geq a^{\log _{b}n}f(1)=f(1)n^{\log _{b}a}\to s(n)\in \Omega (n^{\log _{b}a})

{\ displaystyle s (n) \ geq a ^ {\ log _ {b} n} f (1) = f (1) n ^ {\ log _ {b} a} \ to s (n) \ in \ Omega (n ^ {\ log _ {b} a})}

{\ displaystyle s (n) \ geq a ^ {\ log _ {b} n} f (1) = f (1) n ^ {\ log _ {b} a} \ to s (n) \ in \ Omega (n ^ {\ log _ {b} a})}

care împreună dau

s(n)\in \Theta (n^{\log _{b}a})

{\ displaystyle s (n) \ in \ Theta (n ^ {\ log _ {b} a})}

{\ displaystyle s (n) \ in \ Theta (n ^ {\ log _ {b} a})}

de aici teza.

Cazul 2

Similar cazului 1, pentru cazul 2 presupune ipoteza

f\left({\frac {n}{b^{j}}}\right)=\Theta \left(\left({\frac {n}{b^{j}}}\right)^{\log _{b}a}\right)

{\ displaystyle f \ left ({\ frac {n} {b ^ {j}}} \ right) = \ Theta \ left (\ left ({\ frac {n} {b ^ {j}}} \ right) ^ {\ log _ {b} a} \ right)}

{\ displaystyle f \ left ({\ frac {n} {b ^ {j}}} \ right) = \ Theta \ left (\ left ({\ frac {n} {b ^ {j}}} \ right) ^ {\ log _ {b} a} \ right)}

care a înlocuit în $s$ ${\ displaystyle s}$ $s$ conduce la

s(n)=\Theta \left(\sum _{i=0}^{\log _{b}n-1}a^{i}\left({\frac {n}{b^{i}}}\right)^{\log _{b}a}\right)

{\ displaystyle s (n) = \ Theta \ left (\ sum _ {i = 0} ^ {\ log _ {b} n-1} a ^ {i} \ left ({\ frac {n} {b ^ {i}}} \ right) ^ {\ log _ {b} a} \ right)}

{\ displaystyle s (n) = \ Theta \ left (\ sum _ {i = 0} ^ {\ log _ {b} n-1} a ^ {i} \ left ({\ frac {n} {b ^ {i}}} \ right) ^ {\ log _ {b} a} \ right)}

.

Procedăm similar cu cazul precedent, totuși seria trunchiată obținută nu este o serie geometrică, ci o serie cu termeni constanți

n^{log_{b}a}\sum _{i=0}^{\log _{b}n-1}1=n^{log_{b}a}\log _{b}n

{\ displaystyle n ^ {log_ {b} a} \ sum _ {i = 0} ^ {\ log _ {b} n-1} 1 = n ^ {log_ {b} a} \ log _ {b} n }

{\ displaystyle n ^ {log_ {b} a} \ sum _ {i = 0} ^ {\ log _ {b} n-1} 1 = n ^ {log_ {b} a} \ log _ {b} n }

de aici teza.

Cazul 3

Aplicând iterativ $the$ ${\ displaystyle i}$ $the$ ori ipoteza regularității cazului 3, avem

a^{i}f\left({\frac {n}{b^{i}}}\right)\leq c^{i}f(n)

{\ displaystyle a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ right) \ leq c ^ {i} f (n)}

{\ displaystyle a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ right) \ leq c ^ {i} f (n)}

pentru valori suficient de mari de $n$ ${\ displaystyle n}$ $n$ . Prin urmare, această condiție se aplică tuturor, dar cel mult un număr constant de termeni, pentru care $n$ ${\ displaystyle n}$ $n$ nu este suficient de mare. În mod similar cu cazurile anterioare, acesta este substituit în definiția lui $s$ ${\ displaystyle s}$ $s$ , primind

s(n)\leq \sum _{i=0}^{\log _{b}n}c^{i}f(n)+O(1)\leq f(n)\sum _{i=0}^{\infty }c^{i}+O(1)

{\ displaystyle s (n) \ leq \ sum _ {i = 0} ^ {\ log _ {b} n} c ^ {i} f (n) + O (1) \ leq f (n) \ sum _ {i = 0} ^ {\ infty} c ^ {i} + O (1)}

{\ displaystyle s (n) \ leq \ sum _ {i = 0} ^ {\ log _ {b} n} c ^ {i} f (n) + O (1) \ leq f (n) \ sum _ {i = 0} ^ {\ infty} c ^ {i} + O (1)}

unde este $O(1)$ ${\ displaystyle O (1)}$ $O (1)$ reprezintă termenii menționați anterior pentru care inegalitatea nu se menține. Prin adăugarea seriei geometrice pe care o avem

s(n)=f(n)\left({\frac {1}{1-c}}\right)+O(1)=O\left(f(n)\right)

{\ displaystyle s (n) = f (n) \ left ({\ frac {1} {1-c}} \ right) + O (1) = O \ left (f (n) \ right)}

{\ displaystyle s (n) = f (n) \ left ({\ frac {1} {1-c}} \ right) + O (1) = O \ left (f (n) \ right)}

și din moment ce definiția lui $s$ ${\ displaystyle s}$ $s$ conține $f$ ${\ displaystyle f}$ $f$ într-o sumă non-negativă, avem și $s(n)=\Omega \left(f(n)\right)$ ${\ displaystyle s (n) = \ Omega \ left (f (n) \ right)}$ ${\ displaystyle s (n) = \ Omega \ left (f (n) \ right)}$ . Combinând cele două limitări asimptotice, avem $s(n)=\Theta \left(f(n)\right)$ ${\ displaystyle s (n) = \ Theta \ left (f (n) \ right)}$ ${\ displaystyle s (n) = \ Theta \ left (f (n) \ right)}$ . ^[6]

Dovada teoremei principale

În cazul particular în care $T.$ ${\ displaystyle T}$ $T.$ este definit numai pe puterile exacte ale $b$ ${\ displaystyle b}$ $b$ , analizând arborele recursiv în raport cu relația de recurență observăm că ^[7]

T(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)+\Theta \left(n^{\log _{b}a}\right)

{\ displaystyle T (n) = \ sum _ {i = 0} ^ {\ log _ {b} n} a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ dreapta) + \ Theta \ left (n ^ {\ log _ {b} a} \ right)}

{\ displaystyle T (n) = \ sum _ {i = 0} ^ {\ log _ {b} n} a ^ {i} f \ left ({\ frac {n} {b ^ {i}}} \ dreapta) + \ Theta \ left (n ^ {\ log _ {b} a} \ right)}

.

Prin urmare, aplicând lema demonstrată mai sus, validitatea teoremei principale este imediat obținută în cazul particular în care $n$ ${\ displaystyle n}$ $n$ este definit pe puterile lui $b$ ${\ displaystyle b}$ $b$ . Acest lucru, evident, nu este suficient pentru a demonstra teorema, dar poate fi extins la cazul general, luând în considerare cazul în care apar părți superioare sau inferioare întregi .

În cazul unui număr întreg superior, atunci când se analizează arborele de recurență la apelul j- - lea argumentul ia forma

n_{i}={\begin{cases}n\quad &i=0\\\lceil {\frac {n_{i-1}}{b}}\rceil &i>0\end{cases}}

{\ displaystyle n_ {i} = {\ begin {cases} n \ quad & i = 0 \\\ lceil {\ frac {n_ {i-1}} {b}} \ rceil & i> 0 \ end {cases }}}

{\ displaystyle n_ {i} = {\ begin {cases} n \ quad & i = 0 \\\ lceil {\ frac {n_ {i-1}} {b}} \ rceil & i> 0 \ end {cases }}}

.

Întrucât din definiția întregii părți superioare avem $\lceil x\rceil \leq x+1$ ${\ displaystyle \ lceil x \ rceil \ leq x + 1}$ ${\ displaystyle \ lceil x \ rceil \ leq x + 1}$ , primesti

n_{i}\leq {\frac {n}{b^{i}}}+\sum _{i=0}^{i-1}{\frac {1}{b^{i}}}<{\frac {n}{b^{i}}}+{\frac {b}{b-1}}

{\ displaystyle n_ {i} \ leq {\ frac {n} {b ^ {i}}} + \ sum _ {i = 0} ^ {i-1} {\ frac {1} {b ^ {i} }} <{\ frac {n} {b ^ {i}}} + {\ frac {b} {b-1}}}

{\ displaystyle n_ {i} \ leq {\ frac {n} {b ^ {i}}} + \ sum _ {i = 0} ^ {i-1} {\ frac {1} {b ^ {i} }} <{\ frac {n} {b ^ {i}}} + {\ frac {b} {b-1}}}

.

Din aceasta se observă că $n_{\lfloor \log _{b}n\rfloor }=O(1)$ ${\ displaystyle n _ {\ lfloor \ log _ {b} n \ rfloor} = O (1)}$ ${\ displaystyle n _ {\ lfloor \ log _ {b} n \ rfloor} = O (1)}$ , apoi la profunzimea recursivității $\lfloor \log _{b}n\rfloor$ ${\ displaystyle \ lfloor \ log _ {b} n \ rfloor}$ ${\ displaystyle \ lfloor \ log _ {b} n \ rfloor}$ costul problemei este limitat de o constantă. Generalizăm apoi prima ecuație pentru $n$ ${\ displaystyle n}$ $n$ arbitrar, nu mai este limitat la puterile $b$ ${\ displaystyle b}$ $b$

T(n)=\sum _{i=0}^{\lfloor \log _{b}n\rfloor }a^{i}f\left(n_{i}\right)+\Theta \left(n^{\log _{b}a}\right)

{\ displaystyle T (n) = \ sum _ {i = 0} ^ {\ lfloor \ log _ {b} n \ rfloor} a ^ {i} f \ left (n_ {i} \ right) + \ Theta \ stânga (n ^ {\ log _ {b} a} \ dreapta)}

{\ displaystyle T (n) = \ sum _ {i = 0} ^ {\ lfloor \ log _ {b} n \ rfloor} a ^ {i} f \ left (n_ {i} \ right) + \ Theta \ stânga (n ^ {\ log _ {b} a} \ dreapta)}

și putem continua să studiem suma. Al treilea caz continuă exact în același mod ca al treilea caz al lemei. Pentru al doilea caz, din definiția lui O-mare și amintind expresia lui $n_{i}$ ${\ displaystyle n_ {i}}$ $n_i$ avem că există o constantă $c>0$ ${\ displaystyle c> 0}$ $c> 0$ și un întreg $n_{0}$ ${\ displaystyle n_ {0}}$ $n_ {0}$ astfel încât, pentru $n\geq n_{0}$ ${\ displaystyle n \ geq n_ {0}}$ ${\ displaystyle n \ geq n_ {0}}$

f\left(n_{i}\right)\leq c\left({\frac {n}{b^{i}}}+{\frac {b}{b-1}}\right)^{\log _{b}a}\leq c\left({\frac {n^{\log _{b}a}}{a^{i}}}\right)\left(1+{\frac {b}{b-1}}\right)^{\log _{b}a}=O\left({\frac {n^{\log _{b}a}}{a^{i}}}\right)

{\ displaystyle f \ left (n_ {i} \ right) \ leq c \ left ({\ frac {n} {b ^ {i}}} + {\ frac {b} {b-1}} \ right) ^ {\ log _ {b} a} \ leq c \ left ({\ frac {n ^ {\ log _ {b} a}} {a ^ {i}}} \ right) \ left (1 + {\ frac {b} {b-1}} \ right) ^ {\ log _ {b} a} = O \ left ({\ frac {n ^ {\ log _ {b} a}} {a ^ {i} }} \ dreapta)}

{\ displaystyle f \ left (n_ {i} \ right) \ leq c \ left ({\ frac {n} {b ^ {i}}} + {\ frac {b} {b-1}} \ right) ^ {\ log _ {b} a} \ leq c \ left ({\ frac {n ^ {\ log _ {b} a}} {a ^ {i}}} \ right) \ left (1 + {\ frac {b} {b-1}} \ right) ^ {\ log _ {b} a} = O \ left ({\ frac {n ^ {\ log _ {b} a}} {a ^ {i} }} \ dreapta)}

.

Limita asimptotică obținută ne permite apoi să procedăm în același mod ca în cazul 2 al lemei. Pentru primul caz, într-un mod similar cu ceea ce tocmai s-a făcut, se arată că

f\left(n_{i}\right)=O\left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}a-\varepsilon }\right)

{\ displaystyle f \ left (n_ {i} \ right) = O \ left (\ left ({left {{frac {n} {b ^ {i}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ dreapta)}

{\ displaystyle f \ left (n_ {i} \ right) = O \ left (\ left ({left {{frac {n} {b ^ {i}}} \ right) ^ {\ log _ {b} a- \ varepsilon} \ dreapta)}

ceea ce ne permite apoi să procedăm într-un mod similar cu cazul 1 al lemei. Aceasta completează dovada teoremei principale în cazul unui număr întreg superior, în cazul numărului întreg inferior proba este analogă. ^[8]

Generalizări

Al doilea caz al teoremei principale poate fi generalizat prin substituirea doar a ipotezei sale particulare, $f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)$ ${\ displaystyle f (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log ^ {k} n \ right)}$ ${\ displaystyle f (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log ^ {k} n \ right)}$ pentru unii $k\geq 0$ ${\ displaystyle k \ geq 0}$ ${\ displaystyle k \ geq 0}$ și teza $T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log ^ {k + 1} n \ right)}$ ${\ displaystyle T (n) = \ Theta \ left (n ^ {\ log _ {b} a} \ log ^ {k + 1} n \ right)}$ . ^[9] După cum vedem, cazul non-general este pentru $k=0$ ${\ displaystyle k = 0}$ $k = 0$ .

Teorema Akra-Bazzi generalizează teorema principală, sub ipoteze adecvate, pentru relațiile de recurență în formă $T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))$ ${\ displaystyle T (x) = g (x) + \ sum _ {i = 1} ^ {k} a_ {i} T (b_ {i} x + h_ {i} (x))}$ ${\ displaystyle T (x) = g (x) + \ sum _ {i = 1} ^ {k} a_ {i} T (b_ {i} x + h_ {i} (x))}$ .

Exemple

Cazul 1

Să se dea următoarea relație de recurență:

T_{A}(n)=9\,T_{A}\left({\frac {n}{3}}\right)+n.

{\ displaystyle T_ {A} (n) = 9 \, T_ {A} \ left ({\ frac {n} {3}} \ right) + n.}

T_ {A} (n) = 9 \, T_ {A} \ left ({\ frac {n} {3}} \ right) + n.

Da, da $a=9$ ${\ displaystyle a = 9}$ $a = 9$ , $b=3$ ${\ displaystyle b = 3}$ $b = 3$ Și $f(n)=n$ ${\ displaystyle f (n) = n}$ $f (n) = n$ . Atunci $n^{log_{b}a}=n^{log_{3}9}=\Theta \left(n^{2}\right).$ ${\ displaystyle n ^ {log_ {b} a} = n ^ {log_ {3} 9} = \ Theta \ left (n ^ {2} \ right).}$ $n ^ {{log_ {b} a}} = n ^ {{log_ {3} 9}} = \ Theta \ left (n ^ {2} \ right).$ De cand $f(n)=O\left(n^{log_{3}9-\varepsilon }\right)$ ${\ displaystyle f (n) = O \ left (n ^ {log_ {3} 9- \ varepsilon} \ right)}$ $f (n) = O \ left (n ^ {{log_ {3} 9- \ varepsilon}} \ right)$ când ε = 1 , este posibil să se aplice cazul 1 al teoremei master care obține soluția

T_{A}(n)=\Theta \left(n^{2}\right).

{\ displaystyle T_ {A} (n) = \ Theta \ left (n ^ {2} \ right).}

T_ {A} (n) = \ Theta \ left (n ^ {2} \ right).

Cazul 2

Acum să se dea relația de recurență:

T_{A}(n)=T_{A}\left({\frac {2\,n}{3}}\right)+1,

{\ displaystyle T_ {A} (n) = T_ {A} \ left ({\ frac {2 \, n} {3}} \ right) +1,}

T_ {A} (n) = T_ {A} \ left ({\ frac {2 \, n} {3}} \ right) +1,

in care $a=1$ ${\ displaystyle a = 1}$ $a = 1$ , $b=3/2$ ${\ displaystyle b = 3/2}$ $b = 3/2$ Și $f(n)=1$ ${\ displaystyle f (n) = 1}$ $f (n) = 1$ . Fiind $n^{log_{b}a}=n^{log_{3/2}1}=\Theta (n^{0})=\Theta (1)$ ${\ displaystyle n ^ {log_ {b} a} = n ^ {log_ {3/2} 1} = \ Theta (n ^ {0}) = \ Theta (1)}$ $n ^ {{log_ {b} a}} = n ^ {{log _ {{3/2}} 1}} = \ Theta (n ^ {0}) = \ Theta (1)$ și $f(n)=1$ ${\ displaystyle f (n) = 1}$ $f (n) = 1$ , cazul 2 din Teorema Maestră se menține , conducând la soluție $T_{A}(n)=\Theta (log_{2}n).$ ${\ displaystyle T_ {A} (n) = \ Theta (log_ {2} n).}$ $T_ {A} (n) = \ Theta (log_ {2} n).$

Cazul 3

În cele din urmă, relația de recurență este dată:

T_{A}(n)=3\,T_{A}\left({\frac {n}{4}}\right)+n\log n.

{\ displaystyle T_ {A} (n) = 3 \, T_ {A} \ left ({\ frac {n} {4}} \ right) + n \ log n.}

{\ displaystyle T_ {A} (n) = 3 \, T_ {A} \ left ({\ frac {n} {4}} \ right) + n \ log n.}

in care $a=3$ ${\ displaystyle a = 3}$ $a = 3$ , $b=4$ ${\ displaystyle b = 4}$ $b = 4$ Și $f(n)=n\log n$ ${\ displaystyle f (n) = n \ log n}$ ${\ displaystyle f (n) = n \ log n}$ . Fiind $n^{log_{b}a}=n^{log_{4}3}=O\left(n^{0.793}\right)$ ${\ displaystyle n ^ {log_ {b} a} = n ^ {log_ {4} 3} = O \ left (n ^ {0.793} \ right)}$ $n ^ {{log_ {b} a}} = n ^ {{log_ {4} 3}} = O \ left (n ^ {{0.793}} \ right)$ și $f(n)=\Omega \left(n^{\log _{4}3+\varepsilon }\right)$ ${\ displaystyle f (n) = \ Omega \ left (n ^ {\ log _ {4} 3+ \ varepsilon} \ right)}$ $f (n) = \ Omega \ left (n ^ {{\ log _ {4} 3+ \ varepsilon}} \ right)$ , în care ε ≈ 0,2, cazul 3 al teoremei master poate fi aplicat numai dacă condiția de regularitate este valabilă pentru $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ . Pentru n suficient de mare avem $3\left({\frac {n}{4}}\right)\log \left({\frac {n}{4}}\right)\leq \left({\frac {3}{4}}n\log n\right)=cf(n)$ ${\ displaystyle 3 \ left ({\ frac {n} {4}} \ right) \ log \ left ({\ frac {n} {4}} \ right) \ leq \ left ({\ frac {3} { 4}} n \ log n \ right) = cf (n)}$ ${\ displaystyle 3 \ left ({\ frac {n} {4}} \ right) \ log \ left ({\ frac {n} {4}} \ right) \ leq \ left ({\ frac {3} { 4}} n \ log n \ right) = cf (n)}$ pentru $c=3/4\leq 1$ ${\ displaystyle c = 3/4 \ leq 1}$ $c = 3/4 \ leq 1$ . În consecință, soluția recurenței este $T_{A}(n)=\Theta (n\log n).$ ${\ displaystyle T_ {A} (n) = \ Theta (n \ log n).}$ ${\ displaystyle T_ {A} (n) = \ Theta (n \ log n).}$

Notă

^ Acesta este sensul original al termenului stăpân în nume.
^ Jon Louis Bentley , Dorothea Haken și James B. Saxe , O metodă generală pentru rezolvarea recidivelor de divizare și cucerire , în ACM SIGACT News , vol. 12, nr. 3, septembrie 1980, pp. 36–44, DOI : 10.1145 / 1008861.1008865 .
^ Cormen și colab. , pp. 94-95 .
^ Având în vedere un algoritm recursiv asociat cu relația de recurență, cantitățile implicate pot fi interpretate ca:
- $n$ ${\ displaystyle n}$ $n$ este dimensiunea intrării;
- $la$ ${\ displaystyle a}$ $la$ este numărul de apeluri recursive către algoritm;
- ${\frac {n}{b}}$ ${\ displaystyle {\ frac {n} {b}}}$ ${\ frac {n} {b}}$ este dimensiunea apelului recursiv (adică porțiunea problemei inițiale reprezentată în fiecare subproblemă);
- $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este funcția de cost a subdiviziunii problemei și a fazei de reconstrucție a soluției.
^ Cormen și colab. , p. 94 .
^ Cormen și colab. , pp. 100-102 .
^ Cormen și colab. , pp. 98-100 .
^ Cormen și colab. , pp. 103-106 .
^ Goodrich & Tamassia , pp. 268-270 .

Bibliografie

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introducere în algoritmi , ediția a III-a, MIT Press, 2009, pp. 93 -106, ISBN 978-0-262-53305-8 .
Michael T. Goodrich și Roberto Tamassia , Algorithm Design: Foundation, Analysis, and Internet Example , Wiley, 2002, ISBN 0-471-38365-1 .

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Acesta este sensul original al termenului stăpân în nume.

[2] Jon Louis Bentley , Dorothea Haken și James B. Saxe , O metodă generală pentru rezolvarea recidivelor de divizare și cucerire , în ACM SIGACT News , vol. 12, nr. 3, septembrie 1980, pp. 36–44, DOI : 10.1145 / 1008861.1008865 .

[3] Cormen și colab. , pp. 94-95 .

[4] Având în vedere un algoritm recursiv asociat cu relația de recurență, cantitățile implicate pot fi interpretate ca:
$n$ ${\ displaystyle n}$ $n$ este dimensiunea intrării;
$la$ ${\ displaystyle a}$ $la$ este numărul de apeluri recursive către algoritm;
${\frac {n}{b}}$ ${\ displaystyle {\ frac {n} {b}}}$ ${\ frac {n} {b}}$ este dimensiunea apelului recursiv (adică porțiunea problemei inițiale reprezentată în fiecare subproblemă);
$f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este funcția de cost a subdiviziunii problemei și a fazei de reconstrucție a soluției.

[5] $n$ ${\ displaystyle n}$ $n$ este dimensiunea intrării;

[6] $la$ ${\ displaystyle a}$ $la$ este numărul de apeluri recursive către algoritm;

[7] ${\frac {n}{b}}$ ${\ displaystyle {\ frac {n} {b}}}$ ${\ frac {n} {b}}$ este dimensiunea apelului recursiv (adică porțiunea problemei inițiale reprezentată în fiecare subproblemă);

[8] $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ este funcția de cost a subdiviziunii problemei și a fazei de reconstrucție a soluției.

[5] Cormen și colab. , p. 94 .

[6] Cormen și colab. , pp. 100-102 .

[7] Cormen și colab. , pp. 98-100 .

[8] Cormen și colab. , pp. 103-106 .

[9] Goodrich & Tamassia , pp. 268-270 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]