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)+\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
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