algorithm - 为什么对于小的情况，插入排序比快速排序和冒泡排序快？

Question

我最近读了一篇文章，其中谈到了算法的计算复杂性。作者提到“为什么插入排序在小情况下比快速排序和冒泡排序更快”。有人可以对此做出一些解释吗？

有人知道我上面提到的每种排序算法的实际复杂度吗？

Answer 1

考虑两个复杂度函数:

F(X) = X^2
G(X) = 4 * X * ln(X)

F(3) = 9
G(3) = 13

所以算法 F 赢得了 3 个项目。但是:

F(100) = 10,000
G(100) = 1,842

因此算法 G 在 100 个项目中获胜。

插入排序的复杂度类似于 F(X)。快速排序的复杂度类似于 G(X)。