Em ciência da computação, o método de Akra–Bazzi, ou teorema Akra–Bazzi, é utilizado para analisar o comportamento assintótico de recorrências que aparecem na análise de algoritmos de divisão e conquista onde o sub-problemas têm substancialmente diferentes tamanhos. É uma generalização do teorema mestre para recorrências de divisão e conquista, que assume que os sub-problemas possuem o mesmo tamanho. O método recebe o nome dos matemáticos Mohamad Akra e Louay Bazzi[1].
O método de Akra–Bazzi aplica-se a fórmulas de recorrência da forma[1]
![{\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\qquad {\text{para }}x\geq x_{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eccb31a0a29f84c9f4aad14ffa9dc1fcdfb1f2a)
As condições para o uso são:
- foram fornecidos casos base suficientes
e
são constantes para todo ![{\displaystyle i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
para todo ![{\displaystyle i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
para todo ![{\displaystyle i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
, onde
é uma constante e
denota a notação Grande-O.
para todo ![{\displaystyle i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/add78d8608ad86e54951b8c8bd6c8d8416533d20)
é uma constante
O comportamento assintótico de
é encontrado determinando o valor de
no qual
e substituindo esse valor na equação[2]
![{\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)
Intuitivamente,
representa uma pequena perturbação no índice de
. Observando que
e que o valor absoluto de
está sempre entre
e
,
pode ser usado para ignorar a função piso no índice. Da mesma forma, também se pode ignorar a função de teto. Por exemplo,
e
, conforme o teorema de Akra–Bazzi, têm o mesmo comportamento assintótico.
Exemplo
Suponha que
é definido como 1 para números inteiros
e
para inteiros
. Na aplicação do método de Akra–Bazzi, o primeiro passo é encontrar o valor de
tal que
. Nesse exemplo,
. Então, usando a fórmula, o comportamento assintótico pode ser determinado da seguinte forma[3]:![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4dcd61276328f7c7ec5bdc399b6e11114a2c68)
![{\displaystyle {\begin{aligned}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).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/249eac5c08cd10d641603171bb713c64f13274ea)
Significado
O método de Akra–Bazzi é mais útil do que a maioria de outras técnicas para a determinação do comportamento assintótico, pois cobre uma ampla variedade de casos. A sua principal aplicação é a aproximação do tempo de execução de muitos algoritmos de divisão e conquista. Por exemplo, no merge sort, o número de comparações necessárias, no pior caso, que é aproximadamente proporcional ao seu tempo de execução, é dado recursivamente como
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/ee73c5962f9a03da9b87e5f034fcb1cda756642b)
para inteiros
e, portanto, pode ser calculado usando o método de Akra–Bazzi, onde obtém-se
.
Referências
- ↑ a b «On the solution of linear recurrence equations». Computational Optimization and Applications. 10 – via Springer Link
- ↑ «Proof and application on few examples» (PDF)
- ↑ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford. Introduction to Algorithms. [S.l.: s.n.] ISBN 978-0262033848
Ver também
- Teorema mestre (análise de algoritmos)
- Complexidade assintótica
Ligações externas
O Método de Akra-Bazzi na Resolução de Equações de Recorrência