1.7　分布

一般来说，概率论告诉我们：关于开销分布的其他事实也与我们对算法性能特点的理解有关。幸运的是，对于我们在算法分析中研究的几乎所有例子，实际上只要知道平均值的渐近估计就足以做出可靠的预测。我们在这里回顾几个基本概念。对概率论不熟悉的读者可以参考任何一本标准教材——例如参考资料[6]。

当N取较小值时，Quicksort所用比较次数的完整分布如图1.2所示。对于N的每个取值，画出点CNk/N!，这是使Quicksort需要进行k次比较的输入比例。因为每条曲线都是完整的概率分布，所以曲线下方的面积为1。平均值2NlnN+O(N)随着N的增加而增加，因此曲线向右移动。针对相同数据略微不同的观察结果如图1.3所示，其中每条曲线的水平轴适当缩放以便将平均值近似地置于中心，并稍微平移以分离这些曲线。这表明，该分布收敛于“极限分布”。

图1.2　Quicksort中比较次数的分布

本书中研究的大多数问题中，不仅确实存在这样的极限分布，而且我们还能精确地描述它们的特征。对于包括Quicksort在内的许多其他问题来说，这是一个重要挑战。然而很明显，这种分布集中在平均值附近（concentrated near the mean）。这种情况是常见的，事实上我们能够对这种结果做精确的表述，并且无须学习关于该分布的更多细节。

图1.3　Quicksort中比较次数的分布（缩放并平移到中心且分离曲线）

正如前面讨论的那样，如果是大小为N的输入组数，是大小为N且使算法开销为k的输入组数，那么平均开销可表示为

方差（variance）被定义为

标准差（standard deviation）是方差的平方根。知道平均值和标准差通常就能可靠地预测性能。完成这项工作的经典分析工具是切比雪夫不等式（Chebyshev inequality）：某一次观察值大于标准差与平均值之间距离的c倍的概率小于1/c2。如果标准差明显小于平均值，那么，随着N的增大，观察值很可能非常接近于平均值。这是算法分析中的常见情况。

习题1.23　本章前面给出的Mergesort实现所需比较次数的标准差是多少？

Quicksort所需平均比较次数的标准差是

（见3.9节），因此，参考表1.1，把带入切比雪夫不等式，我们得出结论：存在超过90%的可能，当时比较次数在2,218,033的205,004（9.2%）之内。这样的精度对预测性能来说肯定是足够的。

随着N的增加，相对精度也在增加。例如，当N增加时，分布变得更集中于图1.4所示的峰值附近。该图描绘了一个直方图，显示出Quicksort作用于10,000个不同随机序列所需的比较次数，其中每个序列都有1,000个元素。阴影区域表示超过94%的实验位于本次实验平均值的一个标准差之内。

图1.4　Quicksort比较次数的经验直方图（当1,000时的10,000次实验）

对于总体运行时间，我们可以通过对每个量的平均值求和（乘以开销）得出，但计算总体运行时间的方差是一个复杂的计算过程。然而我们不必担心这一问题，因为总体方差与最大方差近似相等。当N取值很大时，与平均值相比，标准差相对较小，这解释了表1.1和图1.1观察的精度。在算法分析中总是发生这样的情况，如果我们对平均开销有一个精确的渐近估计，并且知道标准差渐近得更小，那么我们通常认为该算法已经“被完全分析”。