1回答

liuyubobobo

2018-07-18

已采纳

你说的都对。

不过，更更关键的，当我们使用大O来描述算法的复杂度的时候，是忽略常数项的。大O刻画的是当数据规模无穷大的时候，算法性能的趋势。他只是一个趋势，不是精确的时间。我们说O(nlogn)的算法比O(n^2)的算法快，是因为当n无穷大的时候，哪怕O(nlogn)的算法是T = 1000000nlogn，而O(n^2)的算法是T = 2n^2，总有一个n，会使得1000000nlogn < 2n^2，并且随着n逐渐增大，这个差距越来越大（解方程，试试看这个n在哪里？）。但是，当n比较小的时候，就不一定了：）比如n=8的时候，1000000nlogn = 24000000；而2n^2只有128：）

插入排序法就是一个常数项非常小的排序算法，小于大多数排序。同时，对于有序（或者近乎有序）的数据，插入排序还可以进化成为O(n)的算法（因为第二层循环可以提前终止），而小数据量的数组，拥有更高的概率是有序的。所以，可以作为在数据量比较低的时候的一种优化手段：）

3

3

liuyubobobo

回复

Grant_Lian

这里只是举一个相对极端例子。来说明为什么是常数项的作用，让当n小的时候，O(nlogn)的算法反而比O(n^2)的算法慢。实际上不同的nlogn的算法，常数项是不同的，通常也不会这么大，而O(n^2)的算法，也不是没有常数项：）

2018-11-18

共3条回复