文章/答案/技术大牛

发布

社区首页 >问答首页 >T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)的时间复杂度是多少？。。。T(n-(n-1))？

问T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)的时间复杂度是多少？。。。T(n-(n-1))？
EN

Stack Overflow用户

提问于 2021-07-01 10:41:37

回答 1查看 495关注 0票数 1

我有一个递归算法。不使用memoization，这就是我的递归关系。如何计算时间复杂度？

发布于 2021-07-01 18:21:06

你有T(n) = sum(T(i) i=1..n-1)

则对于n>1，T(n+1) - T(n) = sum(T(i) i=1..n) - sum(T(i) i=1..n-1) = T(n)

所以对于n>2，T(n) = 2T(n-1)。因此，对于n>2，T(n)是2^n的某个倍数。简单的计算表明，倍数是T(1)/4 (这也适用于n=2)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/68203633

复制

相似问题

问T(n)=T(n-1)+T(n-2)+T(n-3)+T(n-4)的时间复杂度是多少？。。。T(n-(n-1))？EN