У анализи алгоритама мастер теорема представља основу за решавање рекурентних једначина које се јављају при анализи многих подели-па-владај алгоритама. Представљена је и доказана у књизи 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 који му је прослеђен од родитеља и представљен са . Укупан посао који обави цело дрво је сума послова које обави сваки чвор.
Овакви алгоритми могу да се представе рекурентном једначином . Ова рекурзивна једначина се може сукцесивно заменити сама у себе и проширити у израз који представља укупан одрађени посао. Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html
На овај начин се, користећи мастер теорему, лако може израчунати време извршавања оваквих рекурзивних алгоритама и представити у О-нотацији без развијања рекурентне једначине.
Генерички облик Мастер теорема решава рекурентне једначине следећег облика:
Константе и функције имају следећи значај:
n -величина проблема. a -број подпроблема у рекурзији. n/b -величина сваког подпроблема (Овде се претпоставља да су сви подпроблеми у суштини исте величине). f (n) -цена операција обављених ван рекурзивних позива(обухвата операције дељења проблема на подпроблеме и спајања решења добијених као решења подпроблема).
Може се одредити асимптотска граница у следећа три случаја:
Први случај Генерички облик Ако где је (користећи О-нотацију)
следи да је:
Пример
Из горње једначине се може закључити да променљиве узимају следеће вредности:
, где је
Даље проверавамо да ли је задовољен услов првог случаја мастер теореме:
, дакле:
Задовољен је услов, па из првог случаја мастер теореме следи:
Према томе, дата рекурентна једначина T(n) припада Θ(n3).
Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .
Други случај Генерички облик Ако за неку константу k ≥ 0, важи да је:
где је
следи:
Пример
Из претходне једначине променљиве узимају следеће вредности:
где је Даље проверавамо да ли је задовољен услов друог случаја мастер теореме: , дакле:
Задовољен је услов, па из другог случаја мастер теореме следи:
Према томе, дата рекурентна једначина T(n) припада Θ(n log n).
Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .
Трећи случај Генерички облик Ако је тачно:
где је
следи:
Пример
Из претходне једначине променљиве узимају следеће вредности:
, где је
Даље проверавамо да ли је задовољен услов трећег случаја мастер теореме: , дакле:
Задовољен је услов, па из трћег случаја мастер теореме следи:
Према томе, дата рекурентна једначина T(n) припада Θ(n2), што је у складу са f (n) из почетне једначине.
Овај резултат се може потврдити директним решавањем рекурентне једначине: , под претпоставком да је .
Примери нерешивих једначина Следеће једначине се не могу решити мастер теоремомMassachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf:
a није константа
неполиномијална разлика између f(n) и (погледај испод)
a<1 не може имати мање од једног подпроблема
f(n) није позитивна
трећи случај, али није исправно
У другом примеру изнад разлика између и може се изразити односом . Јасно је да за било коју константу . Стога, разлика није полиномијална и мастер теорема не важи.
Примена на познате алгоритме Алгоритам Рекурентна једначина Време извршења Коментар Бинарна претрага Примењена мастер теорема случај: , где је Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Бинарно стабло претраге Примењена мастер теорема случај: где је Оптимална претрага сортиране матрице Примењена Akra-Bazzi theorem за и да се добије Сортирање спајањем Примењена мастер теорема случај: , где је
Референце
Категорија:Информатика Категорија:Алгоритми Категорија:Теорија комплексности