T(n)=T(n-1)+1/n 的渐近复杂度

Question

有一个算法的时间复杂度为

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

我正在解决它的渐近复杂度，得到的是'n'阶，但给出的答案是'log n'。这样做正确吗？如果是'log n'，那为什么呢？

- sandepp

---

请展示如何实现O(n)时间复杂度。 - Femaref

http://en.wikipedia.org/wiki/Harmonic_number - interjay

@interjay 你也应该将其作为答案提交。 - jamylak

@jamylak：完成了，之前没时间做。 - interjay

@IvayloStrandjev：好的，我认为现在应该更清晰了。 - interjay

Answer 1

很容易看出（或者通过归纳证明）T(n)是从1到n的k值的1/k之和。这就是第n个调和数，H_n= 1 + 1/2 + 1/3 + ... + 1/n。

渐近地，调和数的增长率为log(n)。这是因为该总和接近于从1到n的1/x的积分，其等于n的自然对数。事实上，H_n = ln(n) + γ + O(1/n)，其中γ是一个常数。由此，很容易证明T(n)=Θ(log(n))。

- interjay

Answer 2

更多细节请参考：

对于 H(N) = 1 + 1/2 + 1/3 + ... + 1/N，

函数 x :-> 1/x 是一个递减函数，因此：

我们从左侧部分求和 1 到 N，对于右侧部分，我们从2到N 求和并加上1，我们得到：

然后我们计算左边和右边的部分：ln(N+1) <= H(N) <= 1 + ln(N) 这意味着 H(N)/ln(N) -> 1 因此 H(N)=Θ(log(N)) （来源：http://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique#.C3.89quivalent_de_Hn）

- Tony Morris