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,那么为什么呢？

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)).