use*_*752 24 algorithm quicksort insertion-sort
不插入排序O(n ^ 2)>快速排序O(nlogn)...所以对于小n,关系是否相同？
Cas*_*son 20
Big-O Notation描述了n很大时的限制行为,也称为渐近行为.这是近似值.(见http://en.wikipedia.org/wiki/Big_O_notation)
对于小n,插入排序更快,因为快速排序具有来自递归函数调用的额外开销.插入排序也比快速排序更稳定,并且需要更少的内存.
此问题描述了插入排序的一些进一步的好处.(有没有充分的理由使用插入排序？)
Den*_*nis 10
定义"小".
当基准的排序算法,我发现从快速排序切换到排序插入 - 尽管大家有什么在说 - 实际上伤害了超过4个元素较大的阵列性能(在C递归快速).并且可以使用与大小相关的最佳排序算法对这些阵列进行排序.
话虽这么说,但请记住,O(n...)只有比较的数量(在这种特定情况下),而不是算法的速度.速度取决于实现,例如,如果您的快速排序功能是否递归,以及处理函数调用的速度有多快.
最后但并非最不重要的是,大哦符号只是一个上限.
如果算法A需要10000 n log n比较和算法B需要10 n ^ 2,则第一个是O(n log n),第二个是O(n ^ 2).然而,第二个(可能)会更快.
O() 表示法通常用于表征大型问题的性能，同时故意忽略常数因素和对性能的附加偏移。
这很重要，因为常数因素和开销在处理器和实现之间可能会有很大差异：6502 机器上的单线程 Basic 程序的性能将与在 Intel i7 上运行的 C 程序实现的相同算法大不相同级处理器。请注意，实现优化也是一个因素：即使所有其他因素都相同，对细节的关注通常可以使您获得重大的性能提升！
但是，常数因子和开销仍然很重要。如果您的应用程序确保 N 永远不会变得非常大，则 O(N^2) 与 O(N log N) 的渐近行为不会起作用。
插入排序很简单，对于小列表，它通常比实现类似的快速排序或归并排序要快。这就是为什么实际的排序实现通常会退回到“基本情况”的插入排序之类的东西，而不是一直递归到单个元素。
| 归档时间： |
|
| 查看次数： |
37384 次 |
| 最近记录： |