Teorema Master este un instrument folosit pentru a rezolva relațiile de recurență care apar în analiza algoritmilor de împărțire și cuceri. Teorema Master oferă o modalitate sistematică de rezolvare a relațiilor de recurență de forma:

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

1. unde a, b și f(n) sunt funcții pozitive și n este dimensiunea problemei. Teorema principală oferă condiții pentru ca soluția recurenței să fie sub forma O(n^k) pentru o constantă k și oferă o formulă pentru determinarea valorii lui k.
2. Versiunea avansată a teoremei principale oferă o formă mai generală a teoremei care poate gestiona relații de recurență care sunt mai complexe decât forma de bază. Versiunea avansată a teoremei principale poate gestiona recurențe cu termeni multipli și funcții mai complexe.
3. Este important de reținut că teorema principală nu este aplicabilă tuturor relațiilor de recurență și este posibil să nu ofere întotdeauna o soluție exactă pentru o anumită recurență. Cu toate acestea, este un instrument util pentru analiza complexității în timp a algoritmilor de împărțire și cucerire și oferă un bun punct de plecare pentru rezolvarea recurențelor mai complexe.

Teorema magistrală este utilizată pentru a determina timpul de rulare al algoritmilor (algoritmi de împărțire și cucerire) în termeni de notații asimptotice.
Luați în considerare o problemă care este rezolvată folosind recursiunea.

 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>

Algoritmul de mai sus împarte problema în A subprobleme, fiecare de dimensiunea n/b și rezolvați-le recursiv pentru a calcula problema, iar munca suplimentară efectuată pentru problemă este dată de f(n), adică timpul necesar pentru a crea subproblemele și a combina rezultatele lor în procedura de mai sus.

Deci, conform teoremei principale, timpul de rulare al algoritmului de mai sus poate fi exprimat astfel:

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

unde n = dimensiunea problemei
a = numărul de subprobleme din recursivitate și a>= 1
n/b = dimensiunea fiecărei subprobleme
f(n) = costul muncii efectuate în afara apelurilor recursive, cum ar fi împărțirea în subprobleme și costul combinării lor pentru a obține soluția.

Nu toate relațiile de recurență pot fi rezolvate cu utilizarea teoremei principale, adică dacă

• T(n) nu este monoton, ex: T(n) = sin n
• f(n) nu este un polinom, ex: T(n) = 2T(n/2) + 2ⁿ

Această teoremă este o versiune avansată a teoremei principale care poate fi utilizată pentru a determina timpul de rulare al algoritmilor de împărțire și cucerire dacă recurența este de următoarea formă:

unde n = dimensiunea problemei
a = numărul de subprobleme din recursivitate și a>= 1
n/b = dimensiunea fiecărei subprobleme
b> 1, k>= 0 și p este un număr real.

Apoi,

1. dacă a> b^k, atunci T(n) = θ(n^Buturuga_bA)
2. dacă a = b^k, apoi
   (a) dacă p> -1, atunci T(n) = θ(n^Buturuga_bAButuruga^p+1n)
   (b) dacă p = -1, atunci T(n) = θ(n^Buturuga_bAloglog)
   (c) dacă p <-1, atunci T(n) = θ(n^Buturuga_bA)
   
3. în cazul în care o bine atunci
   (a) dacă p>= 0, atunci T(n) = θ(n^kButuruga^pn)
   (b) dacă p <0, atunci T(n) = θ(n^k)
   

Analiza complexității timpului -

Exemplul-1: Căutare binară – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 și p = 0
b^k= 1. Deci, a = b^kși p> -1 [Cazul 2.(a)]
T(n) = θ(n^Buturuga_bAButuruga^p+1n)
T(n) = θ(logn) Exemplul-2: Sortare fuzionare – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Deci, a = b^kși p> -1 [Cazul 2.(a)]
T(n) = θ(n^Buturuga_bAButuruga^p+1n)
T(n) = θ(nlogn) Exemplul-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Deci, a k și p = 0 [Cazul 3.(a)]
T(n) = θ(n^kButuruga^pn)
T(n) = θ(n²)

Exemplul-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Deci, a> b^k[Cazul 1]
T(n) = θ(n^Buturuga_bA)
T(n) = θ(n^Buturuga₂3)

Exemplul-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Deci, a = b^k[Cazul 2.(a)]
T(n) = θ(n^Buturuga_bAButuruga^p+1n)
T(n) = θ(n^Buturuga₂2Buturuga³n)
T(n) = θ(nlog³n)

Exemplul-6: T(n) = 2ⁿT(n/2) + nⁿ
Această recurență nu poate fi rezolvată folosind metoda de mai sus, deoarece funcția nu este de forma T(n) = aT(n/b) + θ(n)^kButuruga^pn)

Întrebări practice GATE –

• GATE-CS-2017 (Setul 2) | Întrebarea 56
• GATE IT 2008 | Întrebarea 42
• GATE CS 2009 | Întrebarea 35

Iată câteva puncte importante de reținut în ceea ce privește Teorema Master:

1. Recurențe de împărțire și cucerire: Teorema principală este concepută special pentru a rezolva relațiile de recurență care apar în analiza algoritmilor de împărțire și cucerire.
2. Forma recurenței: Teorema principală se aplică relațiilor de recurență de forma T(n) = aT(n/b) + f(n), unde a, b și f(n) sunt funcții pozitive și n este dimensiunea a problemei.
3. Complexitatea timpului: Teorema principală oferă condiții pentru ca soluția recurenței să fie sub forma O(n^k) pentru o constantă k și oferă o formulă pentru determinarea valorii lui k.
4. Versiunea avansată: Versiunea avansată a teoremei principale oferă o formă mai generală a teoremei care poate gestiona relații de recurență care sunt mai complexe decât forma de bază.
5. Limitări: Teorema principală nu este aplicabilă tuturor relațiilor de recurență și este posibil să nu ofere întotdeauna o soluție exactă pentru o anumită recurență.
6. Instrument util: În ciuda limitărilor sale, Teorema Master este un instrument util pentru analiza complexității în timp a algoritmilor de împărțire și cucerire și oferă un bun punct de plecare pentru rezolvarea recurențelor mai complexe.
7. Suplimentat cu alte tehnici: în unele cazuri, teorema principală poate fi necesară suplimentării cu alte tehnici, cum ar fi metoda substituției sau metoda iterației, pentru a rezolva complet o anumită relație de recurență.