algorithm - 为什么我们不通过它们的中值复杂度来评估算法

Question

我们有三种评估算法的方法:
最坏的情况
最好的情况
和平均情况

第一个告诉我们查看算法的最差输入，并评估其性能。

第二个告诉我们查看算法的最佳输入。

最后一个告诉我们查看算法输入的平均情况，因此它可能是算法性能的更准确度量。

为什么我们不按中值情况来考虑算法，它肯定比平均情况更准确，或者至少是它的补充因素。因为我们看一个输入，有一半可能的输入在它的下方和上方。

median 给出了 avg 可能无法给出的输入所需的权重。

Answer 1

中位数实际上并没有非常有用的统计属性。

关于平均值的一个有用之处是，它逐渐变得不太可能得到错误的输入。

假设您的算法的平均运行时间在 60% 的情况下为 f(n)，在 40% 的情况下为 g(n)，其中 g (n) >> f(n)。那么您的中位数是 Θ(f(n))，但您的解决方案通常不适合 f(n) 算法的时隙。然而，即使 g(n) 的概率是一个非常小的常数，平均值仍将是 Θ(g(n)) 提醒您该算法可能会运行一个很长一段时间。

期望值的其他有用属性是求和。如果您有许多顺序执行的任务，那么平均总运行时间将等于平均运行时间的总和。这使得平均值更容易推导和使用。中位数没有类似的属性。