如何解决这种复发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))