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

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

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 који му је прослеђен од родитеља и представљен са f(n). Укупан посао који обави цело дрво је сума послова које обави сваки чвор.

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

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

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

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

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

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

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

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

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

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

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

следи да је:

T(n) = \Theta\left(n^{\log_b a} \right)

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

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

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

a = 8, \, b = 2, \, f(n) = 1000n^2
f(n) = \Theta\left(n^c\right), где је c = 2

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

\log_b a = \log_2 8 = 3, дакле: c < \log_b a

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

T(n) = \Theta\left(n^{\log_b a} \right) = \Theta\left(n^{3} \right)

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

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

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

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

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

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

следи:

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

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

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

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

a = 2, \, b = 2, \, c = 1, \, f(n) = 10n
f(n) = \Theta\left(n^{c} \log^k n\right) где је c = 1, k = 0

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

\log_b a = \log_2 2 = 1, дакле: c = \log_b a

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

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).

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

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

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

Ако је тачно:

f(n) = \Theta\left(n^{c} \right) где је c > \log_b a

следи:

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

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

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

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

a = 2, \, b = 2, \, f(n) = n^2
f(n) = \Theta\left(n^c\right), where c = 2

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

\log_b a = \log_2 2 = 1, дакле: c > \log_b a

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

T \left(n \right) = \Theta\left(n^c\right) = \Theta \left(n^2 \right).

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

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

Примери нерешивих једначина[уреди]

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

  • T(n) = 2^nT\left (\frac{n}{2}\right )+n^n
    a није константа
  • T(n) = 2T\left (\frac{n}{2}\right )+\frac{n}{\log n}
    неполиномијална разлика између f(n) и n^{\log_b a} (погледај испод)
  • T(n) = 0.5T\left (\frac{n}{2}\right )+n
    a<1 не може имати мање од једног подпроблема
  • T(n) = 64T\left (\frac{n}{8}\right )-n^2\log n
    f(n) није позитивна
  • T(n) = T\left (\frac{n}{2}\right )+n(2-\cos n)
    трећи случај, али није исправно

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

Примена на познате алгоритме[уреди]

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

Референце[уреди]

  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