Ani*_*tti 6 algorithm code-analysis quicksort
有些人可能在这个可爱的文章都有所涉猎- http://igoro.com/archive/quicksort-killer/ \
真正有趣的是他如何修复快速排序以在O(N log N)中对定义的对手执行.
快速排序可以选择中间元素作为每一步的枢轴,从而始终将输入序列的完美分割为两半.可以在O(N)运行时间确定性地找到中位数,因此总运行时间总是O(N log N).
我的问题是,线性时间中值查找算法最终不会使用相同的比较函数并以O(N ^ 2)而不是O(N)执行？
编辑:
确切地说:我质疑基于分区的中值选择算法的复杂性,该算法使用类似于快速排序的策略,它将使用与快速排序使用的相同的比较功能.如何在这个对手的O(N)中运作？
线性时间中值查找算法最终不会使用相同的比较函数并以O(N ^ 2)而不是O(N)执行？
不,通过添加O(N)函数来找到复杂度变为的中值
O((N+N) log N) == O(2N log N) == O(N log N)
但是,正如该文章所述,增加的常数使其不具吸引力.
标准技术称为3的中位数,完全中位数搜索不会真正改善.
如果最坏的情况很严重,那就不要使用Quicksort.Shellsort有更好的上限.
| 归档时间： |
|
| 查看次数： |
1928 次 |
| 最近记录： |