Resolvendo relação de recorrência

8

Quero provar que a complexidade do tempo de um algoritmo é polilogarítmica na escala de entrada.

A relação de recorrência desse algoritmo é T(2n)T(n)+T(na), Onde a(0,1).

Parece que T(n)logβn para alguns β depende de a. Mas não posso provar essa desigualdade. Como resolver essa relação de recorrência?

Eu só quero obter um polilogarítmico superior em n.

Qiang Li
fonte
1
a<1, Eu assumo? Além disso, você verificou nossa pergunta de referência ? Eu não acho que o caso específico sobre o qual você está perguntando seja explicitamente abordado, mas há muitas técnicas descritas.
David Richerby
1
Não existe um teorema "mestre" para esse tipo que eu conheça; Cf. esta questão minha e esta . (cc @DavidRicherby)
Raphael

Respostas:

4

Seu palpite está errado. De fato, não é difícil mostrar que, assumindoT(n)>0 para todos n>0, então T(n)=Ω(logkn)para todos k. De fato, para que isso ocorra, precisamos disso por tempo suficienten Nós teríamos

(1+ak)logkn=logkn+logknalogk(2n),
ou 1+akklognlogn+log2, que dura enquanto [1+akk1]lognlog2e, em particular, para grandes o suficiente n.

Qual é a ordem correta de crescimento de T(n)? Para tentar descobrir, escrevaS(n)=T(2n). A recorrência agora se torna

S(n+1)=S(n)+S(an).
Para grandes nesperaríamos S(n+1)S(n) estar muito perto de S(n)e, heuristicamente, esperaríamos que S satisfazer S(n)=S(an). Essa equação parece um pouco difícil de resolver, mas uma solução aproximada éS(n)=nΘ(logn). Substituindo, deduzimos que a ordem de crescimento deT(n) deve ser algo como (logn)Θ(loglogn).
Yuval Filmus
fonte
Parece que logk(2n)=(log2+logn)k. O limite inferior não se mantém.
Qiang Li
@ QiangLi Obrigado por detectar o erro. O limite inferior é válido, no entanto, uma vez que o argumento é modificado adequadamente.
Yuval Filmus