Teorema mestre com condições relaxadas

Por
| 

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.

Teorema mestre com condições relaxadas

Í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 a1, b>1, o número inteiro k0 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+ak1nk1+a1n+a0. Então, T(n) tem os seguintes limites assintóticos

  1. Se k<logba, então T(n)=Θ(nlogba);
  2. Se k=logba, então T(n)=Θ(nklogn);
  3. 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

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)+Θ(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)

Ir para o índice

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)

Ir para o índice

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)

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)+Θ(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)

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 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.

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, Θ 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.

Ir para o índice

Leia também

Aproveite e leia também os seguintes artigos

Referências

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar