algorithm - 为什么当输入大小改变时算法的优先级会改变

Question

我正在研究算法的时间复杂度。书中解释说

Running time of insertion sort is O(n^2)

Running time of merge sort is O(n logn)

n较小时插入排序较好，n较大时归并排序较好。
我不明白为什么会这样？为什么当输入大小不同时算法的优先级会不同？

Answer 1

The hidden constant!

给定大小为 n 的输入，假设您有两种插入和合并排序的实现，它们执行以下比较次数*:
- 插入排序 : 8n^2属于 O(n^2)- 归并排序 : 64nlogn属于 O(nlog n)
但是，如果您 solve 8n^2 <= 64nlogn你会得到大小为 43 的输入或更少的插入排序更好。

例如，Python 的内置排序算法，即 Timsort 混合使用插入排序和合并排序。
当 n 很小时(在 Python 的情况下为 64)，Timsort 将使用插入排序来对元素进行排序。
你可以看看 docs了解更多详情。

*算法的不同实现会导致与算法时间复杂度相关的不同常数值。例如，Python 不使用教科书的插入排序，而是使用 二元插入排序 其中通过二分查找找到下一项的正确位置。