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
As condições para o uso são:
foram fornecidos casos base suficientes e são constantes para todo para todo para todo , onde é uma constante e denota a notação Grande-O. para todo é uma constante
O comportamento assintótico de é encontrado determinando o valor de no qual e substituindo esse valor na equação
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:
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
para inteiros e, portanto, pode ser calculado usando o método de Akra–Bazzi, onde obtém-se .
Referências
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
Categoria:Teoremas em matemática discreta Categoria:Análise de algoritmos Categoria:Complexidade de algoritmos Categoria:Análise assintótica Categoria:Relações de recorrência