为什么插入排序O(n^2)在排序小数组~7个元素方面更好。与O(nlogn)排序算法相比，如快速排序和合并排序？

Question

我看到了什么：，我已经读过另外两篇文章了

1. 为什么插入排序比对小元素列表进行快速排序要好？
2. 是否有充分的理由使用插入排序？

，但上的答案对我来说还不够具体。

从这两篇文章的答案中，他们主要指出合并、排序和快速排序可能比较慢，因为递归函数调用会带来额外的开销。但我想知道具体的阈值7是如何设定的？

我的问题：

我想知道为什么截断大约有7个元素，其中插入排序之类的二次排序算法比像快速排序或合并排序这样的O(nlogn)排序算法要快。

• 对小型子数组使用插入排序。Mergesort对于微小的子阵列来说开销太大了。
• 截止到插入排序~7个元素。

我是从普林斯顿大学的讲演幻灯片那里得到的，我认为这是一个很好的来源。参见Mergesort下的第11张幻灯片:实际改进部分。

如果你的答案包括数学证明的例子，我会非常感激的。

Answer 1

大-O只注意到当n变大时占主导地位的因素。它忽略了常数因子和较小的项，它们几乎总是存在的，并且在n很小的时候更显着。因此，对于比较只需要在微小输入上工作的算法来说，Big几乎是无用的。

例如，您可以有一个具有像t = 5n log n + 2n + 3这样的时间图的O( whose )函数，以及一个时间图类似于t = 0.5n^2 + n + 2的O(n^2)函数。

比较这两个图，您会发现，尽管存在大O，O(n^2)函数的速度会稍快，直到n达到13。