resolver recorrências

Question

Am tentando resolver o recursão dada, usando árvore de recursão, T(n) = 3T(n/3) + n/lg n.

No primeiro (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)) nível.

No segundo nível, acaba por ser n/(log(n/9)).

Posso generalizar a equação acima na forma de n.loglogn

Esta é uma dúvida geral que eu tenho, eu preciso de uma visão sobre isso.

Nota: Qualquer função que tem de ser Theta(n^k log^k (n)) nessa função k deve> = 1. E, neste caso k é -1 modo mestre teorema não vir a imagem

Answer 1

É verdade, o Mestre teorema não se aplica.

T (n) = 3T (n / 3) + n / log n.

Seja g (n) = T (n) / n.

Em seguida, n g (n) = 3 (n / 3) * g (n / 3) + n / log n.

Assim

g (n) = g (n / 3) + 1 / log n.

Isto dá g (n) = Soma 1 / log n + 1 / log n / 3 + 1 / log n / 9 + ...

= Teta (Soma 1 / log n + 1 / (log n-1) + 1 / (log n - 2) + ...) = Teta (Integral 1 / x entre 1 e log n) = Teta (log n log ).

Assim T (n) = N g (n) = teta (n log log n.)

Você adivinhou certo.

Answer 2

Se você usar uma árvore para visualizar a pergunta, você verá que a soma de cada classificação é a seguinte:

• Ranking 0:

(que é igual a n / log (n)) - rank 1:

e assim por diante, com uma soma geral de n/log(n/(3^i)) para cada categoria, i sendo a classificação atual. assim, todos juntos temos:

se abrirmos a equação temos:

(a partir do final e a andar para trás .. primeiro quando i = log (base3) n e, em seguida, de volta indo)

desde log base não importa em theta, temos:

que é:

que é (em sigma):

que é uma série harmônica, igual a:

e desde ln é log com uma base de e, e bases de log não importa em theta, nós finalmente obter:

que é igual a:

Assim, é teta (n n log log).