为什么 小规模数据，插入排序法时间复杂度小于归并排序法？
来源：2-2 使用插入排序法优化归并排序法
CregskiN
2020-08-19 15:21:46
老师描述的是 小规模数据，插入排序法O(n^2)“前面的常数”小于归并排序法O(nlogn)“前面的常数”，这块儿没听明白
写回答
1回答
-
比如插入排序的时间时间可能是 T = 2*n^2；而归并排序是 T = 10 * nlogn。
在 n = 8 的时候；2*n^2 = 128；10 * nlogn = 240。
但是，只要 n 无限增大，总会有一个点，10nlogn 会比 2n^2 小。这就是我在课程中强调的，大 O 描述的是 n 趋向于无穷大的时候，算法性能的变化趋势。
继续加油！：）
3
相似问题