寻找谐波系列的大O.

Question

证明

1 + 1/2 + 1/3 + ... + 1/n is O(log n). 
Assume n = 2^k

我把这个系列放到了总和中,但我不知道如何解决这个问题.任何帮助表示赞赏

Answer 1

这很容易从微积分中的一个简单事实中得出:

在此输入图像描述

我们有以下不等式:

在此输入图像描述

在这里我们可以得出结论,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认同)

Answer 2

这是使用离散数学的公式:

那么,H(n)= O(log n)