我们需要知道/查找/分析算法的每个情况{最佳、平均和Worst...all}场景吗？

Question

在有关数据结构和算法的书籍中，我们经常看到它们并不分析所有算法的每个案例场景。

一些算法与平均情况一起讨论，一些算法具有平均和最坏情况，而另一些算法则是最佳、平均和最坏情况。

为什么他们倾向于这样做？

为什么我们不需要知道所有算法的所有情况？

Answer 1

除非您控制输入，否则最好的情况通常是无用的。(即最好的情况通常是异常情况)。除非它很容易计算，否则不值得浪费你的时间。

平均情况:这是您通常可以预期的情况。假设您使用的输入范围很大，这通常是需要考虑的最有用的事情。

最坏的情况:如果你处理任意输入(特别是如果他们是不受信任的--即你正在接受来自网络上的人的输入)，那么对于两个平均情况相同的算法来说，这是一个像样的平局。还有一些在设计中需要考虑的问题--这是偶尔会出现的。一般来说，如果你有两个算法是O(n)平均情况，但一个是O(n lg n)最坏情况，另一个是O(n^2) -这可能会影响你选择哪个算法。或者它可能会影响你的算法设计。

例如:快速排序与合并排序。两者都是O(n lg n)快速排序的最坏情况是O(n^2)，合并排序是(IIRC)仍然是O(n lg n) -但一般来说，如果数据适合内存，快速排序往往会更快。即使它有一个更昂贵的最坏情况，因为我们知道它有一个更昂贵的最坏情况，我们可以尝试减轻它(3的中位数而不仅仅是随机分区，等等)。并利用它通常比mergesort更快的事实。

Answer 2

最坏情况分析通常是花费适度努力分析算法的最有用的方法。平均情况更复杂，因为平均情况通常取决于不同输入的可能性，所以您必须根据不同输入的概率来说明平均情况是什么。最好的情况不是很有用，因为我希望我的程序可能在1秒内完成，这不允许我计划一些如果我的程序实际上需要3个小时就会花费太长时间的活动。无论如何，知道它将在五分钟内完成，这一点要有用得多。

最好的情况也有一个问题的程序，存储少量的预先准备的输入和输出，然后检查他们得到的输入与预先准备的输入。如果它们得到匹配，那么它们就会用预先准备好的输出进行响应，而不做其他任何事情，从而获得很好的-但没有意义的-最佳情况行为。

在某些情况下，最坏的情况分析并不是你想要的。一些设计加密算法的人可能想要一个保证，没有人能在10年内破解它(不幸的是，这种保证通常是不存在的)。