T（n）= T（n-1）+ 1 / n的渐近复杂度

有一种算法具有时间复杂性

    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））。