问主方法仅适用于分治算法。
EN

Stack Overflow用户

提问于 2016-10-24 10:11:35

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

主方法只适用于大小相等的分治算法？不是所有递归算法吗？

回答已采纳

发布于 2016-10-24 10:31:05

主定理并不适用于所有递归问题，这是正确的。在它的各种证明中，你可以看到主定理是通过计算大小相等的子问题的代价来进行的，每个子问题的代价都是相同的。

所以，除非你能把一个给定的问题分解成这样大小相同的子问题，否则主定理就不足以帮助你找到它的解决方案。例如，与T(n)依赖于T(N)的递推关系，例如k是任何一个特殊的整数，都不能用主定理真正解决。然而，在其证据中使用的方法仍然是有用的。(即扩展子问题，直到关系完全依赖于基本情况)

票数 1

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

原文链接：

https://stackoverflow.com/questions/40215796

复制

相似问题

问主方法仅适用于分治算法。EN