El teorema mestre és una eina que s'utilitza per resoldre les relacions de recurrència que sorgeixen en l'anàlisi d'algorismes de dividir i vencer. El teorema mestre proporciona una manera sistemàtica de resoldre relacions de recurrència de la forma:

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

1. on a, b i f(n) són funcions positives i n és la mida del problema. El teorema mestre proporciona condicions perquè la solució de la recurrència sigui en forma de O(n^k) per a una constant k, i dóna una fórmula per determinar el valor de k.
2. La versió avançada del teorema mestre proporciona una forma més general del teorema que pot gestionar relacions de recurrència que són més complexes que la forma bàsica. La versió avançada del teorema mestre pot gestionar recurrències amb múltiples termes i funcions més complexes.
3. És important tenir en compte que el teorema mestre no és aplicable a totes les relacions de recurrència, i és possible que no sempre proporcioni una solució exacta a una recurrència determinada. Tanmateix, és una eina útil per analitzar la complexitat temporal dels algorismes de dividir i vencer i proporciona un bon punt de partida per resoldre recurrències més complexes.

El teorema mestre s'utilitza per determinar el temps d'execució dels algorismes (algorismes de divideix i conquereixes) en termes de notacions asimptòtiques.
Considereu un problema que es resol amb recursivitat.

 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>

L'algorisme anterior divideix el problema en a subproblemes, cadascun de mida n/b i resol-los recursivament per calcular el problema i el treball addicional realitzat per al problema ve donat per f(n), és a dir, el temps per crear els subproblemes i combinar els seus resultats en el procediment anterior.

Així, segons el teorema mestre, el temps d'execució de l'algorisme anterior es pot expressar com:

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

on n = mida del problema
a = nombre de subproblemes en la recursivitat i a>= 1
n/b = mida de cada subproblema
f(n) = cost del treball realitzat fora de les crides recursives com dividir en subproblemes i el cost de combinar-los per obtenir la solució.

No totes les relacions de recurrència es poden resoldre amb l'ús del teorema mestre, és a dir, si

• T(n) no és monòton, ex: T(n) = sin n
• f(n) no és un polinomi, per exemple: T(n) = 2T(n/2) + 2ⁿ

Aquest teorema és una versió avançada del teorema mestre que es pot utilitzar per determinar el temps d'execució dels algorismes de dividir i conquerir si la recurrència és de la forma següent:

on n = mida del problema
a = nombre de subproblemes en la recursivitat i a>= 1
n/b = mida de cada subproblema
b> 1, k>= 0 i p és un nombre real.

Llavors,

1. si a> b^k, aleshores T(n) = θ(n^registre_ba)
2. si a = b^k, doncs
   (a) si p> -1, aleshores T(n) = θ(n^registre_baregistre^p+1n)
   (b) si p = -1, aleshores T(n) = θ(n^registre_bainici de sessió)
   (c) si p <-1, aleshores T(n) = θ(n^registre_ba)
   
3. si a k, doncs
   (a) si p>= 0, aleshores T(n) = θ(n^kregistre^pàgn)
   (b) si p <0, aleshores T(n) = θ(n^k)
   

Anàlisi de la complexitat temporal -

Exemple 1: cerca binària – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 i p = 0
b^k= 1. Així, a = b^ki p> -1 [Cas 2.(a)]
T(n) = θ(n^registre_baregistre^p+1n)
T(n) = θ(logn) Exemple 2: Ordenació de fusió – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Així, a = b^ki p> -1 [Cas 2.(a)]
T(n) = θ(n^registre_baregistre^p+1n)
T(n) = θ(nlogn) Exemple-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Així, a k i p = 0 [Cas 3.(a)]
T(n) = θ(n^kregistre^pàgn)
T(n) = θ(n²)

Exemple-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Així, a> b^k[Cas 1]
T(n) = θ(n^registre_ba)
T(n) = θ(n^registre₂3)

Exemple-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Així, a = b^k[Cas 2.(a)]
T(n) = θ(n^registre_baregistre^p+1n)
T(n) = θ(n^registre₂2registre³n)
T(n) = θ(nlog³n)

Exemple-6: T(n) = 2ⁿT(n/2) + nⁿ
Aquesta recurrència no es pot resoldre amb el mètode anterior, ja que la funció no té la forma T(n) = aT(n/b) + θ(n)^kregistre^pàgn)

Preguntes pràctiques GATE -

• GATE-CS-2017 (Conjunt 2) | Pregunta 56
• GATE IT 2008 | Pregunta 42
• GATE CS 2009 | Pregunta 35

Aquests són alguns punts importants a tenir en compte pel que fa al teorema mestre:

1. Recurrències de divideix i venços: el teorema mestre està dissenyat específicament per resoldre les relacions de recurrència que sorgeixen en l'anàlisi dels algorismes de divideix i vencera.
2. Forma de la recurrència: el teorema mestre s'aplica a les relacions de recurrència de la forma T(n) = aT(n/b) + f(n), on a, b i f(n) són funcions positives i n és la mida del problema.
3. Complexitat temporal: el teorema mestre proporciona condicions perquè la solució de la recurrència sigui en forma de O(n^k) per a una constant k, i dóna una fórmula per determinar el valor de k.
4. Versió avançada: la versió avançada del teorema mestre proporciona una forma més general del teorema que pot gestionar relacions de recurrència que són més complexes que la forma bàsica.
5. Limitacions: el teorema mestre no és aplicable a totes les relacions de recurrència, i pot ser que no sempre proporcioni una solució exacta a una recurrència determinada.
6. Eina útil: Malgrat les seves limitacions, el Teorema Mestre és una eina útil per analitzar la complexitat temporal dels algorismes de dividir i conquerir i proporciona un bon punt de partida per resoldre recurrències més complexes.
7. Complementat amb altres tècniques: En alguns casos, el teorema mestre pot necessitar ser complementat amb altres tècniques, com el mètode de substitució o el mètode d'iteració, per resoldre completament una relació de recurrència determinada.