Teorema Mestre e Exemplos Resolvidos

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
  • Análise do Teorema e Algumas Explicações
• Exemplos e Exercícios Resolvidos
  • Exemplo 1
  • Exemplo 2
  • Exemplo 3
  • Exemplo 4
• Observações Gerais
  • Caso Base
  • f(n) é uma Notação Assintótica
  • Limitações do Teorema
• Leia também
• Referências

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.

Ir para o índice

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.

Ir para o índice

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)$.

Ir para o índice

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.

Ir para o índice

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}$.

Ir para o índice

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.

Ir para o índice

Leia também

Aproveite e leia também os seguintes artigos

• Exercícios Resolvidos sobre o Teorema Mestre
• Teorema mestre com condições relaxadas
• Complexidade de Algoritmos - Um Texto Introdutório

Ir para o índice

Referências

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