请教什么情况下的算法复杂度是N*Log(N)

请问什么情况下的算法复杂度是N*Log(N)?
我知道二分法的复杂度是 O(Log(N))

请问什么算法的复杂度是 N*Log(N)？

------解决方案--------------------
一票nlogn的排序和凸包算法。
所有能达到T(n)=cT(n/c)+O(n)的，其中c是常数。
FFT是n*logn*loglogn的所以严格来说不算。
------解决方案--------------------
知道了二分法
那么你就很容易理解二叉树

二叉树用来排序,复杂度就是N*Log(N)

相当于做了N次二分法
------解决方案--------------------

探讨

谢谢各位指点，很清楚很明晰

好像快速排序的最坏复杂度是 O(n^2),
最好复杂度是N*Log(N)

请问这是不是和二叉树的效率一样？

也就是说，快速排序就是二叉树排序？

------解决方案--------------------
选择排序法
------解决方案--------------------
能以复杂度O(N)的算法将大问题分解成两个子问题的算法
------解决方案--------------------
分治法：分成c个子问题(divide)，再用O(n)时间合并(conquer),就是o(nlogn)复杂度了(log以c为底)

------解决方案--------------------

探讨
我知道二分法的复杂度是 O(Log(N))

请问什么算法的复杂度是 N*Log(N)？

请教什么情况下的算法复杂度是N*Log(N)

相关推荐