O teorema mestre é um dos métodos mais conhecidos para resolver relações de recorrências provenientes de algoritmos do paradigma de divisão e conquista.
Comparado com outros métodos, ele é simples e intuitivo. Além disso, ele resolve boa parte das relações de recorrência desse paradigma. É claro, não estou dizendo que ele é fácil ou difícil, pois isso depende de cada um.
O objetivo da postagem é apresentar o teorema mestre e alguns exemplos resolvidos.
O texto tem caráter complementar, portanto eu recomendo que você consulte livros que abordam o assunto para ter referências mais ricas sobre o teorema mestre e não limite-se apenas a este artigo.
Índice
O Teorema
Para entender o teorema, é necessário que você conheça as notações assintóticas $O$, $\Theta$ e $\Omega$. Caso você não conheça essas notações, procure alguma referência para aprendê-las.
Em síntese, o teorema mestre resolve recorrências que possuem a seguinte forma
$$T(n)=aT(n/b)+f(n)$$
$n$ é o tamanho do problema. Os valores de $a$ e de $b$ são constantes. Em particular, o valor de $a$ é igual ao número de subproblemas no qual o problema original foi dividido. O valor $n/b$ é o tamanho de cada um desses subproblemas. A função $f(n)$ representa o custo no tempo de cada chamada recursiva do algoritmo analisado.
O teorema é apresentado a seguir
Teorema Mestre (CORMEN, 2012): sejam $a\geq 1$ e $b>1$ constantes, seja $f(n)$ uma função assintoticamente positiva e seja $T(n)$ definida no domínio dos números inteiros não negativos pela recorrência
$$T(n)=aT(n/b)+f(n)$$
onde interpretamos que $n/b$ significa $\lfloor n/b\rfloor$ ou $\lceil n/b\rceil$. Então, $T(n)$ tem os seguintes limites assintóticos:
- 1. Se $f(n)=O\left(n^{\log_b a - \epsilon}\right)$ para alguma constante $\epsilon>0$, então $T(n)=\Theta\left(n^{\log_b a}\right)$.
- 2. Se $f(n)=\Theta\left(n^{\log_b a}\right)$, então $T(n)=\Theta\left(n^{\log_b a}\lg n\right)$.
- 3. Se $f(n)=\Omega\left(n^{\log_b a + \epsilon}\right)$ para alguma constante $\epsilon>0$, e se $af(n/b)\leq cf(n)$ para alguma constante $c<1$ e todos os $n$ suficientemente grandes, então $T(n)=\Theta(f(n))$.
Análise do Teorema e Algumas Explicações
A primeira coisa a ser feita para aplicar o teorema mestre é identificar as constantes $a$ e $b$ e a função $f(n)$.
Certo cuidado deve ser tomado na hora de identificar a constante $b$. Observe que ela é o divisor na divisão $n/b$. Quando temos $T(2n/3)$, por exemplo, o valor de $b$ é igual a $3/2$, pois $\cfrac{2n}{3}=\cfrac{n}{3/2}$.
Também devemos nos atentar ao valor das constantes. O valor de $a$ deve ser maior ou igual a 1, afinal o algoritmo deve gerar pelo menos um subproblema (quando não é caso base, obviamente). Já a constante $b$ deve ser maior do que 1, senão ao invés de estarmos dividindo o problema, estaríamos gerando subproblemas maiores que o problema original.
Em todos os três casos, devemos calcular o valor de $\log_b a$ e comparar as funções $f(n)$ e $n^{\log_b a}$.
O valor de $\epsilon$ nos casos 1 e 3 pode ser qualquer valor real maior do que zero que satisfaça a notação assintótica do caso analisado. Se tal valor não existir, então devemos tentar outro caso.
Se você preferir, o logaritmo binário no caso 2 ($\lg n=\log_2 n$) pode ser substituído por $\log n$. Não faz diferença em termos de notação assintótica.
Exemplos e Exercícios Resolvidos
Acredito que a melhor forma de aprender o teorema mestre é através de exercícios e exemplos, pois não é tão simples memorizá-lo, mesmo que sejam apenas três casos.
As recorrências a seguir foram retiradas do livro Algoritmos: teoria e prática, listado na seção de referências no final da postagem.
Exemplo 1
Seja a recorrência
$$T(n)=9T(n/3)+n$$
Vamos identificar as constantes $a$, $b$ e a função $f(n)$:
$$a=9,\quad b=3,\quad f(n)=n$$
As duas constantes e a função satisfazem as condições do teorema. Isto é, $a=9\geq 1$, $b=3>1$ e $f(n)=n$ é uma função assintoticamente positiva, pois a função é positiva quando $n$ tende ao infinito.
Agora vamos calcular o valor de $\log_b a$:
$$\log_b a=\log_3 9=2$$
Para o primeiro caso, temos que verificar se $f(n)=n$ é $O(n^{\log_b a-\epsilon})=O(n^{2-\epsilon})$, para alguma constante $\epsilon>0$. Se escolhermos $\epsilon=1$, então $O(n^{2-\epsilon})=O(n)$, portanto $f(n)=n$ é $O(n)$. Logo, como a recorrência satisfaz o primeiro caso do teorema mestre, então $T(n)=\Theta(n^{\log_b a})=\Theta(n^2)$.
Uma vez que o primeiro caso foi satisfeito, então não precisamos analisar os demais casos.
Exemplo 2
$$T(n)=T(2n/3)+1$$
Para essa recorrência, temos
$$a=1\geq 1,\quad b=\frac{3}{2}>1,\quad f(n)=1$$
Para entender melhor como esses valores foram obtidos, podemos reescrever a recorrência da seguinte forma
$$T(n)=1\times T\left(\frac{n}{3/2}\right)+1$$
Agora vamos calcular o valor de $\log_b a$:
$$\log_b a=\log_{3/2} 1=0$$
Para o primeiro caso, teríamos $O(n^{\log_b a-\epsilon})=O(n^{-\epsilon})$, porém não é possível encontrar uma constante $\epsilon>0$ de forma que $f(n)$ seja $O(n^{-\epsilon})$. Isso só seria possível se $\epsilon$ fosse negativo ou zero.
No segundo caso, temos $\Theta(n^{\log_b a})=\Theta(n^0)=\Theta(1)$. Como $f(n)=1$ é $\Theta(1)$, então o segundo caso é satisfeito. Portanto, $T(n)=\Theta(n^{\log_b a}\lg n)=\Theta(n^0\lg n)=\Theta(\lg n)$ ou, equivalentemente, $T(n)=\Theta(\log n)$.
Exemplo 3
$$T(n)=3T(n/4)+n\log_2 n$$
Temos que
$$a=3,\quad b=4, \quad f(n)=n\log_2 n$$
Primeiramente, calculamos $\log_b a$:
$$\log_b a=\log_4 3=0,7924812504\ldots$$
O primeiro e o segundo caso não são satisfeitos. Não irei dar explicações detalhadas para não estender a postagem.
Analisando o terceiro caso, podemos escolher $\epsilon=0,2075187496\ldots$ (eu fiz essa escolha para que a soma $\log_b a+\epsilon$ seja igual a 1, pois fica mais fácil de fazer as contas). Dessa forma,
$$\Omega(n^{\log_b a+\epsilon})=\Omega(n^{0,7924812504\ldots+0,2075187496\ldots})=\Omega(n)$$
e $f(n)=n\log_2 n=\Omega(n)$, pois $f(n)$ é assintoticamente maior.
Entretanto, ainda precisamos verificar se a condição de regularidade $af(n/b)\leq cf(n)$ também é satisfeita:
$$\begin{align*}af(n/b)\leq cf(n)\\3\times\frac{n}{4}\log_2 {\frac{n}{4}}\leq cn\log_2 n\\\frac{3}{4}n\left(\log_2 n - \log_2 4\right)\leq cn\log_2 n\\\frac{3}{4}n\left(\log_2 n - 2\right)\leq cn\log_2 n\\\frac{3}{4}n\log_2 n - 2\times\frac{3}{4}n\leq cn\log_2 n\\\frac{3}{4}n\log_2 n - \frac{3}{2}n\leq cn\log_2 n\end{align*}$$
Se escolhermos $c=3/4 < 1$, então
$$\begin{align*}\frac{3}{4}n\log_2 n - \frac{3}{2}n\leq \frac{3}{4}n\log_2 n\\-\frac{3}{2}n\leq 0\\\frac{3}{2}n\geq 0\\n\geq 0\end{align*}$$
Ou seja, a condição é satisfeita para $c=3/4$ e qualquer $n$ maior do que zero. Concluímos que $T(n)$ se enquadra no terceiro caso do teorema mestre, portanto $T(n)=\Theta(f(n))=\Theta(n\log_2 n)$.
Observação: em geral, o valor de $c$ não é único.
Exemplo 4
A relação de recorrência a seguir é um contraexemplo no qual o teorema mestre não é aplicável, isto é, nenhum dos três casos é satisfeito (CORMEN, 2012)
$$T(n)=2T(n/2)+n\log_2 n$$
Primeiramente, identificamos $a$, $b$ e $f(n)$:
$$a=2,\quad b=2,\quad f(n)=n\log_2 n$$
Agora, calculamos o valor $\log_b a$
$$\log_b a = \log_2 2 = 1$$
Consequentemente, temos que $n^{\log_b a} = n$. É fácil de ver que os casos 1 e 2 não são satisfeitos. Vamos analisar o caso 3, isto é, tentaremos mostrar que $f(n)=n\log_2 n=\Omega(n^{1+\epsilon})$. Para tentar realizar essa demonstração, utilizarei a definição da notação Ômega Ω do livro do Cormen:
$$\begin{align*}0\leq cn^{1+\epsilon}\leq f(n)\\0\leq cnn^{\epsilon}\leq n\log_2 n\end{align*}$$
Como $n$ é positivo, então podemos dividir a desigualdade por $nn^{\epsilon}$ sem que o sentido da desigualdade se altere
$$0\leq c\leq \frac{\log_2 n}{n^{\epsilon}}$$
Como $\epsilon>0$, então o termo $\cfrac{\log_2 n}{n^{\epsilon}}$ é decrescente, pois a função $n^{\epsilon}$ é assintoticamente maior que a função $\log_2 n$. Mesmo se escolhermos um $\epsilon$ muito próximo de zero, a função $n^{\epsilon}$ será maior do que $\log_2 n$ a partir de algum valor de $n$. Em síntese,
$$\lim_{n\rightarrow \infty}\frac{\log_2 n}{n^{\epsilon}} = 0,\quad \forall\epsilon>0$$
Uma das consequências disso é que é impossível encontrar uma constante positiva $c$, tal que
$$c\leq \frac{\log_2 n}{n^{\epsilon}}$$
Portanto, terceiro caso não é satisfeito. Assim, o teorema mestre não se aplica à relação de recorrência $T(n)$.
De acordo com Cormen (2012), isso ocorre porque a função $f(n)=n\log_2 n$ não é polinomialmente maior que $n^{1+\epsilon}$.
Observações Gerais
Caso Base
As recorrências desta postagem foram apresentadas sem um caso base. Isso não significa que ele não existe. A razão para isso é que o caso base não é utilizado nos cálculos.
Algo similar ocorre quando utilizamos o método de Akra-Bazzi para resolver recorrências.
f(n) é uma Notação Assintótica
Frequentemente, a função $f(n)$ é dada em termos de alguma notação assintótica. Por exemplo,
$$T_1(n)=2T(n/2)+\Theta(n)$$
$$T_2(n)=T(n/5)+O(\log n)$$
Nesse caso, podemos assumir que $f(n)$ é a função indicada na notação. Para $T_1(n)$, teríamos $f(n)=n$ e, para $T_2(n)$, teríamos $f(n)=\log n$.
Limitações do Teorema
Como vimos no exemplo 4, existem recorrências que o teorema mestre não é capaz de resolver. Para essas recorrências, devemos empregar outro método.
Essa limitação ocorre por causa de lacunas existentes entre os casos 1 e 2 e entre os casos 2 e 3, que estão relacionadas ao fato de a função $f(n)$ não ser polinomialmente menor ou maior do que $n^{\log_b a}$, respectivamente (CORMEN, 2012).
Além disso, se cairmos no caso 3, ainda temos que verificar a condição de regularidade, que pode não ser satisfeita.
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