算法时间复杂度分析：关系式 T(n) = T(n-1) + T(n/2) + n 的时间复杂度是什么？

Question

7

对于这个关系式：

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) 吗？还是说这种方法是错误的？

- adnanmuttaleb

1

如果你对复杂度有一个“猜测”，你可以尝试使用归纳法直接证明事情。如果你的猜测是错误的，这种方法可能无法帮助你找到正确的解决方案，但如果你的猜测是正确的，那么你就可以得到所需的证明，而不需要记忆任何特殊的方法。 - hugomg

2个回答

2

不，你不能使用主定理来解决它。

你需要使用Akra-Bazzi方法，这是一个更干净的知名主定理的概括。

主定理假设子问题具有相同的大小。

主定理涉及形式为 T(n) = a T(n/b) + f(n) 的递归关系，其中 a>=1，b>1。

我这里不会详细解释解决步骤，希望你自己去尝试。如果你在解决过程中遇到问题，请在下面评论区留言。祝你好运...

- Am_I_Helpful

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hugomg · Accepted Answer

我不认为你的方法在一般情况下是正确的。当你舍弃T(n/2)项来计算T(n-1)项的复杂度时，你最终低估了T(n-1)项的大小。

这里给出一个具体反例：

 T(n) = T(n-1) + T(n-2) + 1

对于这个问题，您的技术可能会得出T(n) = O(n^2)，但实际复杂度是指数级别的。