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.

Í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(n3−1)=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×n4≤cn12n≤cn
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×n216≤cn2n28≤cn218≤c
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×n416≤cn418n4≤cn418≤c
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)710n≤cn
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×n29≤cn279n2≤cn279≤c
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.
Nenhum comentário:
Postar um comentário