san*_*epp 8 algorithm math recursion
存在具有时间复杂度的算法
T(n)=T(n-1)+1/n if n>1 =1 otherwise
我正在解决它的渐近复杂性,并将命令作为'n',但给出的答案是'log n'.这是对的吗？如果是log n,那么为什么呢？
int*_*jay 9
可以很容易地看出(或者通过感应正式证明)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)).
归档时间：
12 年，9 月 前
查看次数：
8756 次
最近记录：