我们有三种方法来评估算法:
最坏的情况
最好的情况
和平均情况
第一个告诉我们查看算法可能的最差输入，并评估其性能。
第二个告诉我们查看算法的最佳输入。
最后一个告诉我们查看算法输入的平均情况，因此它可能是算法性能的更准确衡量标准。
为什么我们不通过中值情况来考虑算法，它肯定比平均情况更准确，或者至少是它的补充因素。 因为我们查看一个输入，一半可能的输入位于其下方和上方。
median 给出了 avg 可能无法给出的输入所需的权重。
最佳答案
中位数实际上并没有非常有用的统计属性。
平均值的一个有用之处是，它逐渐变得更不可能得到错误的输入。
假设算法的平均运行时间在 60% 的情况下为 f(n)，在 40% 的情况下为 g(n)，其中 g (n)>>f(n)。那么你的中位数是θ(f(n))，但你的解决方案通常不适合f(n)算法的时隙。但是，即使 g(n) 的概率是一个非常小的常数，平均值仍然是 θ(g(n))，提醒您该算法可能会运行一段时间好久了。
期望值的其他有用属性是求和。如果您有多个按顺序执行的任务，则平均总运行时间将等于平均运行时间的总和。这使得平均值更容易导出和使用。中位数没有类似的属性。
关于algorithm - 为什么我们不通过中值情况复杂度来评估算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52903428/