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
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
- Se $k < \log_b a$, então $T(n)=\Theta\left(n^{\log_b a}\right)$;
- Se $k=\log_b a$, então $T(n)=\Theta\left(n^k\log n\right)$;
- 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$
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)$$
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)$$
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)$$
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)$$
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.
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.
Leia também
Aproveite e leia também os seguintes artigos
Referências
- [1] CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.
Nenhum comentário:
Postar um comentário