寻找调和级数的时间复杂度（Big O）。

Question

证明

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

我将这个级数代入求和式中，但不知道如何解决这个问题。欢迎任何帮助。

- user2092408

Answer 1

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

然后我们有以下不等式：

在这里我们可以得出结论，S = 1 + 1/2 + ... + 1/n 同时是 Ω(log(n)) 和 O(log(n))，因此它是Ɵ(log(n))，这个边界实际上是紧密的。

- chiwangc

---

谢谢！我的教授说我们不应该在这个问题中使用微积分。有什么离散数学的解决方法吗？ - user2092408

为了证明O(log(n))的上限，你只需要证明最左边的不等式成立（即1/2 + 1/3 + ... + 1/(n+1) <= ln(n)），你可以使用数学归纳法来证明。提示：使用泰勒展开或其他方法证明1/(n+1) <= log(n+1) - log(n) = log(1+1/n)。 - chiwangc

只需输入任何小的输入并显示其证明。 - Ankit Mishra

Answer 2

这是一个使用离散数学的公式：

因此，H(n) = O(log n)

- Sushovan Mandal

Answer 3

如果问题改为：

1 + 1/2 + 1/4 + ... + 1/n

系列现在可以写成：

1/2^0 + 1/2^1 + 1/2^2 + ... + 1/2^(k)

循环将运行多少次？从0到k = k + 1次。从两个系列中，我们可以看到2^k = n。因此k = log (n)。所以，它运行的次数= log(n) + 1 = O(log n)。

- Sahim Salem