为什么我们不通过算法的中值复杂度来评估它们呢
提问于 2018-10-20 07:30:56
我们有三种方法来评估算法：
最坏的情况
最佳案例
和平均案例
第一个告诉我们查看算法可能最差的输入，并评估其性能。
第二个告诉我们查看算法的最佳输入。
最后一个告诉我们查看算法输入的平均情况，因此它可能是更准确地衡量算法性能的方法。
为什么我们不通过它的中值情况来考虑一个算法，它是一个比平均情况更准确的算法，或者至少是它的补充因素。因为我们看一个输入，一半可能的输入在它的下面和上面。
median给出了avg可能不会给出的输入所需的权重。
回答 1
Stack Overflow用户
发布于 2018-10-20 08:44:14
中位数实际上并没有非常有用的统计属性。
关于average的一件有用的事情是，它变得越来越不可能得到错误的输入。
假设您算法的平均运行时间在60%的情况下是f(n)，在40%的情况下是g(n)，其中g(n) >> f(n)。那么你的中位数是Θ(f(n))，但你的解决方案通常不适合f(n)算法的时隙。但是，即使g(n)的概率是一个非常小的常量，average仍然会提醒您算法可能会运行很长时间。
期望值的其他有用属性是求和。如果有许多任务按顺序执行，那么平均总运行时间将等于平均运行时间的总和。这使得average更容易派生和使用。对于中值，没有类似的属性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52903428
复制相关文章
腾讯云开发者
