1回答

liuyubobobo

2017-10-25

已采纳

没有理解你的问题。你说的要设置的算法常数具体是什么？你已经看到了3-1章，已经学完了第二章的选择排序法和归并排序法，以选择排序和归并排序为例，你说的要设置的常数是什么？或者以一个具体算法为例，你说的要设置的常数具体指什么？

---

我在课程中所说的算法复杂度的常数，不是开发者设置的，是算法本身固有的。其实很好理解，同样是一个线性复杂度的算法，有的算法可能是100*n，也就是扫描一遍整个数组，但是对数组中的每一个元素，都需要进行100个操作；有的算法可能是1*n，就是扫描一遍数组，对数组中的每一个元素只进行1个操作就够了。注意，对于这两个算法，无论是100*n还是1*n，在我们的算法复杂度表示中，都是O(n)的。因为渐进复杂度符号只是在表达算法的性能和数据规模之间的关系。这两个算法的性能和数据规模之间都是线性的关系。但是对于这个n之前的常数：100或者1，在大O表示中被忽略了。

而实际中，这个常数有可能影响性能，尤其是在数据规模比较小的情况下。继续看这个课程，无论是归并排序还是快速排序，我都会讲一个优化方案，就是在数据较小的时候转而使用插入排序法，这样可以得到大约10%的性能提升。其中的原因就是：插入排序法虽然是O(n^2)级别的算法，但是之前的常数非常低，使得在n比较小的时候，实际性能会更好。

比如一个O(n^2)的算法，实际执行的操作是2*n^2个；

一个O(nlogn)的算法，实际执行的操作是16*n*logn个。

当n=16的时候，O(n^2)的算法需要执行的指令是2*16*16=512个；而O(nlogn)的算法需要执行的指令是16*16*log(16) = 1024个。此时O(n^2)的算法需要执行的指令更少，更快：）

不过同样的例子，自己用计算器看一下，当n=100,1000,10000的时候，O(nlogn)算法的性能优势就会越来越明显。这也是为什么，对算法性能进行测试的时候，我们必须要使用大数据量进行测试的原因。通常情况下，数据量越大，效果越明显：）

更多可以参考我在《算法面试》（http://coding.imooc.com/class/82.html）课程中第二章的介绍：）

加油！

1

2

嘉拉迪雅

非常感谢！

2017-10-27

共2条回复