Exercícios Resolvidos sobre o Teorema Mestre

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)
• Exercício 2 (multiplicação recursiva de matrizes)
• Exercício 3 (algoritmo de Strassen)
• Exercício 4
• Exercício 5
• Exercício 6
• Exercício 7
• Exercício 8 (busca binária)
• Exercício 9
• Exercício 10
• Exercício 11
• Exercício 12
• Exercício 13
• Exercício 14
• Leia também
• Referências

Exercício 1 (Merge Sort)

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

$$T(n)=2T(n/2)+\Theta(n)$$

Para essa recorrência, temos

$$a=2,\quad b=2,\quad f(n)=\Theta(n)$$

e ainda

$$\log_b a=\log_2 2=1$$

Vamos assumir que $f(n)=n$. Oberve que o caso 1 não se aplica, pois não é possível encontrar um $\epsilon>0$ tal que $f(n)=O(n^{1-\epsilon})$.

A recorrência satisfaz o caso 2, pois $f(n)=\Theta(n^{\log_b a})=\Theta(n)$. Portanto, $T(n)=\Theta(n^{\log_b a}\log n)=\Theta(n\log n)$.

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)+\Theta(n^2)$$

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

$$a=8,\quad b=2,\quad f(n)=n^2$$

$$\log_b a = \log_2 8=3$$

Para o primeiro caso, temos que verificar se $f(n)=O(n^{3-\epsilon})$, para algum $\epsilon>0$.

Escolhendo $\epsilon=1$, o caso 1 é automaticamente satisfeito: $f(n)=O(n^{3-\epsilon})=O(n^{3-1})=O(n^2)$. Portanto, $T(n)=\Theta(n^{\log_b a})=\Theta(n^3)$.

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)+\Theta(n^2)$$

Iniciamos calculando o logaritmo

$$\log_b a=\log_2 7$$

O logaritmo anterior é um número irracional: $\log_2 7=2,8073549221\ldots$.

Analisando o primeiro caso, temos $f(n)=O(n^{\log_2 7-\epsilon})=O(n^{2,8073549221\ldots-\epsilon})$. Essa igualdade é válida, pois, como $f(n)=n^2$, poderíamos escolher $\epsilon=0,8073549221\ldots$. Dessa forma, teríamos $f(n)=O(n^2)$.

Portanto, $T(n)=\Theta(n^{\log_b a})=\Theta(n^{\log_2 7})$. O algoritmo tradicional de multiplicação de matrizes tem complexidade $\Theta(n^3)$, logo o algoritmo de Strassen é mais rápido.

Exercício 4

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

$$a=2,\quad b=4,\quad f(n)=1$$

$$\log_b a=\log_4 2=\frac{1}{2}$$

Primeiro caso: $f(n)=O(n^{1/2-\epsilon})$. A igualdade anterior é verdadeira se escolhermos, por exemplo, $\epsilon=1/2$, pois teríamos $f(n)=O(1)$.

Portanto, pelo primeiro caso do teorema mestre, teremos $T(n)=\Theta(n^{\log_b a})=\Theta(n^{1/2})=\Theta(\sqrt{n})$.

Exercício 5

Recorrência: $T(n)=2T(n/4)+\sqrt{n}$

$$a=2,\quad b=4,\quad f(n)=\sqrt{n}$$

$$\log_b a=\log_4 2=\frac{1}{2}$$

Observe que $f(n)$ é igual a $n^{\log_b a}$, portanto essa recorrência satisfaz o segundo caso do teorema mestre

$$T(n)=\Theta(n^{\log_b a}\log n)=\Theta(\sqrt{n}\log n)$$

Exercício 6

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

$$a=2,\quad b=4,\quad f(n)=n$$

$$\log_b a=\log_4 2=\frac{1}{2}$$

Uma vez que $f(n)=n$ é assintoticamente maior que $n^{\log_b a}=\sqrt{n}$, então os casos 1 e 2 não se aplicam.

Para o terceiro caso, devemos, primeiramente, encontrar um $\epsilon$ tal que $f(n)=\Omega(n^{1/2+\epsilon})$. Se escolhermos $\epsilon=1/2$, então $f(n)=\Omega(n)$, que é uma igualdade verdadeira.

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

$$\begin{align*}af(n/b)&\leq cf(n)\\2\times\frac{n}{4}&\leq cn\\\frac{1}{2}n&\leq cn\end{align*}$$

Podemos escolher $c=\cfrac{1}{2}<1$, que a desigualdade será sempre válida. Portanto, a recorrência satisfaz o terceiro caso do teorema mestre

$$T(n)=\Theta(f(n))=\Theta(n)$$

Exercício 7

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

$$a=2,\quad b=4,\quad f(n)=n^2$$

$$\log_b a=\log_4 2=\frac{1}{2}$$

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

Primeiramente, podemos escolher $\epsilon=3/2$, por exemplo, pois teremos $f(n)=\Omega(n^{1/2+3/2})=\Omega(n^2)$, que é válido.

Agora, basta analisar a condição de regularidade

$$\begin{align*}af(n/b)&\leq cf(n)\\2\times\frac{n^2}{16}&\leq cn^2\\\frac{n^2}{8}&\leq cn^2\\\frac{1}{8}&\leq c\end{align*}$$

No último passo, os dois membros da desigualdade foram divididos por $n^2$, 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)=\Theta(f(n))=\Theta(n^2)$$

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)+\Theta(1)$ é $T(n)=\Theta(\lg n)$.

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

$$T(n)=\Theta(n^{\log_b a}\lg n)=\Theta(n^0\lg n)=\Theta(\lg n)$$

Exercício 9

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

$$a=2,\quad b=2,\quad f(n)=n^4$$

$$\log_b a=\log_2 2=1$$

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

$$\begin{align*}f(n)&=n^4\\&=\Omega(n^{1+\epsilon})\\&=\Omega(n^{1+3})\\&=\Omega(n^4)\end{align*}$$

Agora, basta analisar a condição de regularidade

$$\begin{align*}af(n/b)&\leq cf(n)\\2\times\frac{n^4}{16}&\leq cn^4\\\frac{1}{8}n^4&\leq cn^4\\\frac{1}{8}&\leq c\end{align*}$$

Podemos escolher $c=\cfrac{1}{8}$, que a condição é satisfeita. Portanto, $T(n)$ satisfaz o terceiro caso do teorema mestre:

$$T(n)=\Theta(f(n))=\Theta(n^4)$$

Exercício 10

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

$$a=1,\quad b=\frac{10}{7},\quad f(n)=n$$

$$\log_b a=\log_{10/7} 1=0$$

$f(n)$ é assintoticamente maior que $n^{\log_b a} = 1$, então podemos ir direto para caso 3.

Para $\epsilon=1$, temos que $f(n)=\Omega(n^{0+1})=\Omega(n)$. Vamos analisar a condição de regularidade

$$\begin{align*}af(n/b)&\leq cf(n)\\\frac{7}{10}n&\leq cn\end{align*}$$

Podemos escolher $c=\cfrac{7}{10}$, que a condição é satisfeita. Portanto, $T(n)$ satisfaz o terceiro caso do teorema mestre:

$$T(n)=\Theta(f(n))=\Theta(n)$$

Exercício 11

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

$$a=16,\quad b=4,\quad f(n)=n^2$$

$$\log_b a=\log_4 16=2$$

Como $n^{\log_b a}$ é igual a $f(n)$, então a recorrência satisfaz o segundo caso do teorema mestre

$$T(n)=\Theta(n^{\log_b a}\log n)=\Theta(n^2\log n)$$

Exercício 12

Recorrência: $T(n)=2T(n/4)+\sqrt{n}$

$$a=2,\quad b=4,\quad f(n)=\sqrt{n}=n^{1/2}$$

$$\log_b a=\log_4 2=\frac{1}{2}$$

Como $n^{\log_b a} = n^{1/2}$ é igual a $f(n)$, então a recorrência satisfaz o segundo caso do teorema mestre

$$T(n)=\Theta(n^{\log_b a}\log n)=\Theta(\sqrt{n}\log n)$$

Exercício 13

Recorrência: $T(n)=7T(n/3)+n^2$

$$a=7,\quad b=3,\quad f(n)=n^2$$

$$\log_b a=\log_3 7=1,7712\ldots$$

$f(n)=n^2$ é assintoticamente maior que $n^{\log_b a} = n^{1,7712\ldots}$, então podemos ir direto para caso 3.

Para $\epsilon=0,22875626\ldots$, temos que $f(n)=\Omega(n^{1,7712\ldots+0,2287\ldots})=\Omega(n^2)$. O valor 0,2287... foi escolhido para que a soma dele com $\log_b a$ seja 2, apenas por conveniência. Vamos analisar a condição de regularidade

$$\begin{align*}af(n/b)&\leq cf(n)\\7\times\frac{n^2}{9}&\leq cn^2\\\frac{7}{9}n^2&\leq cn^2\\\frac{7}{9}&\leq c\end{align*}$$

Podemos escolher $c=\cfrac{7}{9}$, que a condição é satisfeita. Portanto, $T(n)$ satisfaz o terceiro caso do teorema mestre:

$$T(n)=\Theta(f(n))=\Theta(n^2)$$

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\times n/4$, e, juntas, as etapas de dividir e combinar levarão o tempo $\Theta(n^2)$. 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)+\Theta(n^2)$. 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á

$$\begin{align*}T_C(n)&=\Theta(n^{\log_b a})\\&=\Theta(n^{\log_4 a})\\&=\Theta(n^{\frac{1}{2}\log_2 a})\end{align*}$$

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

A complexidade do algoritmo de Strassen é de $T_S(n)=\Theta(n^{\log_2 7})$. O enunciado quer $T_C(n)<T_S(n)$, o que nos leva a

$$\begin{align*}T_C(n)&<T_S(n)\\\Theta(n^{\frac{1}{2}\log_2 a})&<\Theta(n^{\log_2 7})\\n^{\frac{1}{2}\log_2 a}&<n^{\log_2 7}\\\frac{1}{2}\log_2 a&<\log_2 7\\\log_2 a&<2\log_2 7\\\log_2 a&<\log_2 7^2\\\log_2 a&<\log_2 49\\a&<49\end{align*}$$

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

• Teorema Mestre e Exemplos Resolvidos
• O Método de Akra-Bazzi na Resolução de Equações de Recorrência
• Teorema mestre com condições relaxadas

Referências

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