Teorema mestre não aplicável?

11

Dada a seguinte equação recursiva

T(n)=2T(n2)+nlogn
queremos aplicar o teorema do mestre e observe que

nlog2(2)=n.

Agora, verificamos os dois primeiros casos para , ou seja, seε>0

  • nlognO(n1ε) ou
  • nlognΘ(n) .

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

  • nlognΩ(n1+ε) .

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?

Joachim
fonte
4
O caso três não está satisfeito porque não é para qualquer . Use a regra de l'Hôpital no limitelognΩ(nϵ)ϵ>0lognnϵ
sdcvvc
1
Depois de mostrar que nenhum dos casos se aplica, isso prova que você não pode aplicar o teorema mestre conforme indicado.
Raphael
Quem precisa do teorema mestre? Use árvores de recursão.
Jeffe

Respostas:

7

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)=nlogn cresce mais rápido que mas mais lento que n 1 + ε para qualquer ε > 0 .nn1+εε>0

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

Caso 2A: Considere para alguns k 0 .f(n)=Θ(nlogbalogbkn)k0

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 é quek=0f(x)Θ(logbn)

.

T(n)=Θ(nlogbalogbk+1n)

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)=Θ(nlog2n).

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 lognq(n1+ε).

limxcf(x)g(x)=limxcf(x)g(x)
f(x)g(x)cf(n)=nlogng(n)=n1+εlognΘ(n1+ε).

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)=j=0logbn1ajh(n/bj)
h(n)=nlogbalogbkn.g(n)=nlogbalogbk+1n.

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

g(n)=nlogbalogbknj=0logbn1(ablogba)j=nlogbalogbk+1n.

QED

nb

T(n)=aT(n/b)+f(n),T(1)=Θ(1)
T(n)=Θ(nlogba)+j=0logbn1ajT(n/bj).
f(n)Θ(nlogbalogbkn)Θ

T(n)=Θ(nlogbalogbk+1n).

nb

Dmitri Chubarov
fonte
1

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)g(n)

vonbrand
fonte