Teorema mestre com condições relaxadas

O teorema mestre é o método mais conhecido para resolver equações de recorrência do paradigma de divisão e conquista, entretanto uma das grandes dificuldades ao aplicá-lo é identificar em qual dos três casos a recorrência se enquadra.

É possível relaxar as condições de cada caso e tornar o teorema mais simples, limitando o tipo de recorrência que o teorema é capaz de resolver.

Para tanto, parte-se do pressuposto de que a complexidade no tempo da etapa de conquista (normalmente denotada por $f(n)$) é representada por um polinômio.

Índice

• Relaxando as condições
• Exemplos
  • Merge sort
  • Busca binária
  • Algoritmo de Strassen
  • Multiplicação recursiva de matrizes
  • Exemplo sortido
• Considerações finais
• Leia também
• Referências

Relaxando as condições

O teorema mestre usual resolve equações de recorrência do tipo [1]

$$T(n)=aT(n/b)+f(n)$$

Contudo, ao resolver equações do paradigma de divisão e conquista, frequentemente $f(n)$ é um polinômio ou é limitado assintoticamente por algum polinômio.

Podemos derivar um "novo teorema mestre" se supormos que $f(n)$ é um polinômio:

Sejam as constantes $a\geq 1$, $b>1$, o número inteiro $k\geq 0$ e $T(n)$ definida no domínio dos números inteiros não negativos pela recorrência

$$T(n)=aT(n/b)+p_k(n)$$

onde $p_k(n)$ é um polinômio de grau $k$: $p_k(n)=a_kn^k+a_{k-1}n^{k-1}+\ldots a_1n+a_0$. Então, $T(n)$ tem os seguintes limites assintóticos

1. Se $k < \log_b a$, então $T(n)=\Theta\left(n^{\log_b a}\right)$;
2. Se $k=\log_b a$, então $T(n)=\Theta\left(n^k\log n\right)$;
3. Se $k>\log_b a$, então $T(n)=\Theta\left(n^k \right)$.

Se $p_k(n)$ for uma notação assintótica do tipo $\Theta(n^k)$ ou ainda $O(n^k)$, então o teorema anterior também funciona, bastando considerar a função dentro da notação assintótica como $p_k(n)$. Por exemplo

• Em $T(n)=T(n/3)+\Theta(n^2)$, $p_k(n)=n^2$;
• Em $T(n)=2T(n/2)+O(n)$, $p_k(n)=n$;
• Em $T(n)=2T(n/2)+\Theta(1)$, $p_k(n)=1$

Ir para o índice

Exemplos

A seguir, apresento alguns exemplos de recorrências de algoritmos conhecidos que podem ser resolvidos com esse teorema mestre simplificado.

Merge sort

A equação de recorrência do Merge Sort é

$$T(n)=2T(n/2)+\Theta(n)$$

Para essa recorrência, temos

$$a=2;\,b=2;\,k=1$$

Como $k=\log_b a=\log_2 2=1$, então o Merge Sort satisfaz o segundo caso. Portanto,

$$T(n)=\Theta(n\log n)$$

Ir para o índice

Busca binária

A recorrência da busca binária é

$$T(n)=T(n/2)+\Theta(1)$$

Para essa recorrência, temos

$$a=1;\,b=2;\,k=0$$

Como $k=\log_b a=\log_2 1=0$, então, assim como o Merge Sort, a busca binária satisfaz o segundo caso. Portanto,

$$T(n)= \Theta(n^0\log n) =\Theta(\log n)$$

Ir para o índice

Algoritmo de Strassen

A equação de recorrência do algoritmo de Strassen é

$$T(n)=7T(n/2)+\Theta(n^2)$$

Para essa recorrência, temos

$$a=7;\,b=2;\,k=2$$

Como $\log_b a=\log_2 7=2.807\ldots$ e $k < 2.807\ldots$, então a equação de recorrência do algoritmo de Strassen satisfaz o primeiro caso do teorema mestre

$$T(n)=\Theta\left(n^{\log_2 7}\right)= \Theta\left(n^{2.807\ldots }\right)$$

Ir para o índice

Multiplicação recursiva de matrizes

O algoritmo recursivo de multiplicação de matrizes possui a seguinte equação de recorrência

$$T(n)=8T(n/2)+\Theta(n^2)$$

As constantes são

$$a=8;\,b=2;\,k=2$$

Como $\log_b a=\log_2 8=3$ e $k < 3$, então a equação de recorrência do algoritmo satisfaz o primeiro caso do teorema mestre

$$T(n)=\Theta\left(n^{\log_2 8}\right)= \Theta\left(n^3\right)$$

Ir para o índice

Exemplo sortido

Seja a equação de recorrência

$$T(n)=2T(n/4)+n$$

As constantes são

$$a=2;\,b=4;\,k=1$$

Como $\log_b a=\log_4 2=\cfrac{1}{2}$ e $k > \cfrac{1}{2}$, então a equação de recorrência do algoritmo satisfaz o terceiro caso do teorema mestre

$$T(n)=\Theta\left(n^k\right)= \Theta\left(n\right)$$

Observação: no teorema mestre original, o terceiro caso exige a verificação de uma condição de regularidade. Como consideramos apenas os casos onde $f(n)$ é um polinômio, então não é necessário checar a condição, pois ela sempre será satisfeita.

Ir para o índice

Considerações finais

Observe que essa versão do teorema mestre é mais simples. Além de eliminar a necessidade de verificar a condição de regularidade no terceiro caso, também resume a verificação de cada caso a uma simples desigualdade, que é mais fácil do que ter que verificar se $f(n)$ é $O$, $\Theta$ ou $\Omega$ de alguma função.

É claro, essa simplificação teve um preço, que foi restringir $f(n)$ à polinômios. Aliás, esse teorema mestre relaxado foi protagonista da questão 21 do POSCOMP 2015.

Ir para o índice

Leia também

Aproveite e leia também os seguintes artigos

• Teorema Mestre e Exemplos Resolvidos
• Exercícios Resolvidos sobre o Teorema Mestre
• O Método de Akra-Bazzi na Resolução de Equações de Recorrência

Referências

• [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.