1.6　渐近近似

在前面给出的关于Quicksort平均运行时间的结论中得到的是准确结果，但我们还给出了一个以著名函数表示的更简捷的近似表达式，这些著名的函数用来计算准确的数值估计。正如我们将看到的那样，通常来讲，准确结果是很难得到的，或者说得出和解释近似结果至少要容易得多。理想情况下，我们分析算法的目的是得出准确结果；但从实用角度来看，能够做出有用的性能预测，力求导出简捷而准确的近似答案，可能更符合我们的总体目标。

为此，我们需要处理这些近似值的经典技巧。在第4章，我们将研究Euler-Maclaurin求和公式，它提供了一种用积分估计求和的方法。因此，我们可以通过计算

得到近似调和级数。然而，≈的意义还可以更精确，例如，我们可以断定 ，其中是一个常数，在分析中叫作欧拉常数（Euler constant）。虽然没有规定符号O中隐含的常数，但这个公式提供了一种估计HN值的方法，即随着N的增加，估计的HN精度越来越高。此外，如果我们想要估计得更加精确，那么可以推导出一个HN精确到O(N-3)甚至的公式，其中k为任意常数。这种近似方法称为渐近展开（asymptotic expansions），是算法分析的核心，也是第4章的主要内容。

渐近展开的使用可以看作在精确结果（这是理想的目标）与简捷近似（这是实际的需求）之间的一种折中。事实证明，一方面，如果需要，我们通常有能力得出更准确的表达式，但另一方面，我们又没有这样的需求，因为仅含有几项的展开式（如上面HN的表达式）就能将答案精确到多位小数。我们一般用符号≈对结果求和，而不是命名无理常数，例如，定理1.3的结论就是如此。

此外，准确的结果和渐近近似都受制于概率模型所固有的不准确性（这种模型通常都是现实的理想化）和随机波动。表1.1显示了对于不同大小的随机序列，Quicksort所用比较次数的准确值、近似值和经验值。准确值和近似值由定理1.3给出的公式计算得出；经验值是选取100个序列，然后测出的平均值，这些序列由小于106的随机正整数构成。这不仅检验我们讨论的渐近近似，还检验我们所使用的随机排序模型固有的“近似”（忽略了相等关键字）。出现相等关键字时的Quicksort分析在参考资料[28]中有介绍。

表1.1　Quicksort使用的平均比较次数

习题1.20　在由104个小于106的随机整数构成的序列中，有多少关键字可能等于该序列中的其他关键字？运行仿真或进行数学分析（借助于数学计算系统），或两者都做。

习题1.21　用由小于M的随机正整数组成的序列进行实验，其中M=10,000、1000、100或其他值。比较Quicksort作用于这种序列的性能与其作用于相同大小的随机序列的性能。描述使随机排序模型不准确的情况的特征。

习题1.22　如何用类似于表1.1的表格来描述Mergesort的相关特点，讨论这个想法。

在算法理论中，符号O用于隐去所有细节：语句“Mergesort需要O(NlogN)次比较”隐藏了除算法、实现和计算机最基本特征之外的所有内容。在算法分析中，渐近展开提供了一种可控的方式来隐藏不相关的细节，与此同时保留了最重要的信息，尤其是涉及常数因子的信息。功能强大的一般分析工具直接进行渐近展开，因此常常可提供简捷而准确地描述算法性质的表达式的简单直接结论。有时我们利用渐近（估计）来提供比其他方式更准确的程序性能描述。