4. 最好、最坏与平均情况¶
4.1. 最好、最坏与平均情况¶
分析算法时，我们应该研究最好情况、最坏情况还是平均情况？ 通常我们对最好情况并不感兴趣，因为它可能极少出现，而且对于公允刻画算法的运行时间而言，它往往过于乐观。 换句话说，基于最好情况的分析多半不能代表算法的实际行为。 不过，在少数情况下，最好情况分析也是有用的—特别是当最好情况出现的概率很高时。 Shellsort 和 Quicksort 算法都可以利用 Insertion Sort 的最好情况运行时间，从而变得更高效。
那么最坏情况呢？ 分析最坏情况的优点在于：你可以确切地知道，算法的性能至少不会低于这个水平。 这对实时应用尤其重要，例如用于监控空中交通管制系统的计算机。 在这种场景下，使用这样一个算法是不可接受的：它在 大多数时候 都能足够快地处理 \(n\) 架飞机，但当所有 \(n\) 架飞机都来自同一方向时，却无法足够快地完成任务。
而对于其他应用—特别是当我们想把程序在许多不同输入上多次运行的代价汇总起来时—最坏情况分析可能无法代表算法的性能。 通常我们更想知道平均情况的运行时间。 这意味着我们希望了解算法在规模为 \(n\) 的输入上的 典型 行为。 遗憾的是，平均情况分析并不总是可行的。 平均情况分析首先要求我们了解，程序实际得到的输入（及其代价）相对于程序所有可能输入构成的集合是如何分布的。 例如，前文曾提到，顺序查找算法平均要检查数组中的一半值。 只有当值为 \(K\) 的元素等可能地出现在数组中的任何位置时，这一结论才成立。 如果这个假设不正确，那么该算法在平均情况下 并不 一定检查数组中的一半值。
数据分布的特性对许多查找算法都有显著影响，例如基于 hashing 的算法，以及诸如 BST 这样的查找树。 对数据分布的错误假设，可能给程序的空间或时间性能带来灾难性的后果。 而特殊的数据分布也可以加以利用，例如 self-organizing lists 的做法就是如此。
总之，对于实时应用，我们多半倾向于对算法做最坏情况分析。 否则，如果我们对输入分布足够了解、能够计算平均情况，则往往希望做平均情况分析。 若做不到这一点，就只能采用最坏情况分析。
