Question

该算法的时间复杂度为多少？T(N)=2T(N/2)+N

Answer 1

如果没有给出T(0)的值的话，这个算法是没有尽头的……
虽然我们可以手算出T(0)
=
0，但是计算机没这个本事，它只会一遍遍的求zhidaoT(0)
=
2
*
T(0)
+
0
直到堆栈溢出。
在加上T(0)
=
0这个结束递归的条件之后，这个算法的时间复杂度是O(logN)