我正在寻找一个上界和下界（或者只是一个 Θ 界限）。
T(n) = T(n-1) + 1/lg(n)
我正在备考一场考试，这是我遇到的一道练习题。
1个回答
1
我猜以下展开式会给你适当的提示：
T(n) =
= 1/lg(n) + T(n-1)
= 1/lg(n) + 1/lg(n-1) + T(n-2)
= 1/lg(n) + 1/lg(n-1) + 1/lg(n-2) + T(n-3)
= ···
= 1/lg(n) + ··· + 1/lg(n/2) + T(n/2)
= Theta(n/lg(n)) + T(n/2)
现在，对这个新的递归式使用主定理。
T(n) =
= 1/lg(n) + T(n-1)
= 1/lg(n) + 1/lg(n-1) + T(n-2)
= 1/lg(n) + 1/lg(n-1) + 1/lg(n-2) + T(n-3)
= ···
= 1/lg(n) + ··· + 1/lg(n/2) + T(n/2)
= Theta(n/lg(n)) + T(n/2)
现在，对这个新的递归式使用主定理。
- anumi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 T(n) = (T(n-1) + n!) 的时间复杂度是什么？
- 5 解决递归关系： T(n)=T(n-1)+T(n/2)+n
- 8 递归式为T(n) = T(n^(1/2)) + 1。
- 15 计算递归关系 T(n)=T(n/log n) + Θ(1)。
- 5 解决递归：T(n) = T(n^(1/2)) + Θ(lg lg n)
- 4 计算递归关系式 T(n)=T(n-1)+logn
- 11 递归的复杂度：T(n) = T(n-1) + T(n-2) + C。
- 11 如何解决：T(n) = T(n-1) + n
- 4 如何解决这个递归式 T(n) = T(n − 1) + lg(1 + 1/n)，其中 T(1) = 1？
- 5 解决：T(n) = T(n-1) + n