Teorema principale (informatica)

Nell'analisi degli algoritmi, il Teorema Principale o Master Theorem (noto anche come Teorema dell'Esperto) è un caso particolare del teorema di Akra-Bazzi, quando i sottoproblemi hanno tutti dimensioni paragonabili. Permette di calcolare la complessità temporale degli algoritmi ricorsivi definiti mediante relazioni di ricorrenza. Si noti che il teorema non fornisce l'esatto tempo di esecuzione dell'algoritmo, ma il suo comportamento asintotico come funzione della dimensione dell'input, tralasciando le costanti additive e moltiplicative.

Enunciato

Sia dato un algoritmo $A$ e la relazione di ricorrenza $T_A(n)$ che ne descrive il costo:

$T_A(n) = a T_A\left(\frac{n}{b}\right) + f(n)\,$

dove $a \ge 1\,$ e $b > 1\,$ siano costanti, $\;\frac{n}{b}\;$ si può interpretare sia come $\;\left\lfloor \frac{n}{b} \right\rfloor\;$ (funzione floor), sia come $\;\left\lceil \frac{n}{b} \right\rceil\;$ (funzione ceiling), ed in cui:

• $n$ è la dimensione dell'input
• $a$ è il numero di chiamate ricorsive all'algoritmo $A$
• $\frac{n}{b}$ è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema)
• $f(n)$ è la funzione di costo della fase di suddivisione del problema e di ricostruzione della soluzione.

Per semplicità di trattazione supporremo che $n$ sia un'esatta potenza di $b$ e che la ricorsione si arresti quando $n=1$.

Analizzando l'albero della ricorsione relativo alla precedente relazione di ricorrenza, possiamo riscrivere quest'ultima nella forma $T_A(n)= \sum_{i=0}^{\log_{b}n} a^{i}f \left ( \frac{n}{b^{i}} \right )$.

Allora la funzione $\,T_A(n)\,$ è limitata asintoticamente secondo uno dei tre seguenti casi:

Caso 1

Se $\quad f(n) \in O\left( n^{\log_b a - \varepsilon} \right)$ (notazione O grande) per qualche costante $\quad \varepsilon > 0\,$

allora $\quad T_A(n) \in \Theta\left( n^{\log_b a} \right).\,$

Dimostrazione

Nel dimostrare il Caso 1 del Teorema Master faremo un abuso della notazione O grande, scrivendo che $f(n) = O \left (n \right)$

Per ipotesi $f(n) = O \left (n^{\log_{b}a-\epsilon} \right)$ per $\epsilon > 0$.

Usando l'abuso di notazione O grande accennato precedentemente, riscriviamo il termine principale della sommatoria espressa in precedenza in modo più conveniente alla dimostrazione del teorema; segue questa catena di uguaglianze:

$a^{i} f\left ( \frac{n}{b^{i}} \right ) = O \left ( a^{i} \left ( \frac{n}{b^{i}}\right )^{\log_{b}a -\epsilon} \right) = O \left ( n^{\log_{b}a -\epsilon} \left ( \frac{ab^{\epsilon}}{b^{\log_{b}a}} \right)^{i} \right) = O \left(n^{\log_{b}a-\epsilon} \left ( b^{\epsilon} \right )^{i} \right )$.

Pet limitare $T_A(n)$ possiamo scrivere:

$T_A(n)= \sum_{i=0}^{\log_{b}n} O \left ( n^{\log_{b}a-\epsilon} \left (b^{\epsilon} \right )^{i} \right ) = O \left ( n^{log_{b}a-\epsilon} \sum_{i=0}^{\log_{b}n} \left(b^{\epsilon}\right)^{i}\right ) = O \left ( n^{log_{b}a-\epsilon} \left ( \frac{b^{\epsilon(\log_{b}n+1)}-1}{b^{\epsilon}-1} \right) \right ) = O \left ( n^{log_{b}a-\epsilon} \left ( \frac{b^{\epsilon }n^{\epsilon}-1}{b^{\epsilon}-1} \right )\right ) = O \left (n^{\log_{b}a-\epsilon} n^{\epsilon} \right ) = O \left (n^{\log_{b}a} \right )$

Analizzando l'espressione $T_A(n)= \sum_{i=0}^{\log_{b}n} a^{i}f \left ( \frac{n}{b^{i}} \right )$, possiamo isolare i tempi di esecuzione relativi ai soli nodi sull'ultimo livello dell'albero di ricorsione, ottenendo:

$T_A(n) \ge a^{\log_{b}n} = n^{\log_{b}a}$ e quindi $T_A(n)= \Omega( n^{\log_{b}a})$.

Le due limitazioni ricavate implicano che $T_A(n)= \Theta( n^{\log_{b}a})$.

Caso 2

Se $f(n) \in \Theta\left( n^{\log_b a}(\log n)^k \right)$ per un intero $k \geq 0$

allora $T(n) \in \Theta\left( n^{\log_b a} \left ( \log n \right )^{k+1} \right).$

Dimostrazione

Dimostriamo il Caso 2 nel caso particolare in cui $\quad k=0$.

Partendo dall'ipotesi $f(n) = \Theta\left( n^{\log_b a}\right)$, riscriviamo il termine principale della sommatoria che esprime $T_A(n)$ come segue:

$a^{i}f \left ( \frac{n}{b^{i}} \right ) = \Theta \left ( a^{i} \left ( \frac{n}{b^{i}}\right )^{\log_{b}a}\right ) = \Theta \left ( n^{\log_{b}a } \left ( \frac{a}{b^{\log_{b}a}}\right )^{i} \right ) = \Theta \left ( n^{\log_{b}a} \right )$.

Da cui:

$T_A(n) = \sum_{i=0}^{\log_{b}n}a^{i}f \left ( \frac{n}{b^{i}} \right ) =\sum_{i=0}^{\log_{b}n}\Theta \left ( n^{\log_{b}a} \right ) = \Theta \left ( n^{\log_{b}a} \log_{b}n \right ) = \Theta \left ( n^{\log_{b}a} \log n\right )$.

Caso 3

Se $\quad f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)\;$ per qualche costante $\quad \varepsilon > 0\,$

e se $\quad a f\left( \frac{n}{b} \right) \le c f(n)\;$ per qualche costante $\; c < 1\;$ e per qualche n sufficientemente elevato,

allora $\quad T_A(n) \in \Theta(f(n)).$

Dimostrazione

Assumendo che valga la relazione $\quad a f\left( \frac{n}{b} \right) \le c f(n)\;$, si può dimostrare che vale la relazione $a^{i}f \left (\frac{n}{b^{i}} \right ) \le c^{i}f(n)$.

Infatti

$a^{i} f \left ( \frac{n}{b^{i}} \right ) = a^{i-1} a f \left ( \frac{n/b^{i-1}}{b} \right ) \le a^{i-1} c f \left ( \frac{n}{b^{i-1}} \right )$

Continuando l'iterazione si ottiene la disuguaglianza desiderata.

Vale la seguente catena di disuguaglianze:

$T_A(n) = \sum_{i=0}^{\log_{b} n} a^{i} f \left ( \frac{n}{b^{i}} \right ) \le \sum_{i=0}^{\log_{b} n} c^{i}f(n) \le f(n) \sum_{i=0}^{\infty} c^{i} = f(n) \; \frac{1}{1-c} = O(f(n))$

Dalla relazione di ricorrenza $\quad T_A(n)=a T_A \left ( \frac{n}{b} \right ) + f(n)$ possiamo ricavare che $\quad T_A(n)= \Omega (f(n))$.

Questo implica che $\quad T_A(n) = \Theta (f(n)).$

Definizione informale

Si tenta qui di dare una definizione molto informale del Master Theorem. In ognuno dei 3 casi sopra esposti si confronta la funzione che descrive il costo della fase di calcolo del sottoproblema di ricombinazione del risultato delle $a$ chiamate ricorsive (cioè la funzione $f(n)$ che appare nella relazione di ricorrenza) con la funzione $n^{\log_b a}.\,$ Il costo della relazione di ricorrenza è determinato dalla funzione che cresce più velocemente tra le due. Ad esempio nel caso 1 la funzione $n^{\log_b a}$ è più grande di $n^{\log_b a - \varepsilon}$ e quindi $T_A(n) = \Theta( n^{\log_b a}).\,$ Viceversa nel caso 3 si confrontano le funzioni $f(n) = n^{\log_b a + \varepsilon}\,$ e $\,n^{\log_b a}$ in cui la prima è la più grande e quindi $T_A(n) = \Theta\left( f(n) \right)$. Infine nel caso 2 le due funzioni crescono in modo simile, ovvero sono dello stesso ordine di grandezza, e la soluzione è la funzione f(n) moltiplicata per un fattore logaritmico: $\quad T(n) = \Theta( n^{\log_b a} \log(n)) = \Theta\left( f(n)\log(n)\right).\,$

Esempi

Caso 1

Sia data la seguente relazione di ricorrenza:

$T_A(n)=9\,T_A\left(\frac{n}{3}\right) + n.\,$

Si ha $a=9$, $b=3$ e $f(n)= n$. Allora $n^{log_b a} = n^{log_3 9} = \Theta\left( n^2 \right).\,$ Dato che $f(n)= O\left( n^{log_3 9 - \varepsilon} \right)\,$ quando ε = 1, è possibile applicare il caso 1 del Master Theorem ottenendo la soluzione

$T_A(n)=\Theta\left(n^2\right).\,$

Caso 2

Sia data ora la relazione di ricorrenza:

$T_A(n)=T_A\left(\frac{2\,n}{3}\right) + 1,$

in cui $a=1$, $b=3/2$ e $f(n)= 1$. Essendo $n^{log_b a} = n^{log_{3/2} 1} = \Theta(n^0) = \Theta(1)\,$ ed $f(n)=1$, vale il caso 2 del Master Theorem, che porta alla soluzione $T_A(n)= \Theta(log_2 n).\,$

Caso 3

Infine sia data la relazione di ricorrenza:

$T_A(n)=3\,T_A\left(\frac{n}{4}\right) + n\lg n.\,$

in cui $a=3$, $b=4$ e $f(n)= n\lg n$. Essendo $n^{log_b a} = n^{log_4 3} = O\left(n^{0.793}\right)\,$ ed $f(n)=\Omega\left(n^{\log_4 3 + \varepsilon}\right)$, in cui ε ≈ 0.2, il caso 3 del Master Theorem si può applicare solo se vale la condizione di regolarità per $f(n)$. Per n sufficientemente grande si ha $3\left(\frac{n}{4}\right) \lg \left(\frac{n}{4}\right) \le \left(\frac{3}{4}n\lg n\right)= cf(n)$ per $c = 3/4 \le 1$. Di conseguenza la soluzione della ricorrenza è $T_A(n)= \Theta(n\lg n).\,$

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Sections 4.3 (The master method), pp.73–90. ISBN 0-262-03293-7.

Voci correlate

• Algoritmo ricorsivo
• Relazione di ricorrenza
• Stima asintotica
• Teorema principale di MacMahon

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica