Risolvere le recidive

Question

sto cercando di risolvere il dato ricorsione, con albero di ricorsione, T(n) = 3T(n/3) + n/lg n.

Nel primo (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)) livello.

Nel secondo livello risulta essere n/(log(n/9)).

Posso generalizzare l'equazione di cui sopra in forma di n.loglogn

Questo è un dubbio generale ho, ho bisogno di una panoramica su questo.

Nota: Qualsiasi funzione che deve essere Theta(n^k log^k (n)) in quella funzione k voglia> = 1. E in questo caso k è -1 in modo teorema non venga a immaginare

Answer 1

E 'vero, non si applica il teorema master.

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

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

Poi n g (n) = 3 (n / 3) * g (n / 3) + n / logn.

Quindi

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

Questo dà g (n) = Somma 1 / log n + 1 / log n / 3 + 1 / log n / 9 + ...

= Theta (Somma 1 / logn + 1 / (log n -1) + 1 / (log n - 2) + ...) = Theta (Integrale 1 / x compreso tra 1 e logn) = Theta (log log n ).

Quindi T (n) = n g (n) = Theta (n logn connettervi.)

Avete indovinato giusto.

Answer 2

Se si utilizza un albero per visualizzare la domanda, vedrete che la somma di ogni posizione è:

• posizione in classifica 0:

(che è pari a n / log (n))  - rank 1:

e così via, con una somma generale di n/log(n/(3^i)) per ogni rango, i essendo la posizione corrente. così, tutti insieme otteniamo:

se apriamo l'equazione otteniamo:

(partendo dalla fine e andando a ritroso .. prima quando i = log (Base3) n e poi tornare)

dal logaritmo in base non importa in theta, otteniamo:

che è:

che è (in Sigma):

che è una serie armonica, pari a:

e dal momento ln è accedere con una base di e, e log basi non contano in theta, abbiamo finalmente ottenere:

che è pari a:

così, è theta (n log log n).