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

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

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

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

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

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

 

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

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

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

Први случајУреди

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

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

следи да је:

 

ПримерУреди

 

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

 
 , где је  

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

 , дакле:  

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

 

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

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

Други случајУреди

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

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

  где је  

следи:

 

ПримерУреди

 

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

 
  где је  

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

 , дакле:  

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

 

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

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

Трећи случајУреди

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

Ако је тачно:

  где је  

следи:

 

ПримерУреди

 

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

 
 , где је  

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

 , дакле:  

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

 

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

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

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

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

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

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

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

Алгоритам Рекурентна једначина Време извршења Коментар
Бинарна претрага     Примењена мастер теорема случај:  , где је  [3]
Бинарно стабло претраге     Примењена мастер теорема случај:   где је  [3]
Оптимална претрага сортиране матрице     Примењена Akra-Bazzi theorem за   и   да се добије  
Сортирање спајањем     Примењена мастер теорема случај:  , где је  

РеференцеУреди

  1. ^ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
  2. ^ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf[мртва веза]
  3. ^ а б Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf