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≥1, b>1, o número inteiro k≥0 e T(n) definida no domínio dos números inteiros não negativos pela recorrência
T(n)=aT(n/b)+pk(n)
onde pk(n) é um polinômio de grau k: pk(n)=aknk+ak−1nk−1+…a1n+a0. Então, T(n) tem os seguintes limites assintóticos
- Se k<logba, então T(n)=Θ(nlogba);
- Se k=logba, então T(n)=Θ(nklogn);
- Se k>logba, então T(n)=Θ(nk).
Se pk(n) for uma notação assintótica do tipo Θ(nk) ou ainda O(nk), então o teorema anterior também funciona, bastando considerar a função dentro da notação assintótica como pk(n). Por exemplo
- Em T(n)=T(n/3)+Θ(n2), pk(n)=n2;
- Em T(n)=2T(n/2)+O(n), pk(n)=n;
- Em T(n)=2T(n/2)+Θ(1), pk(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)+Θ(n)
Para essa recorrência, temos
a=2;b=2;k=1
Como k=logba=log22=1, então o Merge Sort satisfaz o segundo caso. Portanto,
T(n)=Θ(nlogn)
Busca binária
A recorrência da busca binária é
T(n)=T(n/2)+Θ(1)
Para essa recorrência, temos
a=1;b=2;k=0
Como k=logba=log21=0, então, assim como o Merge Sort, a busca binária satisfaz o segundo caso. Portanto,
T(n)=Θ(n0logn)=Θ(logn)
Algoritmo de Strassen
A equação de recorrência do algoritmo de Strassen é
T(n)=7T(n/2)+Θ(n2)
Para essa recorrência, temos
a=7;b=2;k=2
Como logba=log27=2.807… e k<2.807…, então a equação de recorrência do algoritmo de Strassen satisfaz o primeiro caso do teorema mestre
T(n)=Θ(nlog27)=Θ(n2.807…)
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)+Θ(n2)
As constantes são
a=8;b=2;k=2
Como logba=log28=3 e k<3, então a equação de recorrência do algoritmo satisfaz o primeiro caso do teorema mestre
T(n)=Θ(nlog28)=Θ(n3)
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 logba=log42=12 e k>12, então a equação de recorrência do algoritmo satisfaz o terceiro caso do teorema mestre
T(n)=Θ(nk)=Θ(n)
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, Θ ou Ω 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