问题描述
有关系
T（N）= T（N-1）+ T（N / 2）+ N
我可以先解决这个词（T（N-1）+ N），这也是为O（n ^ 2），进而解决项T（N / 2）+ O（N ^ 2）？
can I first solve the term (T(n-1) + n) which gives O(n^2), then solve the term T(n/2) + O(n^2) ?
根据主定理，也给为O（n ^ 2），或者是错误的？
according to the master theorem which also gives O(n ^ 2) or it is wrong?
推荐答案
我不认为你的做法是在一般情况下是正确的。当你扔掉T（N / 2）项计算的T（N-1）项，你最终会低估了T（N-1）项的大小的复杂性。
I don't think your approach is correct in the general case. When you throw away the T(n/2) term to calculate the complexity of the T(n-1) term you end up underestimating the size of the T(n-1) term.
有关具体的反例：
T(n) = T(n-1) + T(n-2) + 1
您的技术也将拿出T（N）=为O（n ^ 2）这一点，但真正的复杂性是指数的。
Your technique is also going to come up with T(n) = O(n^2) for this but the real complexity is exponential.
这篇关于时间的关系T（n）的复杂性= T（N-1）+ T（N / 2）+ N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！