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

Por
| 

Introdução

O método de Akra-Bazzi é um dos métodos mais poderosos para solucionar relações de recorrência advindas, principalmente, de algoritmos de divisão e conquista. Tal método abrange uma quantidade muito maior de relações de recorrência que o Teorema Mestre.

Enquanto o Teorema Mestre resolve apenas recorrências do tipo $$T(n) = aT(n/b) + f(n), \quad \text{(1)}$$ com certas restrições em $f(n)$, o método de Akra-Bazzi é capaz de resolver relações de recorrência da forma $$T(n)=\begin{cases} c_0,\quad n=x_0\\ \sum_{i=1}^k a_iT\left(b_i n\right)+f(n),\quad n>x_0 \end{cases} \quad \text{(2)}$$ onde $a_i > 0$, $0 < b_i < 1$, $c_0\in\mathbb{R}$, $x_0\in\mathbb{N}$, $k\geq 1$ e $f(n)$ é uma função que deve satisfazer a condição de crescimento polinomial

Versão original do método é bem mais detalhada. Aqui, estou utilizando a versão do método apresentada por Cormen em seu livro "Algortimos - Teoria e Prática", porém foram feitas algumas simplificações que serão suficientes para os objetivos do presente texto, entretanto a "essência" do método é a mesma.

Comentários 0