Master theorem

Da Wikipedia, l'enciclopedia libera.

Nell'analisi degli algoritmi, il Master Theorem è un caso particolare del teorema di Akra-Bazzi e permette di calcolare la complessità temporale di un gran numero di algoritmi ricorsivi definiti mediante relazioni di ricorrenza. Si noti che il Master Theorem non fornisce l'esatto tempo di esecuzione (il cosiddetto running time) dell'algoritmo, bensì fornisce il suo comportamento asintotico in funzione della dimensione dell'input, ovvero la funzione che descrive il tempo di esecuzione tralasciando le costanti moltiplicative. Ecco che allora attraverso questo teorema si può ad esempio affermare che un algoritmo ricorsivo ha complessità quadratica in funzione della dimensione dell'input n (cioè cresce come una parabola), ma non si può affermare che cresce ad esempio secondo la funzione $2 n 2 - n$ .

[modifica] 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:

[modifica] 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).\,$

[modifica] 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 $ε > 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})$ .

[modifica] 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}(\log n)^{k+1}\right).$

[modifica] 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 )$ .

[modifica] 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)).$

[modifica] 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)).$

[modifica] 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).\,$