Metodo di Akra-Bazzi

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 si assume che i sottoproblemi abbiano invece dimensioni simili.

La formula

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)),$

per $x\ge 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;$
• $|g^{\prime }(x)|\in O(x^c)$, dove $c$ è una costante e $O$ è la notazione O grande;
• $|h_i(x)|\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 \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)$

(si veda Θ). Intuitivamente $h_i(x)$ rappresenta una perturbazione 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 si può fare per la parte intera superiore.

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

Un esempio

Sia

$T(n)=\{\begin{array}{cc}1,& \text{se }0\le n\le 3,\\ n^2+\frac{7}{4}T\left(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{3}{4}n\rceil \right),& \text{se }n>3.\end{array}$

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, si ha per il comportamento asintotico

$T(x)\in \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)=\mathrm{\Theta }\left(x^2(1+\underset{1}{\overset{x}{\int }}\frac{u^2}{u^3}du)\right)=\mathrm{\Theta }(x^2(1+\ln x))=\mathrm{\Theta }(x^2\log x).$

Impiego

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(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{1}{2}n\rceil \right)+n-1,$

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

Bibliografia

• Template:Cita pubblicazione
• Template:Cita pubblicazione

Voci correlate

• Teorema principale
• Teoria della complessità algoritmica

Collegamenti esterni

• O Método de Akra-Bazzi na Resolução de Equações de Recorrência Template:Pt icon