Método de Akra–Bazzi

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}.}$

As condições para o uso são:

• foram fornecidos casos base suficientes
• ${\displaystyle a_{i}}$ e ${\displaystyle b_{i}}$ são constantes para todo ${\displaystyle i}$
• ${\displaystyle a_{i}>0}$ para todo ${\displaystyle i}$
• ${\displaystyle 0<b_{i}<1}$ para todo ${\displaystyle i}$
• ${\displaystyle \left|g(x)\right|\in O(x^{c})}$, onde ${\displaystyle c}$é uma constante e ${\displaystyle O}$ denota a notação Grande-O.
• ${\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}$ para todo ${\displaystyle i}$
• ${\displaystyle x_{0}}$ é uma constante

O comportamento assintótico de ${\displaystyle T(x)}$ é encontrado determinando o valor de ${\displaystyle p}$ no qual ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}$ 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)}$

Intuitivamente, ${\displaystyle h_{i}(x)}$ representa uma pequena perturbação no índice de ${\displaystyle T}$. Observando que ${\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$ e que o valor absoluto de ${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$ está sempre entre ${\displaystyle 0}$ e ${\displaystyle 1}$, ${\displaystyle h_{i}(x)}$ 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, ${\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)}$, conforme o teorema de Akra–Bazzi, têm o mesmo comportamento assintótico.

Suponha que ${\displaystyle T(n)}$ é definido como 1 para números inteiros ${\displaystyle 0\leq n\leq 3}$ e ${\displaystyle 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)}$ para inteiros ${\displaystyle n>3}$. Na aplicação do método de Akra–Bazzi, o primeiro passo é encontrar o valor de ${\displaystyle p}$ tal que ${\displaystyle {\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1}$. Nesse exemplo, ${\displaystyle p=2}$. Então, usando a fórmula, o comportamento assintótico pode ser determinado da seguinte forma^[3]:${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$

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

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

para inteiros ${\displaystyle n>0}$ e, portanto, pode ser calculado usando o método de Akra–Bazzi, onde obtém-se ${\displaystyle \Theta (n\log n)}$.

• Teorema mestre (análise de algoritmos)
• Complexidade assintótica

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