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.

Formulação

O método de Akra–Bazzi aplica-se a fórmulas de recorrência da forma

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

O comportamento assintótico de $T(x)$ é encontrado determinando o valor de $p$ no qual $\sum _{i=1}^{k}a_{i}b_{i}^{p}=1$ e substituindo esse valor na equação

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

Intuitivamente, $h_{i}(x)$ representa uma pequena perturbação no índice de $T$. Observando que $\lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)$ e que o valor absoluto de $\lfloor b_{i}x\rfloor -b_{i}x$ está sempre entre $0$ e $1$, $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, $T(n)=n+T\left({\frac {1}{2}}n\right)$ e $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.

Exemplo

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

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

$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 $n>0$ e, portanto, pode ser calculado usando o método de Akra–Bazzi, onde obtém-se $\Theta (n\log n)$.

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