认识O(NlogN) 递归

知识点

求中点

   正常想法为mid=(L+R)/2 ，但在特殊情况下可能会溢出导致结果的不准确如两个值都很大的时候 L+R会溢出，此时可以把L提取出来变成mid = L + (R-L)/2 。 > 在程序里可以写成 mid = L + （(R-L) >> 1); 算术左移一位等同于除以2 比使用/性能更好。 ## 递归行为时间复杂度计算(master公式) T(N)=a*T(N/b)+O(N^d) 母   次 子

公式时间复杂度
logb(a) < dO(N^d)
logb(a) > dO(N^logb(a))
logb(a) == dO(N^d*logN)