如何求解这个递归 T(n) = T(n − 1) + lg(1 + 1/n), T(1) = 1？

Question

我陷入了这个重复：

T(n) = T(n − 1) + lg(1 + 1/n), T(1) = 1?

一时半会儿，大师的方法好像不能用在这个上面

Answer 1

我们有：

lg(1 + 1/n) = lg((n + 1) / n) = lg(n+1) - lg(n)

因此：

T(n) - T(n - 1) = lg(n + 1) - lg(n)

T(n-1) - T(n - 2) = lg(n) - lg(n - 1)

...

T(3) - T(2) = lg(3) - lg(2)

T(2) - T(1) = lg(2) - lg(1)

相加和消去，我们得到：

T(n) - T(1) = lg(n + 1) - lg(1) = lg(n + 1)

或T(n) = 1 + lg(n + 1)

因此T(n) = O(lg(n))

Answer 2

与这里的另一个正确答案相同，只是证明不同。

以下所有等式都是根据给定的递归创建的：

• T(n) = T(n-1) + Log((n+1)/n)
• T(n-1) = T(n-2) + Log(n/(n-1))
• .
• .
• .
• T(2) = T(1) + 对数(3/2)

将上述等式中的所有 RHS 和 LHS 相加得出：

• T(n) = T(1) + Log(3/2) + Log(4/3) + ... + Log((n+1)/n)

因为 Log(a) + Log(b) = Log(ab)，

• T(n) = 1 + 日志((n+1)/2)
• T(n) = Log(10) + Log((n+1)/2) = Log(5n + 5) 假设基数为 10 并使用 1 = Log₁₀10

因此 T(n) = O(Log(5n + 5)) = O(Log(n))

Answer 3

它并不像某些人声称的那样是线性的。是O(log(n))。下面是数学分析：

---

如果您开始展开递归，您将得到：

如果你坚持到最后你会得到

或简称：

用积分求和后，您将得到：

最后，如果你要取一个极限 x -> 无穷大：

你会看到第一部分是

这为您提供了最终解决方案 log(x + 1) 即 O(log(n))