平均情况的复杂度

Question

描述一个算法，最差情况，最好情况，都可以想象出来。但是如果问平均情况，那这是一种什么情况？是把所有可能出现的case都加起来平均一下？

Answer 1

liuyubobobo 2024-01-18 11:43:43

对的。如果 case 不能穷举（比如输入是浮点数），就需要使用微积分的方式。实际上，所谓的平均情况，就是一个算法的复杂度的期望。

但是在大多数时候，平均情况并没有意义。因为一旦最坏情况出现，平均情况再好，在实际生产环境中，依然是极度耗时，不可承受的。但是在极少数情况，这个期望值是很有意义的。比如对于快速排序来说，理论上的最坏情况是 O(n^2) 的，但是对于正确的实现，这个情况出现的概率极低，比彗星撞地球的概率还要低，此时，看这个最坏情况意义不大。我们说快排是 nlogn 的，实际上是快排这个算法的期望（平均情况）。（对于这个分析，我的体系课程有详细分析。）

继续加油！：）