Master teorema

U analizi algoritama master teorema predstavlja osnovu za rešavanje rekurentnih jednačina koje se javljaju pri analizi mnogih podeli-pa-vladaj algoritama. Predstavljena je i dokazana u knjizi Introduction to Algorithms koju su napisali Kormen (engl. Cormen) , Liserson (engl. Leiserson) , Riverst (engl. Rivest) i Stein (engl. Stein). Ne mogu se sve rekurentne jednačine rešiti master teoremom. Generalizacija master teoreme obuhvata Akra-Bazi metod.

Uvod

Razmatramo problem koji se može rešiti sledećim rekurzivnim algoritmom:

 procedure T(n : size of problem ) defined as:
   if n < 1 then exit


   Do work of amount f(n)


   T(n/b)
   T(n/b)
   ...repeat for a total of a times...
   T(n/b)
 end procedure

U gornjem algoritmu problem rekurzivno delimo na niz podproblema veličine n/b. Ovo se može zamisliti kao formiranje stabla u kome svaki čvor predstavlja jedan rekurzivni poziv, a njegova deca dalje rekurzivne pozive u okviru tekućeg poziva. Svaki od čvorova obavlja deo posla u zavisnosti od veličine podproblema n koji mu je prosleđen od roditelja i predstavljen sa $f(n)$. Ukupan posao koji obavi celo drvo je suma poslova koje obavi svaki čvor.

Ovakvi algoritmi mogu da se predstave rekurentnom jednačinom $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$. Ova rekurzivna jednačina se može sukcesivno zameniti sama u sebe i proširiti u izraz koji predstavlja ukupan odrađeni posao.

Na ovaj način se, koristeći master teoremu, lako može izračunati vreme izvršavanja ovakvih rekurzivnih algoritama i predstaviti u O-notaciji bez razvijanja rekurentne jednačine.

Generički oblik

Master teorema rešava rekurentne jednačine sledećeg oblika:

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

Konstante i funkcije imaju sledeći značaj:

• n -veličina problema.
• a -broj podproblema u rekurziji.
• n/b -veličina svakog podproblema (Ovde se pretpostavlja da su svi podproblemi u suštini iste veličine).
• f (n) -cena operacija obavljenih van rekurzivnih poziva(obuhvata operacije deljenja problema na podprobleme i spajanja rešenja dobijenih kao rešenja podproblema).

Može se odrediti asimptotska granica u sledeća tri slučaja:

Prvi slučaj

Generički oblik

Ako $f(n)=\Theta \left(n^{c}\right)$ gde je $c<\log _{b}a$ (koristeći O-notaciju)

sledi da je:

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

Primer

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

Iz gornje jednačine se može zaključiti da promenljive uzimaju sledeće vrednosti:

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

$f(n)=\Theta \left(n^{c}\right)$, gde je $c=2$

Dalje proveravamo da li je zadovoljen uslov prvog slučaja master teoreme:

$\log _{b}a=\log _{2}8=3$, dakle: $c<\log _{b}a$

Zadovoljen je uslov, pa iz prvog slučaja master teoreme sledi:

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

Prema tome, data rekurentna jednačina T(n) pripada Θ(n³).

Ovaj rezultat se može potvrditi direktnim rešavanjem rekurentne jednačine: $T(n)=1001n^{3}-1000n^{2}$, pod pretpostavkom da je $T(1)=1$.

Drugi slučaj

Generički oblik

Ako za neku konstantu k ≥ 0, važi da je:

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ gde je $c=\log _{b}a$

sledi:

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

Primer

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

Iz prethodne jednačine promenljive uzimaju sledeće vrednosti:

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

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ gde je $c=1,k=0$

Dalje proveravamo da li je zadovoljen uslov druog slučaja master teoreme:

$\log _{b}a=\log _{2}2=1$, dakle: $c=\log _{b}a$

Zadovoljen je uslov, pa iz drugog slučaja master teoreme sledi:

$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)$

Prema tome, data rekurentna jednačina T(n) pripada Θ(n log n).

Ovaj rezultat se može potvrditi direktnim rešavanjem rekurentne jednačine: $T(n)=n+10n\log _{2}n$, pod pretpostavkom da je $T(1)=1$.

Treći slučaj

Generički oblik

Ako je tačno:

$f(n)=\Theta \left(n^{c}\right)$ gde je $c>\log _{b}a$

sledi:

$T\left(n\right)=\Theta \left(n^{c}\right)$

Primer

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

Iz prethodne jednačine promenljive uzimaju sledeće vrednosti:

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

$f(n)=\Theta \left(n^{c}\right)$, gde je $c=2$

Dalje proveravamo da li je zadovoljen uslov trećeg slučaja master teoreme:

$\log _{b}a=\log _{2}2=1$, dakle: $c>\log _{b}a$

Zadovoljen je uslov, pa iz trćeg slučaja master teoreme sledi:

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

Prema tome, data rekurentna jednačina T(n) pripada Θ(n²), što je u skladu sa f (n) iz početne jednačine.

Ovaj rezultat se može potvrditi direktnim rešavanjem rekurentne jednačine: $T(n)=2n^{2}-n$, pod pretpostavkom da je $T(1)=1$.

Primeri nerešivih jednačina

Sledeće jednačine se ne mogu rešiti master teoremom:

• $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$

  a nije konstanta

• $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$

  nepolinomijalna razlika između f(n) i $n^{\log _{b}a}$ (pogledaj ispod)

• $T(n)=0.5T\left({\frac {n}{2}}\right)+n$

  a<1 ne može imati manje od jednog podproblema

• $T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$

  f(n) nije pozitivna

• $T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$

  treći slučaj, ali nije ispravno

U drugom primeru iznad razlika između $f(n)$ i $n^{\log _{b}a}$ može se izraziti odnosom ${\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}}$. Jasno je da ${\frac {1}{\log n}}<n^{\epsilon }$ za bilo koju konstantu $\epsilon >0$. Stoga, razlika nije polinomijalna i master teorema ne važi.

Primena na poznate algoritme

Algoritam	Rekurentna jednačina	Vreme izvršenja	Komentar
Binarna pretraga	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Primenjena master teorema slučaj: $c=\log _{b}a$, gde je $a=1,b=2,c=0,k=0$
Binarno stablo pretrage	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Primenjena master teorema slučaj: $c<\log _{b}a$ gde je $a=2,b=2,c=0$
Optimalna pretraga sortirane matrice	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Primenjena Akra-Bazzi theorem za $p=1$ i $g(u)=\log(u)$ da se dobije $\Theta (2n-\log n)$
Sortiranje spajanjem	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Primenjena master teorema slučaj: $c=\log _{b}a$, gde je $a=2,b=2,c=1,k=0$