首页 > Algorithm > 比较排序的最优解

比较排序的最优解

Algorithm 2013-06-03

看内核代码内存部分时有红黑树的利用,顺便翻了一下经典的排序算法,比较笨的算法如插入排序、冒泡排序的时间复杂度到了θ(N^2)的程度,但诸如堆排序、归并排序和快速排序的复杂度优化到了θ(NlogN)的程度,其中快排成为均匀杂序里面最快的实践算法,自我YY想着排序算法难道不能优化了?一查阅果真如此:基于比较排序的一般时间复杂度最优值为θ(NlogN)。

比较排序,就是排序算法核心是通过两个值的比较大小来排序的,前面提到的各类排序都是基于比较的,更多参考:WIKI-排序算法。排序是两个数的比较,那么可以将排序的过程构造一个决策树自动前往wiki补充知识),而这个决策树是一个二叉树,如下:

假定有a,b,c三个数进行排序,则构建的决策树如上,(题外话:用dia画图真难看,决策因子都没办法标出来),即为比较排序的一般模型。N个数排序所有可能为N!种,在决策树的表现为有N!个叶子,而排序的时间复杂度则是决策树的深度。

已知的一个定理是:深度为t的二叉树的叶子最多有2^t个 => 具有x个叶子的二叉树深度至少是log x的上界

则知:任何比较排序的时间复杂度在最坏的情况下需要log (N!)的上界

log (N!)

= logN + log(N-1).....+log(1)

> = logN + log(N-1).....+log(N/2) >= (N/2)log(N/2)

= Ω(N log N)

基于比较的排序时间复杂度最优解为Ω(N log N)。


比较排序的最优解来自于OenHan,链接为:http://oenhan.com/sort-optimal-solution
更多阅读