Мастер теорема
У анализи алгоритама мастер теорема представља основу за решавање рекурентних једначина које се јављају при анализи многих подели-па-владај алгоритама. Представљена је и доказана у књизи 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 који му је прослеђен од родитеља и представљен са . Укупан посао који обави цело дрво је сума послова које обави сваки чвор.

Овакви алгоритми могу да се представе рекурентном једначином . Ова рекурзивна једначина се може сукцесивно заменити сама у себе и проширити у израз који представља укупан одрађени посао.

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

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

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

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

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

Први случај

Генерички облик 
Ако  где је  (користећи О-нотацију)

следи да је:

Пример 

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

, где је 

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

, дакле: 

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

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

Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .

Други случај

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

 где је 

следи:

Пример 

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

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

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

 

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

Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .

Трећи случај

Генерички облик 
Ако је тачно:

 где је 

следи:

Пример 

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

, где је 

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

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

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

Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .

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

 
 a није константа
 
 неполиномијална разлика између f(n) и  (погледај испод)
 
 a<1 не може имати мање од једног подпроблема
 
 f(n) није позитивна
 
 трећи случај, али није исправно

У другом примеру изнад разлика између  и  може се изразити односом . Јасно је да  за било коју константу . Стога, разлика није полиномијална и мастер теорема не важи.

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

Референце 

Информатика
Алгоритми
Теорија комплексности
У анализи алгоритама мастер теорема представља основу за решавање рекурентних једначина које се јављају при анализи многих подели-па-владај алгоритама . Представљена је и доказана у књизи Introduction to Algorithms коју су написали Кормен ( ) , Лисерсон ( ) , Риверст ( ) и Стеин ( ) . Не могу се све рекурентне једначине решити мастер теоремом . Генерализација мастер теореме обухвата Акра-Бази метод . Увод Разматрамо проблем који се може решити следећим рекурзивним алгоритмом : procedure T( n \ : size of problem ) defined as : if n <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 који му је прослеђен од родитеља и представљен са \ . Укупан посао који обави цело дрво је сума послова које обави сваки чвор . Овакви алгоритми могу да се представе рекурентном једначином \ . Ова рекурзивна једначина се може сукцесивно заменити сама у себе и проширити у израз који представља укупан одрађени посао . На овај начин се , користећи мастер теорему , лако може израчунати време извршавања оваквих рекурзивних алгоритама и представити у О-нотацији без развијања рекурентне једначине . Генерички облик Мастер теорема решава рекурентне једначине следећег облика : Константе и функције имају следећи значај : n -величина проблема. a -број подпроблема у рекурзији. n /b -величина сваког подпроблема ( Овде се претпоставља да су сви подпроблеми у суштини исте величине ) . f ( n ) -цена операција обављених ван рекурзивних позива( обухвата операције дељења проблема на подпроблеме и спајања решења добијених као решења подпроблема ) . Може се одредити асимптотска граница у следећа три случаја : Први случај Генерички облик Ако где је ( користећи О-нотацију ) следи да је : Пример Из горње једначине се може закључити да променљиве узимају следеће вредности : где је Даље проверавамо да ли је задовољен услов првог случаја мастер теореме : дакле : Задовољен је услов , па из првог случаја мастер теореме следи : Према томе , дата рекурентна једначина T( n ) припада Θ( n3 ) . Овај резултат се може потврдити директним решавањем рекурентне једначине : , под претпоставком да је \ . Други случај Генерички облик Ако за неку константу k ≥ 0 , важи да је : где је следи : Пример Из претходне једначине променљиве узимају следеће вредности : где је Даље проверавамо да ли је задовољен услов друог случаја мастер теореме : дакле : Задовољен је услов , па из другог случаја мастер теореме следи : Према томе , дата рекурентна једначина T( n ) припада Θ( n log n ) . Овај резултат се може потврдити директним решавањем рекурентне једначине : , под претпоставком да је \ . Трећи случај Генерички облик Ако је тачно : где је следи : Пример Из претходне једначине променљиве узимају следеће вредности : где је Даље проверавамо да ли је задовољен услов трећег случаја мастер теореме : дакле : Задовољен је услов , па из трћег случаја мастер теореме следи : Према томе , дата рекурентна једначина T( n ) припада Θ( n2 ) , што је у складу са f ( n ) из почетне једначине . Овај резултат се може потврдити директним решавањем рекурентне једначине : , под претпоставком да је \ . Примери нерешивих једначина Следеће једначине се не могу решити мастер теоремом : a није константа неполиномијална разлика између f( n ) и ( погледај испод ) a<1 не може имати мање од једног подпроблема f( n ) није позитивна трећи случај , али није исправно У другом примеру изнад разлика између и може се изразити односом \ . Јасно је да за било коју константу \ . Стога , разлика није полиномијална и мастер теорема не важи . Примена на познате алгоритме Референце Информатика Алгоритми Теорија комплексности