Мастер теорема

У анализи алгоритама мастер теорема представља основу за решавање рекурентних једначина које се јављају при анализи многих подели-па-владај алгоритама. Представљена је и доказана у књизи Introduction to Algorithms коју су написали Кормен (енгл. Cormen) , Лисерсон (енгл. Leiserson) , Риверст (енгл. Rivest) и Стеин (енгл. Stein). Не могу се све рекурентне једначине решити мастер теоремом. Генерализација мастер теореме обухвата Акра-Бази метод.

Увод

Разматрамо проблем који се може решити следећим рекурзивним алгоритмом:

 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

У горњем алгоритму проблем рекурзивно делимо на низ подпроблема величине n/b. Ово се може замислити као формирање стабла у коме сваки чвор представља један рекурзивни позив, а његова деца даље рекурзивне позиве у оквиру текућег позива. Сваки од чворова обавља део посла у зависности од величине подпроблема n који му је прослеђен од родитеља и представљен са $f(n)$. Укупан посао који обави цело дрво је сума послова које обави сваки чвор.

Овакви алгоритми могу да се представе рекурентном једначином $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$. Ова рекурзивна једначина се може сукцесивно заменити сама у себе и проширити у израз који представља укупан одрађени посао.

На овај начин се, користећи мастер теорему, лако може израчунати време извршавања оваквих рекурзивних алгоритама и представити у О-нотацији без развијања рекурентне једначине.

Генерички облик

Мастер теорема решава рекурентне једначине следећег облика:

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

Константе и функције имају следећи значај:

• n -величина проблема.
• a -број подпроблема у рекурзији.
• n/b -величина сваког подпроблема (Овде се претпоставља да су сви подпроблеми у суштини исте величине).
• f (n) -цена операција обављених ван рекурзивних позива(обухвата операције дељења проблема на подпроблеме и спајања решења добијених као решења подпроблема).

Може се одредити асимптотска граница у следећа три случаја:

Први случај

Генерички облик

Ако $f(n)=\Theta \left(n^{c}\right)$ где је $c<\log _{b}a$ (користећи О-нотацију)

следи да је:

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

Пример

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

Из горње једначине се може закључити да променљиве узимају следеће вредности:

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

$f(n)=\Theta \left(n^{c}\right)$, где је $c=2$

Даље проверавамо да ли је задовољен услов првог случаја мастер теореме:

$\log _{b}a=\log _{2}8=3$, дакле: $c<\log _{b}a$

Задовољен је услов, па из првог случаја мастер теореме следи:

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

Према томе, дата рекурентна једначина T(n) припада Θ(n³).

Овај резултат се може потврдити директним решавањем рекурентне једначине: $T(n)=1001n^{3}-1000n^{2}$, под претпоставком да је $T(1)=1$.

Други случај

Генерички облик

Ако за неку константу k ≥ 0, важи да је:

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ где је $c=\log _{b}a$

следи:

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

Пример

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

Из претходне једначине променљиве узимају следеће вредности:

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

$f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ где је $c=1,k=0$

Даље проверавамо да ли је задовољен услов друог случаја мастер теореме:

$\log _{b}a=\log _{2}2=1$, дакле: $c=\log _{b}a$

Задовољен је услов, па из другог случаја мастер теореме следи:

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

Према томе, дата рекурентна једначина T(n) припада Θ(n log n).

Овај резултат се може потврдити директним решавањем рекурентне једначине: $T(n)=n+10n\log _{2}n$, под претпоставком да је $T(1)=1$.

Трећи случај

Генерички облик

Ако је тачно:

$f(n)=\Theta \left(n^{c}\right)$ где је $c>\log _{b}a$

следи:

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

Пример

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

Из претходне једначине променљиве узимају следеће вредности:

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

$f(n)=\Theta \left(n^{c}\right)$, где је $c=2$

Даље проверавамо да ли је задовољен услов трећег случаја мастер теореме:

$\log _{b}a=\log _{2}2=1$, дакле: $c>\log _{b}a$

Задовољен је услов, па из трћег случаја мастер теореме следи:

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

Према томе, дата рекурентна једначина T(n) припада Θ(n²), што је у складу са f (n) из почетне једначине.

Овај резултат се може потврдити директним решавањем рекурентне једначине: $T(n)=2n^{2}-n$, под претпоставком да је $T(1)=1$.

Примери нерешивих једначина

Следеће једначине се не могу решити мастер теоремом:

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

  a није константа

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

  неполиномијална разлика између f(n) и $n^{\log _{b}a}$ (погледај испод)

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

  a<1 не може имати мање од једног подпроблема

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

  f(n) није позитивна

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

  трећи случај, али није исправно

У другом примеру изнад разлика између $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$. Стога, разлика није полиномијална и мастер теорема не важи.

Примена на познате алгоритме

Алгоритам	Рекурентна једначина	Време извршења	Коментар
Бинарна претрага	$T(n)=T\left({\frac {n}{2}}\right)+O(1)$	$O(\log n)$	Примењена мастер теорема случај: $c=\log _{b}a$, где је $a=1,b=2,c=0,k=0$
Бинарно стабло претраге	$T(n)=2T\left({\frac {n}{2}}\right)+O(1)$	$O(n)$	Примењена мастер теорема случај: $c<\log _{b}a$ где је $a=2,b=2,c=0$
Оптимална претрага сортиране матрице	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$O(n)$	Примењена Akra-Bazzi theorem за $p=1$ и $g(u)=\log(u)$ да се добије $\Theta (2n-\log n)$
Сортирање спајањем	$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$	$O(n\log n)$	Примењена мастер теорема случај: $c=\log _{b}a$, где је $a=2,b=2,c=1,k=0$