T（n）的的漸近複雜= T（N-1）+ 1/N

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

我求解其漸近的複雜性，並獲得順序爲' n'但給出的答案是'log n'。這是對的嗎？如果是log n，那爲什麼？

2013-03-27 sandepp

請出示你到O（N）的方式。 – Femaref 2013-03-27 09:59:01

http://en.wikipedia.org/wiki/Harmonic_number – interjay 2013-03-27 10:12:40

謝謝@interjay我明白了...... – sandepp 2013-03-27 10:17:20

它可以很容易地看到（或者與感應正式證明），該T（n）爲1/k的對於k的從1到n的值的總和。這是Ñ第harmonic number，H _Ñ = 1 + 1/2 1/3 + + ... + 1/N。

漸近，諧波數量的不斷增長的log（n）的數量級上。這是因爲，總和值接近的1/X從1到n的積分，它是等於n的自然對數。事實上，H _Ñ = LN（N）+γ+ O（1/n），其中γ是一個常數。由此，很容易證明T（n）=Θ（log（n））。

2013-03-27 12:32:08 interjay

有關詳細信息：

隨着H(N) = 1 + 1/2 + 1/3 + ... + 1/N

功能x :-> 1/x是減函數這樣：

enter image description here

我們從1 to N左邊部分總結和正確的部分，我們總結從2 to N我們添加1，我們得到：

enter image description here

然後我們計算的左右兩部分：ln(N+1) <= H(N) <= 1 + ln(N)

這意味着H(N)/ln(N) -> 1因此H(N)=Θ(log(N))

2013-03-27 14:59:23

回答