《算法技术手册》一2.3 最好、最坏和平均情况下的性能分析

2.3 最好、最坏和平均情况下的性能分析

也许有人会问，上述结果是否对于所有的输入问题样本都成立？第二种排序算法对于同等规模的其他数据样本表现会如何呢？
输入数据可能包含大量已排好序的元素。
输入数据可能包含重复值。
无论输入数据规模n是多少，元素集合都可以从一个非常小的数据集扩展而来，只不过会有相当多的重复值。
从图2-1上可以看出，第四种排序算法虽然在排序n个乱序字符串时最慢，但它在处理已经排好序的数据时却是最快的。不过，这种领先优势消失得非常快，如图2-2所示，在排序32个乱序的字符串时，第三种排序算法的性能最好。

图2-2：处理完全或者几乎有序的数据时，排序算法的性能
尽管如此，如果一个包含n个字符串的输入“近乎有序”，比如输入数组由有序数组中n/4的字符串（占总字符串的25%）与距离其4个位置的元素交换而得。那么，最终结果会有些出乎意料，如图2-3所示，第四种排序算法的性能表现要远远好于其他排序算法。
对于许多问题来说，单一的最优算法并不存在。选择一个算法需要对问题有着充分的理解，并且知道这个问题将要处理数据规模的概率分布情况，此外还必须考虑算法的实际行为。
这里提供了一些指导性的信息。算法通常可以按以下三类情况进行分析：
最坏情况
最坏情况是指算法对于一类问题样本表现出的最坏性能。通常，算法设计人员在描述最坏情况时，会指出导致算法无法高效执行的输入数据的特征，而并非找出特定的输入数据。
平均情况
平均情况是指算法在随机给定的数据上期望的执行情况。某些问题样本可能会由于一些特例而导致程序需要更长的时间才能完成，但是大多数情况都并非如此。平均情况描述了一般用户对算法性能的期望。
最好情况
最好情况是指算法对于一类问题样本表现出的最好性能。对于这类样本，算法只需要执行很少的计算。在实际情况中，最好情况很少出现。
通过了解算法在每种情况下的性能，读者就能判断它是否适用于特定场景。

图2-3：第四种排序算法在处理几乎有序的数据时性能最好