对于关系
T(n) = T(n-1) + T(n/2) + n
我可以先求解给出 O(n^2) 的项 (T(n-1) + n)，然后求解项 T(n/2) + O(n^2) 吗？
根据也给出 O(n ^ 2) 的主定理还是错误的？
问问题
1331 次
2 回答
2
我认为您的方法在一般情况下是不正确的。当你丢弃 T(n/2) 项来计算 T(n-1) 项的复杂度时，你最终会低估 T(n-1) 项的大小。
举一个具体的反例：
T(n) = T(n-1) + T(n-2) + 1
您的技术也将为此提出 T(n) = O(n^2) 但真正的复杂性是指数级的。
于 2015-05-22T17:17:12.363 回答
2
不，您无法使用 Mater-theorem 解决它。
您需要使用Akra-Bazzi 方法来解决它，这是著名的主定理的更清晰的概括。
主定理假设子问题具有相同的大小。
主定理涉及形式的递推关系
T(n) = a T(n/b) + f(n) ，其中 a>=1，b>1。
我不是在这里推导出解决方案的步骤，以便您解决问题。如果您在解决相同问题时还有其他问题，请在下面发表评论。祝你好运...
于 2015-05-22T17:18:35.733 回答