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

回答