微软一道关于时间复杂度的问题
Suppose T(n) is the runtime of resolving a problem with n elements, T(n)=O(1) if n=1; T(n)=2*T(n/2)+O(n) if n>1; so T(n) is O(n*logn).
这句话是对的,但是怎么推导出来呢?谢谢!
[解决办法]
参考: T(n)= T(n/2) + O(1) 这样的次数为logn 则为O(logn)。
T(n)=2*T(n/2)+O(n) 的话,就是 T(n) = 2 ^ logn + logn * O(n) = n + O(nlogn)=O(nlogn)