归并排序中最后对于递归基的问题
来源：3-3 归并排序法的优化
江景又妍和
2019-03-17
老师，您这一节最后有说过可以自己去尝试一下，在完全随机的情况下，当元素小于什么样的值是最优的呢？我也想着尝试一下，但是可能是我的方法太naive了吧，我只是每次的在15左右不断更改数值。但是我发现这有一个问题，就是说我的电脑不同时刻分配给程序的资源是不同的，所以，即使是一个数值，在不同次运行，也会有时间上的差别，所以我就无法再继续探讨下去了，想请老师指点一番。另外我有在网上看到说当值为7左右的时候最佳，想向老师求证一下，非常感谢～
1回答
-
liuyubobobo
2019-03-17
1
时间肯定有差别，因为对于现代计算机的高级语言编写的算法，算法的实际性能不仅仅和逻辑有关，和具体的实现方式，操作系统的状态，所使用的语言，语言背后的编译器，编译器的优化，等等等都有关系，所以每次运行结果不一样是正常的。
如果真的对这个问题感兴趣，一个合理的方法，是对每一个值都进行多次性能测试（比如1万次），之后对这1万次结果进行统计分析。最简单的方式，就是使用均值。这样的结果，比单次运行结果要可靠很多：）
2
我其实没有具体做过这个研究。关键也在于，其实，对于现代计算机，不同的这个值所带来的性能影响，太小了。对于现代计算机而言，这些细微的性能影响近乎可以忽略不计。甚至不如操作系统的一些小的波动带来的影响。更不用提换一个语言。如果你会另一门脚本语言的话，可以尝试一下（比如Python，PHP，JS，Swift等等），看看使用这些语言，性能测试的结果会怎样，可能会让你大吃一惊：）（应该会慢很多倍。）
所以，真正在生产环境下，除非特殊情况，对于排序，其实不需要这个优化。有兴趣可以看看C++的STL或者Java标准库的源码，对于稳定排序都是用的是归并排序（或者类归并排序），但都没有这个优化：）
在这个课程中，向大家介绍这个优化，主要还是让大家理解插入排序对于近乎有序的数据，包括小量数据，这个O(n^2)的算法反而比O(nlogn)的算法更好。希望通过这个例子，大家对时间复杂度有一个更深刻的认识。时间复杂度只是一个理论工具，是渐进的，所代表的意义是n趋于无穷大时，算法的性能变化优势。他不能完全代表一个具体算法在一个具体数据下的性能：）
加油！：）
412019-03-17
相似问题