<分区>
有一个时间复杂度的算法
T(n)=T(n-1)+1/n if n>1
=1 otherwise
我正在解决它的渐近复杂性，并得到“n”的顺序，但给出的答案是“log n”。这是对的吗？如果是 log n，那为什么？
<分区>
有一个时间复杂度的算法
T(n)=T(n-1)+1/n if n>1
=1 otherwise
我正在解决它的渐近复杂性，并得到“n”的顺序，但给出的答案是“log n”。这是对的吗？如果是 log n，那为什么？
最佳答案
很容易看出(或通过归纳法形式化证明)T(n) 是 k 的值从 1 到 n 的 1/k 之和。这是第n个harmonic number , Hn = 1 + 1/2 + 1/3 + ... + 1/n.
渐近地，谐波数按 log(n) 的顺序增长。这是因为和值接近于 1/x 从 1 到 n 的积分，等于 n 的自然对数。事实上，Hn = ln(n) + γ + O(1/n) 其中 γ 是常数。由此易证T(n) = Θ(log(n))。
关于algorithm - T(n)=T(n-1)+1/n 的渐近复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15656021/