请教什么情况下的算法复杂度是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)？

查看更多 下一篇