Asymptotic złożoność T (n) = T (n-1) + 1/n

Question

Jest to algorytm, który ma złożoność czasową

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

ja rozwiązywaniu jego asymptotycznej złożoności i porządku uzyskanie jak ' n ', ale udzielona odpowiedź to "log n". Czy to jest poprawne? Jeśli jest to log n, to dlaczego?

Answer 1

Można łatwo zauważyć (lub udowodnić formalnie z indukcją), że T (n) jest sumą 1/k dla wartości k od 1 do n. Jest to n th harmonic number, H , H n= 1 + 1/2 + 1/3 + ... + 1/n.

Asymptotycznie numery harmoniczne rosną w kolejności log (n). Jest tak dlatego, że suma jest bliska wartości całki 1/x od 1 do n, która jest równa logarytmowi naturalnemu n. W rzeczywistości, H _n = ln (n) + γ + O (1/n), gdzie γ jest stałą. Z tego łatwo jest pokazać, że T (n) = Θ (log (n)).

Answer 2

Aby uzyskać więcej informacji:

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

funkcja x :-> 1/x jest malejącą funkcją tak:

Mamy Podsumowując od 1 to N lewej części i dla prawej części zsumujemy od 2 to N i dodajemy 1, otrzymujemy:

Następnie obliczamy lewej i prawej części: ln(N+1) <= H(N) <= 1 + ln(N)

Oznacza to H(N)/ln(N) -> 1 stąd H(N)=Θ(log(N))

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