In algoritmica, il teorema master (chiamato anche teorema dell’esperto) è un metodo utilizzato per risolvere equazioni ricorsive della forma: $$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$
dove $a \geq 1$ e $b > 1$, $a$ e $b$ sono costanti.
Applicazione
Questo teorema prevede di confrontare la funzione $f(n)$ con la funzione $n^{\log_b a}$, il risultato di questo confronto determina il caso specifico di applicazione.
I Tre Casi
Primo Caso
Se la funzione $f(n)$ è tale che, per una certa costante $\epsilon>0$, è minore di un fattore polinomiale rispetto alla funzione $n^{\log_b a}$, allora la soluzione dell’equazione ricorsiva è $\Theta(n^{\log_b a})$ $$f(n) = O(n^{\log_b a – \epsilon}) \Rightarrow T(n)=\Theta(n^{\log_b a})$$
Secondo Caso
Se la funzione $f(n)$ è dello stesso ordine della funzione $n^{\log_b a}$, allora la funzione $n^{\log_b a}$ è moltiplicata per un fattore logaritmico e la soluzione dell’equazione ricorsiva è $\Theta(n^{\log_b a} \cdot \log n)$ $$f(n) = \Theta(n^{\log_b a}) \Rightarrow T(n) = \Theta(n^{\log_b a} \cdot \log n)$$
Terzo Caso
Se la funzione $f(n)$ è tale che, per una certa costante $\epsilon>0$, se $a \cdot f(\frac{n}{b}) \leq c \cdot f(n)$ per una certa costante $c<1$ e per $n$ sufficientemente grande, è maggiore di un fattore polinomiale rispetto alla funzione $n^{\log_b a}$, allora la soluzione dell’equazione ricorsiva è $\Theta(f(n))$ $$f(n) = \Omega(n^{\log_b a + \epsilon}) \Rightarrow T(n)=\Theta(f(n))$$
Esempio
Risolviamo la seguente equazione ricorsiva utilizzando il teorema master: $$T(n) = 2T(n/2)+n$$ $$a = 2$$ $$b = 2$$ $$n^{log_b a} = n$$
Poiché la funzione $f(n)$ e la funzione $n^{log_b a}$ sono dello stesso ordine, si rientra nel secondo caso, quindi la soluzione di questa equazione ricorsiva è $T(n)=\Theta(n \cdot \log n)$.
Non Applicabilità
Il teorema master è uno strumento molto utile per risolvere equazioni ricorsive, ma non è applicabile in tutti i casi. Non può essere applicato se: $T(n)$ non è una funzione monotona, la funzione $f(n)$ non è polinomiale, il termine $b$ non può essere espresso come una costante.