Teorema principale

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da 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[modifica | modifica wikitesto]

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

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

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-\varepsilon} \right) per \varepsilon > 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 -\varepsilon} \right) = O \left ( n^{\log_{b}a -\varepsilon} \left ( \frac{ab^{\varepsilon}}{b^{\log_{b}a}} \right)^{i} \right) = O \left(n^{\log_{b}a-\varepsilon} \left ( b^{\varepsilon} \right )^{i} \right ).


Per limitare T_A(n) possiamo scrivere:


T_A(n)= \sum_{i=0}^{\log_{b}n} O \left ( n^{\log_{b}a-\varepsilon} \left (b^{\varepsilon} \right )^{i}  \right ) = O \left ( n^{log_{b}a-\varepsilon} \sum_{i=0}^{\log_{b}n} \left(b^{\varepsilon}\right)^{i}\right ) = O \left (  n^{log_{b}a-\varepsilon}  \left ( \frac{b^{\varepsilon(\log_{b}n+1)}-1}{b^{\varepsilon}-1} \right) \right ) = O \left ( n^{log_{b}a-\varepsilon} \left ( \frac{b^{\varepsilon }n^{\varepsilon}-1}{b^{\varepsilon}-1} \right )\right ) = O \left  (n^{\log_{b}a-\varepsilon} n^{\varepsilon} \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[modifica | modifica wikitesto]

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

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

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

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

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

Caso 1[modifica | modifica wikitesto]

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

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

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

Voci correlate[modifica | modifica wikitesto]

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