Exercícios Resolvidos sobre o Teorema Mestre

Por
| 

O objetivo deste artigo é disponibilizar ao leitor uma lista de exercícios resolvidos sobre o teorema mestre. A maioria dos exercícios foi retirada do livro Algoritmos: teoria e prática (CORMEN et al, 2012).

O teorema mestre é utilizado para resolver recorrências de algoritmos do paradigma de divisão e conquista. Ele fornece a solução de três tipos específicos de recorrências, porém esses três tipos abrangem boa parte das recorrências dos algoritmos desse paradigma.

Exercícios sobre o Teorema Mestre

Índice

Exercício 1 (Merge Sort)

A recorrência a seguir é do algoritmo de ordenação Merge Sort

T(n)=2T(n/2)+Θ(n)

Para essa recorrência, temos

a=2,b=2,f(n)=Θ(n)

e ainda

logba=log22=1

Vamos assumir que f(n)=n. Oberve que o caso 1 não se aplica, pois não é possível encontrar um ϵ>0 tal que f(n)=O(n1ϵ).

A recorrência satisfaz o caso 2, pois f(n)=Θ(nlogba)=Θ(n). Portanto, T(n)=Θ(nlogbalogn)=Θ(nlogn).

Exercício 2 (multiplicação recursiva de matrizes)

A próxima recorrência é da versão recursiva do algoritmo de multiplicação de matrizes

T(n)=8T(n/2)+Θ(n2)

Vamos assumir que f(n)=n2, que é a função na notação assintótica. Assim,

a=8,b=2,f(n)=n2

logba=log28=3

Para o primeiro caso, temos que verificar se f(n)=O(n3ϵ), para algum ϵ>0.

Escolhendo ϵ=1, o caso 1 é automaticamente satisfeito: f(n)=O(n3ϵ)=O(n31)=O(n2). Portanto, T(n)=Θ(nlogba)=Θ(n3).

Ou seja, a versão recursiva tem a mesma complexidade da versão iterativa.

Exercício 3 (algoritmo de Strassen)

O algoritmo de Strassen é um algoritmo de multiplicação de matrizes ligeiramente mais eficaz do que o algoritmo de multiplicação usual.

Neste exercício, vamos calcular o quão mais rápido ele é. A relação de recorrência do algoritmo de Strassen é apresentada a seguir

T(n)=7T(n/2)+Θ(n2)

Iniciamos calculando o logaritmo

logba=log27

O logaritmo anterior é um número irracional: log27=2,8073549221.

Analisando o primeiro caso, temos f(n)=O(nlog27ϵ)=O(n2,8073549221ϵ). Essa igualdade é válida, pois, como f(n)=n2, poderíamos escolher ϵ=0,8073549221. Dessa forma, teríamos f(n)=O(n2).

Portanto, T(n)=Θ(nlogba)=Θ(nlog27). O algoritmo tradicional de multiplicação de matrizes tem complexidade Θ(n3), logo o algoritmo de Strassen é mais rápido.

Exercício 4

Recorrência: T(n)=2T(n/4)+1

a=2,b=4,f(n)=1

logba=log42=12

Primeiro caso: f(n)=O(n1/2ϵ). A igualdade anterior é verdadeira se escolhermos, por exemplo, ϵ=1/2, pois teríamos f(n)=O(1).

Portanto, pelo primeiro caso do teorema mestre, teremos T(n)=Θ(nlogba)=Θ(n1/2)=Θ(n).

Exercício 5

Recorrência: T(n)=2T(n/4)+n

a=2,b=4,f(n)=n

logba=log42=12

Observe que f(n) é igual a nlogba, portanto essa recorrência satisfaz o segundo caso do teorema mestre

T(n)=Θ(nlogbalogn)=Θ(nlogn)

Exercício 6

Recorrência: T(n)=2T(n/4)+n

a=2,b=4,f(n)=n

logba=log42=12

Uma vez que f(n)=n é assintoticamente maior que nlogba=n, então os casos 1 e 2 não se aplicam.

Para o terceiro caso, devemos, primeiramente, encontrar um ϵ tal que f(n)=Ω(n1/2+ϵ). Se escolhermos ϵ=1/2, então f(n)=Ω(n), que é uma igualdade verdadeira.

Agora, precisamos verificar se a condição de regularidade também é satisfeita

af(n/b)cf(n)2×n4cn12ncn

Podemos escolher c=12<1, que a desigualdade será sempre válida. Portanto, a recorrência satisfaz o terceiro caso do teorema mestre

T(n)=Θ(f(n))=Θ(n)

Exercício 7

Recorrência: T(n)=2T(n/4)+n2

a=2,b=4,f(n)=n2

logba=log42=12

Como f(n) é assintoticamente maior que n1/2, então podemos pular a análise dos casos 1 e 2 e ir direto para o caso 3.

Primeiramente, podemos escolher ϵ=3/2, por exemplo, pois teremos f(n)=Ω(n1/2+3/2)=Ω(n2), que é válido.

Agora, basta analisar a condição de regularidade

af(n/b)cf(n)2×n216cn2n28cn218c

No último passo, os dois membros da desigualdade foram divididos por n2, que é não negativo e, portanto, o sentido da desigualdade não é alterado.

Observe que a constante c pode ser qualquer valor maior ou igual a 1/8 e menor do que um. Por exemplo, c=1/8 ou c=1/3 satisfazem a condição.

Portanto, a recorrência satisfaz o terceiro caso do teorema mestre

T(n)=Θ(f(n))=Θ(n2)

Exercício 8 (busca binária)

[CORMEN 4.5-3] Use o método mestre para mostrar que a solução para a recorrência da busca binária T(n)=T(n/2)+Θ(1) é T(n)=Θ(lgn).

Solução: para a recorrência em questão, temos a=1 e b=2. Inicialmente, calculamos o valor de logba, que é log21=0. Uma vez que f(n)=Θ(n0)=Θ(1), então a recorrência da busca binária satisfaz o caso 2 do teorema mestre, portanto

T(n)=Θ(nlogbalgn)=Θ(n0lgn)=Θ(lgn)

Exercício 9

Recorrência: T(n)=2T(n/2)+n4

a=2,b=2,f(n)=n4

logba=log22=1

f(n) é assintoticamente maior que n, então podemos pular direto para caso 3 do teorema mestre:

f(n)=n4=Ω(n1+ϵ)=Ω(n1+3)=Ω(n4)

Agora, basta analisar a condição de regularidade

af(n/b)cf(n)2×n416cn418n4cn418c

Podemos escolher c=18, que a condição é satisfeita. Portanto, T(n) satisfaz o terceiro caso do teorema mestre:

T(n)=Θ(f(n))=Θ(n4)

Exercício 10

Recorrência: T(n)=T(7n/10)+n

a=1,b=107,f(n)=n

logba=log10/71=0

f(n) é assintoticamente maior que nlogba=1, então podemos ir direto para caso 3.

Para ϵ=1, temos que f(n)=Ω(n0+1)=Ω(n). Vamos analisar a condição de regularidade

af(n/b)cf(n)710ncn

Podemos escolher c=710, que a condição é satisfeita. Portanto, T(n) satisfaz o terceiro caso do teorema mestre:

T(n)=Θ(f(n))=Θ(n)

Exercício 11

Recorrência: T(n)=16T(n/4)+n2

a=16,b=4,f(n)=n2

logba=log416=2

Como nlogba é igual a f(n), então a recorrência satisfaz o segundo caso do teorema mestre

T(n)=Θ(nlogbalogn)=Θ(n2logn)

Exercício 12

Recorrência: T(n)=2T(n/4)+n

a=2,b=4,f(n)=n=n1/2

logba=log42=12

Como nlogba=n1/2 é igual a f(n), então a recorrência satisfaz o segundo caso do teorema mestre

T(n)=Θ(nlogbalogn)=Θ(nlogn)

Exercício 13

Recorrência: T(n)=7T(n/3)+n2

a=7,b=3,f(n)=n2

logba=log37=1,7712

f(n)=n2 é assintoticamente maior que nlogba=n1,7712, então podemos ir direto para caso 3.

Para ϵ=0,22875626, temos que f(n)=Ω(n1,7712+0,2287)=Ω(n2). O valor 0,2287... foi escolhido para que a soma dele com logba seja 2, apenas por conveniência. Vamos analisar a condição de regularidade

af(n/b)cf(n)7×n29cn279n2cn279c

Podemos escolher c=79, que a condição é satisfeita. Portanto, T(n) satisfaz o terceiro caso do teorema mestre:

T(n)=Θ(f(n))=Θ(n2)

Exercício 14

[CORMEN 4.5-2] O professor César quer desenvolver um algoritmo para multiplicação de matrizes que seja assintoticamente mais rápido do que o algoritmo de Strassen. Seu algoritmo usará o método de divisão e conquista, repartindo cada matriz em pedaços de tamanho n/4×n/4, e, juntas, as etapas de dividir e combinar levarão o tempo Θ(n2). Ele precisa determinar quantos subproblemas tal algoritmo tem de criar para superar o algoritmo de Strassen. Se o algoritmo criar a subproblemas, a recorrência para o tempo de execução T(n) se tornará T(n)=aT(n/4)+Θ(n2). Qual é o maior valor inteiro de a para o qual o algoritmo do professor César seria assintoticamente mais rápido que o algoritmo de Strassen?

Solução: para valores grandes de a, a recorrência se enquadra no primeiro caso do teorema mestre. Portanto, a complexidade do algoritmo do professor César será

TC(n)=Θ(nlogba)=Θ(nlog4a)=Θ(n12log2a)

Na última etapa, eu mudei a base do logaritmo de 4 para 2.

A complexidade do algoritmo de Strassen é de TS(n)=Θ(nlog27). O enunciado quer TC(n)<TS(n), o que nos leva a

TC(n)<TS(n)Θ(n12log2a)<Θ(nlog27)n12log2a<nlog2712log2a<log27log2a<2log27log2a<log272log2a<log249a<49

Portanto, o maior valor de a para que o algoritmo do professor César seja assintoticamente mais rápido que o algoritmo de Strassen é 48.

Referência deste exercício: CLRS - Exercise 4.5-2

Leia também

Aproveite e leia também os seguintes artigos

Referências

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

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