Master Theorem je nástroj používaný na riešenie rekurentných vzťahov, ktoré vznikajú pri analýze algoritmov rozdeľuj a panuj. Hlavná veta poskytuje systematický spôsob riešenia rekurentných vzťahov vo forme:

T(n) = aT(n/b) + f(n)

1. kde a, b a f(n) sú kladné funkcie a n je veľkosť problému. Hlavná veta poskytuje podmienky, aby riešenie recidívy bolo v tvare O(n^k) pre nejakú konštantu k, a dáva vzorec na určenie hodnoty k.
2. Pokročilá verzia Master Theorem poskytuje všeobecnejšiu formu vety, ktorá dokáže zvládnuť rekurentné vzťahy, ktoré sú zložitejšie ako základná forma. Pokročilá verzia Master Theorem dokáže zvládnuť recidívy s viacerými pojmami a zložitejšími funkciami.
3. Je dôležité poznamenať, že hlavná veta nie je použiteľná pre všetky recidívy a nemusí vždy poskytnúť presné riešenie danej recidívy. Je to však užitočný nástroj na analýzu časovej zložitosti algoritmov rozdeľuj a panuj a poskytuje dobrý východiskový bod pre riešenie zložitejších recidív.

Master Theorem sa používa na určenie doby chodu algoritmov (algoritmov rozdeľ a panuj) v zmysle asymptotických zápisov.
Zvážte problém, ktorý je vyriešený pomocou rekurzie.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems 

Vyššie uvedený algoritmus rozdeľuje problém na a podproblémy, každý veľkosti n/b, a rekurzívne ich riešiť, aby sa vypočítal problém a práca navyše vykonaná na probléme je daná f(n), t. j. čas na vytvorenie podproblémov a spojenie ich výsledkov vo vyššie uvedenom postupe.

Takže podľa hlavnej vety môže byť čas spustenia vyššie uvedeného algoritmu vyjadrený ako:

 T(n) = aT(n/b) + f(n) 

kde n = veľkosť problému
a = počet čiastkových problémov v rekurzii a a>= 1
n/b = veľkosť každého čiastkového problému
f(n) = náklady na prácu vykonanú mimo rekurzívnych hovorov, ako je rozdelenie na podproblémy a náklady na ich kombinovanie na získanie riešenia.

Nie všetky rekurentné vzťahy je možné vyriešiť pomocou hlavnej vety, t.j

• T(n) nie je monotónne, napr.: T(n) = sin n
• f(n) nie je polynóm, napr.: T(n) = 2T(n/2) + 2 ⁿ

Táto veta je pokročilou verziou hlavnej vety, ktorú možno použiť na určenie doby trvania algoritmov rozdelenia a panovania, ak má opakovanie nasledujúci tvar: -

kde n = veľkosť problému
a = počet čiastkových problémov v rekurzii a a>= 1
n/b = veľkosť každého čiastkového problému
b> 1, k>= 0 a p je reálne číslo.

potom

1. ak a> b ^k , potom T(n) = θ(n ^{log _b a} )
2. ak a = b ^k , potom
   (a) ak p> -1, potom T(n) = θ(n ^{log _b a} log ^p+1 n)
   (b) ak p = -1, potom T(n) = θ(n ^{log _b a} loglogn)
   (c) ak p <-1, potom T(n) = θ(n ^{log _b a} )
   
3. Ak k, teda
   (a) ak p>= 0, potom T(n) = θ(n ^k log ^p n)
   (b) ak p < 0, potom T(n) = θ(n ^k )
   

Analýza časovej zložitosti –

Príklad-1: Binárne vyhľadávanie – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 a p = 0
b ^k = 1. Takže a = b ^k a p> -1 [Prípad 2.(a)]
T(n) = θ(n ^{log _b a} log ^p+1 n)
T(n) = θ(logn) Príklad-2: Zlúčiť triedenie – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b ^k = 2. Takže a = b ^k a p> -1 [Prípad 2.(a)]
T(n) = θ(n ^{log _b a} log ^p+1 n)
T(n) = θ(nlogn) Príklad-3: T(n) = 3T(n/2) + n ²
a = 3, b = 2, k = 2, p = 0
b ^k = 4. Takže, a k a p = 0 [Prípad 3.(a)]
T(n) = θ(n ^k log ^p n)
T(n) = θ(n ² )

Príklad-4: T(n) = 3T(n/2) + log ² n
a = 3, b = 2, k = 0, p = 2
b ^k = 1. Takže a> b ^k [Prípad 1]
T(n) = θ(n ^{log _b a} )
T(n) = θ(n ^{log ₂ 3} )

Príklad-5: T(n) = 2T(n/2) + nlog ² n
a = 2, b = 2, k = 1, p = 2
b ^k = 2. Takže a = b ^k [Prípad 2.(a)]
T(n) = θ(n ^{log _b a} log ^p+1 n)
T(n) = θ(n ^{log ₂ 2} log ³ n)
T(n) = θ(nlog ³ n)

Príklad-6: T(n) = 2 ⁿ T(n/2) + n ⁿ
Toto opakovanie nie je možné vyriešiť pomocou vyššie uvedenej metódy, pretože funkcia nie je v tvare T(n) = aT(n/b) + θ(n ^k log ^p n)

Cvičné otázky GATE –

• GATE-CS-2017 (Sada 2) | Otázka 56
• GATE IT 2008 | Otázka 42
• GATE CS 2009 | Otázka 35

Tu je niekoľko dôležitých bodov, ktoré treba mať na pamäti, pokiaľ ide o hlavnú vetu:

1. Rekurencie rozdeľuj a panuj: Hlavná teoréma je špeciálne navrhnutá na riešenie vzťahov opakovania, ktoré vznikajú pri analýze algoritmov rozdeľuj a panuj.
2. Forma rekurencie: Hlavná veta platí pre rekurentné vzťahy v tvare T(n) = aT(n/b) + f(n), kde a, b a f(n) sú kladné funkcie a n je veľkosť problému.
3. Časová zložitosť: Hlavná veta poskytuje podmienky na to, aby riešenie recidívy bolo v tvare O(n^k) pre nejakú konštantu k a dáva vzorec na určenie hodnoty k.
4. Pokročilá verzia: Pokročilá verzia Master Theorem poskytuje všeobecnejšiu formu vety, ktorá dokáže zvládnuť rekurentné vzťahy, ktoré sú zložitejšie ako základná forma.
5. Obmedzenia: Hlavná veta nie je aplikovateľná na všetky recidívy a nemusí vždy poskytnúť presné riešenie danej recidívy.
6. Užitočný nástroj: Napriek svojim obmedzeniam je Master Theorem užitočným nástrojom na analýzu časovej zložitosti algoritmov rozdeľuj a panuj a poskytuje dobrý východiskový bod pre riešenie zložitejších recidív.
7. Doplnené o ďalšie techniky: V niektorých prípadoch môže byť potrebné doplniť hlavnú vetu o ďalšie techniky, ako je substitučná metóda alebo metóda iterácie, aby sa úplne vyriešil daný vzťah opakovania.