我最近读了一篇文章,其中谈到了算法的计算复杂性。 作者提到“为什么插入排序在小情况下比快速排序和冒泡排序更快”。有人可以对此做出一些解释吗?
有人知道我上面提到的每种排序算法的实际复杂度吗?
最佳答案
考虑两个复杂度函数:
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)。
关于algorithm - 为什么对于小的情况,插入排序比快速排序和冒泡排序快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7643377/