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

Из Википедије, слободне енциклопедије

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

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

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

Генерички облик[уреди]

Ако је тачно:

где је

следи:

Пример[уреди]

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

, where

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

, дакле:

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

Према томе, дата рекурентна једначина 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. 3,0 3,1 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf