asintotica complessità della T (n) = T (n-1) + 1/n

Question

C'è un algoritmo che ha la complessità temporale

T(n)=T(n-1)+1/n if n>1 
     =1   otherwise 

sto risolvendo per la sua complessità asintotica, e l'ordine ottenendo come ' n 'ma la risposta data è' log n '. È corretto? Se è log n, allora perché?

Answer 1

Può essere facilmente visto (o dimostrato formalmente con induzione) che T (n) è la somma di 1/k per i valori di k da 1 a n. Questo è il n th harmonic number, H _n = 1 + 1/2 + 1/3 + ... + 1/n.

In modo asintotico, i numeri armonici crescono nell'ordine di log (n). Questo perché la somma è vicina in valore all'integrale di 1/x da 1 a n, che è uguale al logaritmo naturale di n. Infatti, H _n = ln (n) + γ + O (1/n) dove γ è una costante. Da questo, è facile mostrare che T (n) = Θ (log (n)).

Answer 2

Per maggiori dettagli:

Con H(N) = 1 + 1/2 + 1/3 + ... + 1/N

la funzione x :-> 1/x è una funzione decrescente così:

Sommiamo dal 1 to N parte sinistra e per la parte destra sommiamo da 2 to N e aggiungiamo 1, otteniamo:

Poi si calcola la parti sinistra e destra: ln(N+1) <= H(N) <= 1 + ln(N)

questo implica H(N)/ln(N) -> 1 quindi H(N)=Θ(log(N))

(da http://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique#.C3.89quivalent_de_Hn)