时间的关系T（n）的复杂性= T（N-1）+ T（N / 2）+ N [英] time complexity of relation T(n) = T(n-1) + T(n/2) + n

问题描述

有关系

T（N）= T（N-1）+ T（N / 2）+ N

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！