在有关数据结构和算法的书籍中，我们经常看到它们并没有分析所有算法的每个案例场景。
一些算法与平均情况一起讨论，一些算法与平均情况和最坏情况一起讨论，而其他算法则结合最佳、平均和最差情况。
为什么他们倾向于这样做？
为什么我们不需要了解所有算法的所有情况？
最佳答案
除非您控制输入，否则最好的情况通常是无用的。 (即最好的情况通常是异常情况)。除非很容易计算，否则不值得浪费您的时间。
一般情况:这是您通常可以期望的情况。假设您使用大范围的输入，这通常是需要考虑的最有用的事情。
最坏的情况:如果您处理任意输入(特别是如果它们不受信任 - 即您正在接受来自网络上的人的输入)，那么对于具有相同平均情况的两种算法来说，这是一个不错的决胜局。在一般设计中也需要考虑一些事情 - 这偶尔会出现。一般来说，如果你有两种算法是 O(n) 平均情况，但一种是 O(n lg n) 最坏情况，一种是 O(n^2) - 它可能会影响你决定使用哪一种。或者它可能会影响您的算法设计。
示例:快速排序与归并排序。两者都是 O(n lg n) Quicksort 的最坏情况是 O(n^2)，合并排序 (IIRC) 仍然是 O(n lg n) - 但一般来说，如果数据适合内存，Quicksort 往往会更快。即使它有一个更昂贵的最坏情况，因为我们知道它有一个更昂贵的最坏情况，我们可以尝试减轻它(三个中位数而不是随机分区等)并利用它通常比归并排序更快。
关于algorithm - 我们是否需要了解/查找/分析算法的每个案例{最佳、平均和最差...所有}场景？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6721816/