1）+ T（n / 2）+ n
为关系
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）的主定理或者它是错误的？
不，你不能用母体定理来解决它。
你需要使用Akra-Bazzi方法来解决它，这是对着名大师定理的一个更清晰的概括。
主定理假定子问题具有相同的大小。
主定理涉及形式的重现关系
T（n）= a T（n / b）+ f（n），其中a> = 1，b> 1。
我不是在这里推导出解决方案的步骤，以便您解决它。 如果您在解决问题时还有其他问题，请在下面评论。 祝你好运...
我认为你的方法在一般情况下是不正确的。 当扔掉T（n / 2）项来计算T（n-1）项的复杂性时，最终会低估T（n-1）项的大小。
对于一个具体的反例：
T(n) = T(n-1) + T(n-2) + 1
你的技术也会为此提出T（n）= O（n ^ 2），但真正的复杂性是指数的。
链接地址: http://www.djcxy.com/p/26487.html上一篇: 1) + T(n/2) + n