为什么插入排序 O(n^2) 在排序小数组 ~ 7 元素时更好。与 Quick Sort 和 Merge Sort 等 O(nlogn) 排序算法相比？
Why is Insertion Sort O(n^2) better at sorting small array ~ 7 elements. compare to O(nlogn) sorting algorithm like Quick Sort and Merge Sort?
我看到的：
首先，我已经阅读了另外两个 SO post
Why is Insertion sort better than Quick sort for small list of elements?
Is there ever a good reason to use Insertion Sort?
但是上面的答案对我来说不够具体。
从这两个 post 的回答中，他们主要指出合并排序和快速排序可能会很慢，因为递归函数调用的额外开销。但是我想知道具体的阈值7是怎么设置的？
我的问题：
我想知道为什么截断大约是 7 个元素，其中二次排序算法（如插入排序）比 O(nlogn) 排序算法（如快速排序或合并排序）更快。
- Use insertion sort on small subarrays. Mergesort has too much overhead for tiny subarrays.
- Cutoff to insertion sort for ~ 7 elements.
我从普林斯顿 lecture slide 那里得到了这个，我认为这是一个足够有信誉的来源。请参阅合并排序下的第 11 张幻灯片：实用改进部分。
如果您的回答包含数学证明示例，我将不胜感激。
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^2) 函数会稍微快一些，直到 n 达到大约 13。
我看到的： 首先，我已经阅读了另外两个 SO post
Why is Insertion sort better than Quick sort for small list of elements?
Is there ever a good reason to use Insertion Sort?
但是上面的答案对我来说不够具体。
从这两个 post 的回答中，他们主要指出合并排序和快速排序可能会很慢，因为递归函数调用的额外开销。但是我想知道具体的阈值7是怎么设置的？
我的问题：
我想知道为什么截断大约是 7 个元素，其中二次排序算法（如插入排序）比 O(nlogn) 排序算法（如快速排序或合并排序）更快。
- Use insertion sort on small subarrays. Mergesort has too much overhead for tiny subarrays.
- Cutoff to insertion sort for ~ 7 elements.
我从普林斯顿 lecture slide 那里得到了这个，我认为这是一个足够有信誉的来源。请参阅合并排序下的第 11 张幻灯片：实用改进部分。
如果您的回答包含数学证明示例，我将不胜感激。
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^2) 函数会稍微快一些，直到 n 达到大约 13。