在递归算法情况下计算时间复杂度？
在递归算法情况下计算时间复杂度？
提问于 2011-11-02 22:18:02
在使用递归算法的情况下如何计算时间复杂度？
例如t(n) = t(3n/2) + 0(1) (堆排序)
回答 4
Stack Overflow用户
回答已采纳
发布于 2011-11-03 00:06:03
师父的定理就是捷径。但是，既然你想学习所有递归函数的复杂性，我建议你学习递归树的工作原理，这构成了Master定理的基础。这篇link将详细解释这一点。与其盲目地使用大师的理论，不如学习它，以便在未来更好地理解它！这个link about recursion tree也是一个很好的读物
Stack Overflow用户
发布于 2011-11-02 22:32:37
使用Master Theorem。
无论如何，您的等式看起来是错误的，因为递归调用具有比调用者更高的输入值，所以您的复杂度是O(无穷大)。
请把它修好。
Stack Overflow用户
发布于 2011-11-02 22:34:05
通常你可以猜测答案并使用归纳来证明它。
但是有一个定理可以解决很多情况，比如堆排序，名为Master定理：
http://en.wikipedia.org/wiki/Master_theorem
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7981830
复制相关文章
相似问题
腾讯云开发者
