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))\text{para }x\ge 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$
• $|g(x)|\in O(x^c)$, onde $c$é uma constante e $O$ denota a notação Grande-O.
• $|h_i(x)|\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 \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\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(\lfloor \frac{1}{2}n\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\le n\le 3$ e $n^2+\frac{7}{4}T\left(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{3}{4}n\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{array}{cc}T(x)& \in \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)\\ & =\mathrm{\Theta }\left(x^2(1+\underset{1}{\overset{x}{\int }}\frac{u^2}{u^3}du)\right)\\ & =\mathrm{\Theta }(x^2(1+\ln x))\\ & =\mathrm{\Theta }(x^2\log x).\end{array}$

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(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{1}{2}n\rceil \right)+n-1$

para inteiros $n>0$ e, portanto, pode ser calculado usando o método de Akra–Bazzi, onde obtém-se $\mathrm{\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