如何解决该递归T（n）= T（n − 1）+ lg（1 + 1 / n），T（1）= 1？ [英] How to solve for this recurrence T(n) = T(n − 1) + lg(1 + 1/n), T(1) = 1?
本文介绍了如何解决该递归T（n）= T（n − 1）+ lg（1 + 1 / n），T（1）= 1？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我陷入了这种重复发生：
I got stuck in this recurrence:
T(n) = T(n − 1) + lg(1 + 1/n), T(1) = 1?
一段时间，似乎主方法无法应用于此方法。
for a while and it seems the master method cannot be applied on this one.
推荐答案
我们有：
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）
添加和消除，我们得到：
Adding and eliminating, we get:
T（n）-T（1）= lg（n + 1）-lg（1）= lg（n + 1）
或 T（n）= 1 + lg（n + 1）
因此 T（n）= O（lg（n））
这篇关于如何解决该递归T（n）= T（n − 1）+ lg（1 + 1 / n），T（1）= 1？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
