微软一道关于时间复杂度的有关问题
微软一道关于时间复杂度的问题
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)
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)