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

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

Увод

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

 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)=aT\left(\frac{n}{b}\right)+f(n)$. Ова рекурзивна једначина се може сукцесивно заменити сама у себе и проширити у израз који представља укупан одрађени посао.

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

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

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

$T(n)=aT\left(\frac{n}{b}\right)+f(n)\text{,}a\ge 1\text{, }b>1$

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

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

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

Први случај

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

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

следи да је:

$T(n)=\mathrm{\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)=\mathrm{\Theta }\left(n^c\right)$, где је $c=2$

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

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

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

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

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

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

Други случај

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

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

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

следи:

$T(n)=\mathrm{\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)=\mathrm{\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }^{k+1}n\right)=\mathrm{\Theta }\left(n^1{\log }^{1}n\right)=\mathrm{\Theta }(n\log n)$

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

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

Трећи случај

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

Ако је тачно:

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

следи:

$T\left(n\right)=\mathrm{\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)=\mathrm{\Theta }\left(n^c\right)$, где је $c=2$

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

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

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

$T\left(n\right)=\mathrm{\Theta }\left(n^c\right)=\mathrm{\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^{lo{g}_{2}2}}=\frac{n}{n\log n}=\frac{1}{\log n}$. Јасно је да $\frac{1}{\log n}<n^{ϵ}$ за било коју константу $ϵ>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)$ да се добије $\mathrm{\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$