时间为什么变慢了
来源：2-2 实现插入排序法
pangzi264118
2020-07-24 09:01:29
老师您好 按照您在这一小节关于for循环条件的优化之后，我发现一个有趣的事情。当n==10000时，执行时间会比优化前快 0.01s 当n==100000时，执行时间会比优化前慢0.01s 我不太明白为啥是这样。观察老师的视频解说也是一样的结果 老师对此有何见解吗？？
写回答
1回答
-
这个结论是不能稳定复现的，比如我进行了一次测试，在我的计算机上，结果是这样的：
InsertionSort , n = 10000 : 0.156131 s InsertionSort2 , n = 10000 : 0.139387 s InsertionSort , n = 100000 : 15.845891 s InsertionSort2 , n = 100000 : 15.611283 s
两次，第二种写法都更快一些。
实际上，如果你仅仅是运行两次的话，最大的干扰是，两次的测试数据可能不一致。（上述测试数据是一样的，在课程后续，我会介绍创建一样的测试数据做比较。）
另外，对于一个 O(n^2) 的算法来说，10 万级别的数据，0.01 s 的差距也太小了，操作系统本身的扰动也肯能造成这个差距。一个更合理的比较方法，是多次测量然后做统计分析。
不过在课程中我应该强调过，我不太建议同学们对这种因为逻辑书写的方式不同而造成的极其细微的性能变化过多的关注。这不是我们学习算法的重点。学习算法的重点还是应该放到算法逻辑上。到后续你就会看到，一旦我们使用高级的排序算法，不要说 10 万级别的数据，100 万级别的数据都在1 秒钟以内轻松搞定。这种级别的优化，是变换算法的逻辑书写方式，无论如何都做不到的。我们还是要把更多的注意力放在这种算法的“质”的优化上：）
赞细心观察&实验精神。继续加油！：）
0
相似问题