Il Master Theorem è uno strumento utilizzato per risolvere le relazioni di ricorrenza che sorgono nell'analisi degli algoritmi divide et impera. Il Master Theorem fornisce un modo sistematico per risolvere le relazioni ricorrenti della forma:

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

1. dove a, b e f(n) sono funzioni positive e n è la dimensione del problema. Il Teorema Maestro fornisce le condizioni affinché la soluzione della ricorrenza sia nella forma di O(n^k) per una costante k, e fornisce una formula per determinare il valore di k.
2. La versione avanzata del Master Theorem fornisce una forma più generale del teorema in grado di gestire relazioni ricorrenti più complesse rispetto alla forma di base. La versione avanzata del Master Theorem può gestire ricorrenze con termini multipli e funzioni più complesse.
3. È importante notare che il Teorema Maestro non è applicabile a tutte le relazioni ricorrenti e potrebbe non fornire sempre una soluzione esatta per una data ricorrenza. Tuttavia, è uno strumento utile per analizzare la complessità temporale degli algoritmi divide et impera e fornisce un buon punto di partenza per risolvere ricorrenze più complesse.

Il Teorema Principale viene utilizzato per determinare il tempo di esecuzione degli algoritmi (algoritmi divide et impera) in termini di notazioni asintotiche.
Consideriamo un problema risolto mediante la ricorsione.

 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'algoritmo di cui sopra divide il problema in UN sottoproblemi, ciascuno di dimensione n/b e risolverli ricorsivamente per calcolare il problema e il lavoro extra svolto per il problema è dato da f(n), cioè il tempo necessario per creare i sottoproblemi e combinare i loro risultati nella procedura precedente.

Quindi, secondo il teorema principale, il tempo di esecuzione dell'algoritmo di cui sopra può essere espresso come:

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

dove n = dimensione del problema
a = numero di sottoproblemi nella ricorsione e a>= 1
n/b = dimensione di ciascun sottoproblema
f(n) = costo del lavoro svolto al di fuori delle chiamate ricorsive come la divisione in sottoproblemi e costo della loro combinazione per ottenere la soluzione.

Non tutte le relazioni ricorrenti possono essere risolte con l'uso del teorema maestro, cioè se

• T(n) non è monotono, es: T(n) = sin n
• f(n) non è un polinomio, es: T(n) = 2T(n/2) + 2^N

Questo teorema è una versione avanzata del teorema principale che può essere utilizzato per determinare il tempo di esecuzione degli algoritmi divide et impera se la ricorrenza è nella seguente forma: -

dove n = dimensione del problema
a = numero di sottoproblemi nella ricorsione e a>= 1
n/b = dimensione di ciascun sottoproblema
b> 1, k>= 0 e p è un numero reale.

Poi,

1. se a> b^K, allora T(n) = θ(n^{tronco d'albero_BUN})
2. se a = b^K, Poi
   (a) se p> -1, allora T(n) = θ(n^{tronco d'albero_BUN}tronco d'albero^p+1N)
   (b) se p = -1, allora T(n) = θ(n^{tronco d'albero_BUN}loglog)
   (c) se p <-1, allora T(n) = θ(n^{tronco d'albero_BUN})
   
3. se un okay allora
   (a) se p>= 0, allora T(n) = θ(n^Ktronco d'albero^PN)
   (b) se p <0, allora T(n) = θ(n^K)
   

Analisi della complessità temporale –

Esempio 1: Ricerca binaria – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 e p = 0
B^K= 1. Quindi, a = b^Ke p> -1 [Caso 2.(a)]
T(n) = θ(n^{tronco d'albero_BUN}tronco d'albero^p+1N)
T(n) = θ(logn) Esempio 2: Merge Sort – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
B^K= 2. Quindi, a = b^Ke p> -1 [Caso 2.(a)]
T(n) = θ(n^{tronco d'albero_BUN}tronco d'albero^p+1N)
T(n) = θ(nlogn) Esempio 3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
B^K= 4. Quindi, a k e p = 0 [Caso 3.(a)]
T(n) = θ(n^Ktronco d'albero^PN)
T(n) = θ(n²)

Esempio 4: T(n) = 3T(n/2) + log²N
a = 3, b = 2, k = 0, p = 2
B^K= 1. Quindi, a> b^K[Caso 1]
T(n) = θ(n^{tronco d'albero_BUN})
T(n) = θ(n^{tronco d'albero₂3})

Esempio 5: T(n) = 2T(n/2) + nlog²N
a = 2, b = 2, k = 1, p = 2
B^K= 2. Quindi, a = b^K[Caso 2.(a)]
T(n) = θ(n^{tronco d'albero_BUN}tronco d'albero^p+1N )
T(n) = θ(n^{tronco d'albero₂2}tronco d'albero³N)
T(n) = θ(nlog³N)

Esempio 6: T(n) = 2^NT(n/2) + n^N
Questa ricorrenza non può essere risolta utilizzando il metodo sopra poiché la funzione non è della forma T(n) = aT(n/b) + θ(n^Ktronco d'albero^PN)

Domande pratiche GATE –

• GATE-CS-2017 (Set 2) | Domanda 56
• CANCELLO IT 2008 | Domanda 42
• GATECS2009 | Domanda 35

Ecco alcuni punti importanti da tenere a mente riguardo al Teorema del Maestro:

1. Ricordi di divisione e conquista: il Master Theorem è specificamente progettato per risolvere le relazioni di ricorrenza che sorgono nell'analisi degli algoritmi di divisione e conquista.
2. Forma della ricorrenza: il Teorema Maestro si applica alle relazioni di ricorrenza della forma T(n) = aT(n/b) + f(n), dove a, b e f(n) sono funzioni positive e n è la dimensione del problema.
3. Complessità temporale: il Teorema Principale fornisce le condizioni affinché la soluzione della ricorrenza sia nella forma di O(n^k) per una costante k e fornisce una formula per determinare il valore di k.
4. Versione avanzata: la versione avanzata del Master Theorem fornisce una forma più generale del teorema in grado di gestire relazioni ricorrenti più complesse rispetto alla forma di base.
5. Limitazioni: il Teorema Principale non è applicabile a tutte le relazioni ricorrenti e potrebbe non fornire sempre una soluzione esatta per una data ricorrenza.
6. Strumento utile: nonostante i suoi limiti, il Master Theorem è uno strumento utile per analizzare la complessità temporale degli algoritmi divide et impera e fornisce un buon punto di partenza per risolvere ricorrenze più complesse.
7. Integrazione con altre tecniche: in alcuni casi, potrebbe essere necessario integrare il Master Theorem con altre tecniche, come il metodo di sostituzione o il metodo di iterazione, per risolvere completamente una determinata relazione di ricorrenza.