Teorema mestre não aplicável?

Dada a seguinte equação recursiva

$$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ queremos aplicar o teorema do mestre e observe que

$$n^{\log_2(2)} = n.$$

Agora, verificamos os dois primeiros casos para , ou seja, se$\varepsilon > 0$

• $n\log n \in O(n^{1-\varepsilon})$ ou
• $n\log n \in \Theta(n)$ .

Os dois casos não estão satisfeitos. Então, temos que verificar o terceiro caso, ou seja, se

• $n\log n \in \Omega(n^{1+\varepsilon})$ .

Eu acho que a terceira condição também não está satisfeita. Mas por que? E qual seria uma boa explicação para o motivo de o teorema do mestre não poder ser aplicado neste caso?

Os três casos do Teorema Mestre a que você se refere são provados na Introdução aos Algoritmos por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein (2ª Edição, 2001).

Observa-se corretamente que a recorrência em questão se enquadra entre o caso 2 e o caso 3. Ou seja,$f(n) = n \log n$ cresce mais rápido que mas mais lento que n 1 + ε para qualquer ε > 0 .$n$$n^{1+\varepsilon}$$\varepsilon > 0$

No entanto, o teorema pode ser generalizado para cobrir essa recorrência. Considerar

Caso 2A: Considere para alguns k ≥ 0 .$f(n) = \Theta (n^{\log_b a }\log_b^k n)$$k\geq 0$

Este caso se reduz ao caso 2 quando . É intuitivamente claro que ao longo de cada ramificação da árvore de recorrência, f ( x ) é adicionado Θ ( log b n ) vezes. Um esboço de uma prova mais formal pode ser encontrado abaixo. O resultado final é que$k = 0$$f(x)$$\Theta (\log_b n)$

.

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$

Na introdução aos algoritmos, essa declaração é deixada como um exercício.

Aplicando esta afirmação à recorrência em questão, finalmente obtemos

$$T(n) = \Theta(n \cdot \log^2 n).$$

Mais detalhes sobre o Teorema Mestre podem ser encontrados na excelente página da Wikipedia (imho) .

Como @sdcvvc aponta nos comentários para provar que o Caso 3 não se aplica aqui, pode-se invocar a regra de L'Hospital que diz que para quaisquer funções def(x)eg(x)diferenciável nas imediações doc. Aplicando este paraf(n)=nlogneg(n)=N1+εpode-se mostrar queo logn∉q(n1+ε)

$$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$$ $f(x)$$g(x)$$c$$f(n) = n \log n$$g(n) = n^{1+\varepsilon}$$\log n \not\in \Theta (n^{1+\varepsilon}).$

---

Esboço da Prova do Teorema Mestre para o Caso 2A.

Esta é uma reprodução de partes da prova da Introdução aos algoritmos com as modificações necessárias .

Primeiro, provamos o seguinte lema.

Lema A:

Considere uma função onde h ( n ) = n log b a log k b n . Então g ( n ) = n log b a log k + 1 b n

$$g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$$ $h(n) = n^{\log_b a} \log_b^k n.$$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Prova: Substituindo na expressão por g ( n ), pode-se obter g ( n ) = n log b a log k b$h(n)$$g(n)$

$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

$n$$b$

$$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$$ $$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j T(n/b^j).$$ $f(n)$$\Theta(n^{\log_b a} \log_b^k n)$$\Theta$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

$n$$b$

O teorema de Akra-Bazzi é uma generalização estrita do teorema do mestre. Como bônus, sua prova é uma nevasca de integrais que farão sua cabeça girar ;-)

$T(n) \sim g(n)$