这些循环关系的运行时间
这些循环关系的运行时间
提问于 2015-05-16 22:39:34
如何计算这些关系的紧束缚运行时？
- T(n)=T(n-3)+n^2
- T(n) = 4T(n/4)+log^3(n)
对于第一种方法，我使用了给出n^2但不正确的代换方法，第二种方法是用马斯特斯定理得到nlog^4(n)，这也是不对的。彻底的解释是有帮助的。谢谢!
回答 1
Stack Overflow用户
发布于 2015-07-15 05:29:56
对于第一次递归，我们可以用递归树方法来求解。
T(n)=T(n-3)+n^2
( a)在这里，我们看到子问题的数目是n/3 (每个i从n减去3，所以在n/3步骤中，我们将到达最后一个子问题)。
( b)在每一级，费用为n^2。
因此，时间复杂度大致为(n/3)*n^2= (n^3)/3，即O(n^3)
关于第二次递推关系
T(n)=4T(n/4)+log^3(n)
在这里我们不能应用主定理，因为n和log^3(n)不是可比较的多项式次数，如果我们有像nlog^3(n)这样的东西，我们就可以应用主定理(严格对数界的推论)，因为它比对数时间更严格。
如果我错了，请纠正我
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30284101
复制相关文章
相似问题
腾讯云开发者
