Metodo di Akra-Bazzi

Da Wikipedia, l'enciclopedia libera.

In informatica, il metodo Akra-Bazzi, o teorema Akra-Bazzi, è utilizzato per analizzare il comportamento asintotico delle ricorrenze matematiche che appaiono nello studio degli algoritmi divide et impera, in cui i diversi sottoproblemi hanno dimensioni decisamente differenti. È una generalizzazione del teorema principale, in cui i si assume che i sottoproblemi abbiano invece dimensioni simili.


La formula[modifica | modifica sorgente]

Il metodo Akra-Bazzi si applica alle formule ricorsive del tipo

T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x)) for x \geq x_0.

Le pre-condizioni sono

  • vi sono sufficienti casi base
  • a_i e b_i sono costanti per ogni i
  • a_i > 0 per ogni i
  • 0 < b_i < 1 per ogni i
  • \left|g'(x)\right| \in O(x^c), dove c è una costante e O è la notazione O grande
  • \left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right) per ogni i
  • x_0 è una costante

Il comportamento asintotico di T(x) si trova determinando il valore di p per cui \sum_{i=1}^k a_i b_i^p = 1, sostituendolo poi nell'equazione

T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)

(vedi Θ). Intuitivamente h_i(x) rappresenta una pertubazione piccola nell'indice di T. notando che

\lfloor b_i  \rfloor = b_i x + (\lfloor b_i x \rfloor - b_i x)

e

\lfloor b_i x \rfloor - b_i x

sono sempre comprese tra 0 e 1, h_i(x) può essere utilizzato per escludere la parte intera nell'indice, e lo stesso di può fare per la parte intera superiore.

Quindi, T(n) = n + T \left(\frac{1}{2} n \right) e T(n) = n + T \left(\left\lfloor \frac{1}{2} n \right\rfloor \right) avranno, ai fini del metodo Akra-Bazzi, lo stesso comportamento asintotico.

Un esempio[modifica | modifica sorgente]

Sia T(n),\,n\in\mathbb{N} definita come

1 per gli 0 \leq n \leq 3
n^2 + \frac{7}{4} T \left( \left\lfloor \frac{1}{2} n \right\rfloor \right) + T \left( \left\lceil \frac{3}{4} n \right\rceil \right) per n > 3

Applicando il metodo, il primo passo consiste nel trovare il valore di p per cui \frac{7}{4} \left(\frac{1}{2}\right)^p + \left(\frac{3}{4} \right)^p = 1. Nell'esempio proposto, p = 2. Usando quindi la formula, sia ha per il comportamento asintotico

T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}\,du \right)\right)
=\Theta \left( x^2 \left( 1+\int_1^x \frac{u^2}{u^3}\,du \right)\right)
=\Theta(x^2(1 + \ln x))
=\Theta(x^2 \log x).

Impiego[modifica | modifica sorgente]

Il metodo Akra-Bazzi è più utile di molte altre tecniche in quanto copre un ventaglio molto ampio di casi. La sua principale applicazione è l'approssimazione del tempo di esecuzione di molti algoritmi divide et impera. Ad esempio nel merge sort, il numero di comparazioni richieste nel caso peggiore, che è all'incirca proporzionale al tempo di esecuzione, è dato ricorsivamente da T(1) = 0 e

T(n) = T\left(\left\lfloor \frac{1}{2} n \right\rfloor \right) + T\left(\left\lceil \frac{1}{2} n \right\rceil \right) + n - 1

per gli n > 0, e può essere valutato come \Theta(n \log n).

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]