为什么插入排序在排序小于等于7个元素的数组时比O(nlogn)的快速排序和归并排序更好？

Question

我看到的： 首先我阅读了这两篇其他的SO帖子

1. 为什么对于小型元素列表插入排序比快速排序更好？

2. 有没有使用插入排序的好理由？

但是，那里的答案对我来说不够具体。

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

我的问题：

我想知道为什么在大约7个元素的情况下，二次排序算法（如插入排序）比O(nlogn)排序算法（如快速排序或归并排序）更快。

• 在小的子数组上使用插入排序。对于微小的子数组来说，归并排序的开销太大了。
• 当元素数量小于 ~7 时，切换到插入排序。

我从普林斯顿大学讲义幻灯片中获取了这个信息，我认为这是一个足够可靠的来源。请查看第11张幻灯片，在“Mergesort: Practical Improvements”部分下面。

如果您的回答包括数学证明示例，我将非常感激。

- OLIVER.KOO

---

请记住的关键是，大O表示算法的规模增长趋势，而不是算法的速度快慢。 - Strikegently

可能是[当输入规模较小时为什么插入排序比快速排序更快？]的重复问题。(https://dev59.com/AnjZa4cB1Zd3GeqPeHI3) - Jim Mischel

@JimMischel提供的SO帖子讨论了这个概念。我在这里想知道具体如何设置7的阈值。 - OLIVER.KOO

阅读该答案的最后一段。这个数字可能比7更多或更少，这取决于操作环境。要确定任何特定计算机的确切值，唯一的方法是进行实验。基于经验结果和两种算法中常数因子的比较，7是一个很好的估计值。 - Jim Mischel

好的，我被说服了。Jim，你写的答案非常好，正是我想要的。我应该链接你的答案然后关闭我的问题吗？我在想为什么那篇帖子的总投票数是负数。 - OLIVER.KOO

Answer 1

Big-O只注重主导因素，随着n的增大，它会忽略常数因素和次要项，而这些因素在n很小时更为显著。因此，对于仅需要处理小输入的算法来说，Big-O几乎没有用处。

例如，你可以有一个时间复杂度为O(n log n)的函数，其时间图像如t = 5n log n + 2n + 3，还可以有一个时间复杂度为O(n^2)的函数，其时间图像如t = 0.5n^2 + n + 2。

比较这两个图像，你会发现尽管按照Big-O的标准，O(n log n)函数应该更快，但是在n约等于13之前，O(n^2)函数会稍微快一点。

- cHao

---

在大O符号表示法中，我们可以说O(n^2)比O(n log n)增长得更快。如果我们为n绘制这些图表，最终O(n^2)可以在特定的n值上超过O(n log n)。您可以查看图表。 - EsmaeelE