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

У анализи алгоритама мастер теорема представља основу за решавање рекурентних једначина које се јављају при анализи многих подели-па-владај алгоритама. Представљена је и доказана у књизи 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 који му је прослеђен од родитеља и представљен са ${\displaystyle f(n)}$. Укупан посао који обави цело дрво је сума послова које обави сваки чвор.

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

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

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

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

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

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

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

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

следи да је:

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

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

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

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

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

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

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

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

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

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

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

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

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

следи:

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

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

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

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

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

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

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

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

${\displaystyle 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).

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

Ако је тачно:

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

следи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У другом примеру изнад разлика између ${\displaystyle f(n)}$ и ${\displaystyle n^{\log _{b}a}}$ може се изразити односом ${\displaystyle {\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}}}$. Јасно је да ${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$ за било коју константу ${\displaystyle \epsilon >0}$. Стога, разлика није полиномијална и мастер теорема не важи.

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