对于关系
T(n) = T(n-1) + T(n/2) + n
我可以先解出项 (T(n-1) + n) ，它给出 O(n^2) ，然后解出项 T(n/2) + O(n^2) 吗？
根据主定理，它也给出了 O(n ^ 2) 或者它是错误的？
不，你不能用主定理来解决它。
你需要使用来解决它阿克拉-巴齐法 http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method，对著名的主定理的更清晰的概括。
主定理假设子问题具有相同的大小。
主定理涉及以下形式的递推关系
T(n) = a T(n/b) + f(n) ，其中 a>=1，b>1。
我不会在这里导出解决方案的步骤，以便您解决它。如果您在解决相同问题时遇到其他问题，请在下面评论。祝你好运...
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
