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.

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

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x)),}$

per ${\displaystyle x\geq x_{0}.}$

Le pre-condizioni sono:

• vi sono sufficienti casi base;
• ${\displaystyle a_{i}}$ e ${\displaystyle b_{i}}$ sono costanti per ogni ${\displaystyle i;}$
• ${\displaystyle a_{i}>0}$ per ogni ${\displaystyle i;}$
• ${\displaystyle 0<b_{i}<1}$ per ogni ${\displaystyle i;}$
• ${\displaystyle \left|g'(x)\right|\in O(x^{c})}$, dove ${\displaystyle c}$ è una costante e ${\displaystyle O}$ è la notazione O grande;
• ${\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}$ per ogni ${\displaystyle i;}$
• ${\displaystyle x_{0}}$ è una costante.

Il comportamento asintotico di ${\displaystyle T(x)}$ si trova determinando il valore di ${\displaystyle p}$ per cui ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}$, sostituendolo poi nell'equazione

${\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\right)}$

(si veda Θ). Intuitivamente ${\displaystyle h_{i}(x)}$ rappresenta una perturbazione piccola nell'indice di ${\displaystyle T.}$ notando che

${\displaystyle \lfloor b_{i}\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$

e

${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$

sono sempre comprese tra 0 e 1, ${\displaystyle 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, ${\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}$ e ${\displaystyle 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.

Sia

${\displaystyle T(n)={\begin{cases}1,&{\text{se }}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),&{\text{se }}n>3.\end{cases}}}$

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

${\displaystyle 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).}$

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 ${\displaystyle T(1)=0}$ e

${\displaystyle 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 ${\displaystyle n>0}$, e può essere valutato come ${\displaystyle \Theta (n\log n)}$.

• (EN) Mohamad Akra, Louay Bazzi, On the solution of linear recurrence equations, in Computational Optimization and Applications, vol. 10, n. 2, 1998, pp. 195-210.
• (EN) Tom Leighton, Notes on Better Master Theorems for Divide-and-Conquer Recurrences (manoscritto, 9 pagine), Massachusetts Institute of Technology, 1996.

• Teorema principale
• Teoria della complessità algoritmica

• O Método de Akra-Bazzi na Resolução de Equações de Recorrência (PT)