T(n)= T(n-1)+ 1/n的渐近复杂度 [英] Asymptotic complexity of T(n)=T(n-1)+1/n

问题描述

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

There is an algorithm which has the time complexity

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

我正在解决其渐近复杂性，并将阶数设为'n'，但给出的答案是'log n'.这是正确的吗?如果是log n，为什么?

I am solving for its asymptotic complexity, and getting order as 'n' but the answer given is 'log n'. Is it correct? If it is log n, then why?

推荐答案

对于从1到n的k值，T(n)是1/k的和很容易看出(或用归纳法正式证明). .这是第 n 个谐音，H _n = 1 + 1/2 + 1/3 + ... + 1/n.

It can be easily seen (or proven formally with induction) that T(n) is the sum of 1/k for the values of k from 1 to n. This is the nth harmonic number, 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)).

Asymptotically, the harmonic numbers grow on the order of log(n). This is because the sum is close in value to the integral of 1/x from 1 to n, which is equal to the natural logarithm of n. In fact, H_n = ln(n) + γ + O(1/n) where γ is a constant. From this, it is easy to show that T(n) = Θ(log(n)).

这篇关于T(n)= T(n-1)+ 1/n的渐近复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！