有一种算法具有时间复杂性
T(n)=T(n-1)+1/n if n>1 =1 otherwise
我正在解决其渐近复杂性，并将阶数设为“ n”，但给出的答案是“ log n”。这是正确的吗？如果是log n，那为什么呢？
可以很容易地看到（或用归纳法正式证明），对于从1到n的k值，T（n）是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））。
