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)),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43afa42b6af6759fbe81508c190bd3c5f323f4d3)
per
Le pre-condizioni sono:
- vi sono sufficienti casi base;
e
sono costanti per ogni ![{\displaystyle i;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0b76142d363a9c36ce05c893bebe6a40e20396)
per ogni ![{\displaystyle i;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0b76142d363a9c36ce05c893bebe6a40e20396)
per ogni ![{\displaystyle i;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0b76142d363a9c36ce05c893bebe6a40e20396)
, dove
è una costante e
è la notazione O grande;
per ogni ![{\displaystyle i;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0b76142d363a9c36ce05c893bebe6a40e20396)
è una costante.
Il comportamento asintotico di
si trova determinando il valore di
per cui
, 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a35d0d6ec3f950deee27e776fd22a13d4f8d4fe2)
(si veda Θ). Intuitivamente
rappresenta una perturbazione piccola nell'indice di
notando che
![{\displaystyle \lfloor b_{i}\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c8ea255fd5040b8f2616b1877503e830a35f660)
e
![{\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71d0b84f3909bca7d1d168fd6f38ef40c385f808)
sono sempre comprese tra 0 e 1,
può essere utilizzato per escludere la parte intera nell'indice, e lo stesso si può fare per la parte intera superiore.
Quindi,
e
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3d3fe69440f3e285fc58e7393fb17137949122f)
Applicando il metodo, il primo passo consiste nel trovare il valore di
per cui
. Nell'esempio proposto,
. Usando quindi la formula, sia 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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c28a942714a8cb065a10b140b3405c0e7ff3490)
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
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6634ca6438a8a6b053adf4137e770ab1c074545)
per gli
, e può essere valutato come
.
- (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.