寻找谐波系列的大O.
use*_*408 35 complexity-theory big-o time-complexity
证明
1 + 1/2 + 1/3 + ... + 1/n is O(log n).
Assume n = 2^k
我把这个系列放到了总和中,但我不知道如何解决这个问题.任何帮助表示赞赏
chi*_*ngc 48
这很容易从微积分中的一个简单事实中得出:
我们有以下不等式:
在这里我们可以得出结论,S = 1 + 1/2 + ... + 1/n都是Ω(log(n))和O(log(n)),因此它是Ɵ(log(n)),绑定实际上很紧张.
- 为了你的目的(即证明`O(log(n))`上限),你只需要争论最左边的不等式(即`1/2 + 1/3 + ... + 1 /(n + 1) )<= ln(n)`),你可以通过数学归纳来证明这一点.(*提示*:认为我们有`1 /(n + 1)<= log(n + 1) - log(n)= log(1 + 1/n)`使用泰勒的扩展或其他方式) (3认同)
