算法的经验分析

在2.3节和2.4节，我们对递归和非递归算法进行数学的分析。

除了可以对算法的效率做数学分析以外，另一种主要方法是对算法的效率做经验分析。下面这个方案清楚地描述了这种方法的步骤。

对算法效率做经验分析的通用方案

了解实验的目的
决定用来度量效率的度量M和度量单位（单位时间内的操作次数）
决定输入样本的特性（它的范围，大小等等）
为实验准备算法的程序实现
生成输入样本
对输入样本进行算法并纪录观察到的实验数据
分析获得的实验数据

实验目标会影响如何对算法的效率进行度量。统计基本操作运行次数，了解算法的渐进效率；对程序不同部分时间进行度量能够揭示出程序性能的瓶颈。

在对算法执行的基本操作次数进行计数，在算法程序实现出现基本操作处进行计数。

记录算法的程序实现的运行时间。度量物理运行时间，利用系统命令，例如UNIX中的time命令。对程序不同时间进行度量，在程序段的刚开始处(Tstart)和才结束时(Tfinish)查询系统的时间，然后计算这两个时间的差(Tfinish-Tstart) .在C和C++中，clock函数来达到这个目的；在Java中，System类的currentTimeMillis()方法提供了这个功能。

无论决定用记时方法还是用基本操作计数法来度量效率，我们都必须确定实验的输入样本。用一个样本来代表一类“典型”的输入。所以输入样本由我们来确定，我们必须作几方面的决定：样本的规模（比较明智的做法是，先从相对较小的样本开始，以后如有必要再加大），输入样本的范围（不要小得没有意义，也不要过分大），以及一个在所选择范围内产生输入的程序，可以符号一种漠视（例如1000，2000，3000,…)也可以随机产生（例如在最大值和最小值之间均匀分布）。

根据一个模式来改变输入规模的主要好处是，我们很容易分析这种改变所带来的影响。例如，如果一个样本的规模每次都会翻倍，我们可以计算所观察到的度量之间的比率M(2n)/M(n)。主要弊端是存在这种可能性。例如，如果所有样本的规模都是偶数，但所研究的算法对于奇数规模的输入却运行得十分缓慢，我们得出得结论就是不正确的。

对于实验样本的规模，我们需要重点考虑的另一个因素是，是否需要包括同样规模样本的不同实例。如果我们预测，对于相同规模的不同实例，观测到的度量值会有相当的不同，那么，让样本中的每一种规模都包含多个实例是比较明智的，并且计算并研究每种规模的观察结果的平均值或者中值。

对于算法效率的经验分析来说，多数情况写下都需要产生一些随机数。即使我们决定对输入规模应用一种模式，我们仍然希望输入的实例会自动随机产生。计算机语言的函数库提供的随机数发生器，它会输出一个均匀分布在0和1区间中的（伪）随机变量的值。如果需要一个另外一种随机变量，我们应该做一个相应的变换。例如，x是一个均匀分布在区间0≦x<1上的连续随机变量，变量y=l+[x(r-l)]就会均匀地分布在l和r-l间的整数上，其中l和r是两个整数(l < r)

我们使用最广泛，研究最彻底的一个生成伪随机数的算法是所谓的线性同余法.

算法 Random(n, m, seed, a, b)
    //根据线性同余法生成n个伪随机数的一个序列
    //输入：一个正整数n和正整数参数m，seed，a，b
    //注意：我们可以把生成的整数作为小数点后面的数字，来获得0和1区间的伪随机数
    r0 <- seed
    for i <- 1 to n do
        r1 <- (a*r(i-1)+b) mod m

代码不复杂，如何选择算法参数才是真正的难点。seed可以任意选择，并且常常将它设为当前日期或者时间；m应该是一个较大数，出于方便考虑，把它定为2^w, w是计算机的字长；a可以是0.01w和0.99w间的任何整数，可以选择1作为b的值。

作为实验结果的经验数据需要记录下来，拿来做分析。数据可以用表格或者称为散点图的图形呈现，散点图就是在笛卡尔坐标系中用点将数据标出。

以表格呈现数据的主要优点是，我们可以很方便地对它们进行计算。例如，我们可以计算M(n)/g(n)的比率，g(n)是所讨论算法的效率类型的候选对象。如果该算法的确属于Θ(g(n))，这个比率会趋向于一个大于0的常数。我们也可以计算M(2n)/M(n)的比率，看一看当输入的规模翻倍的时候，运行时间是如何变化的。对于对数算法来说，这个比率只会发生很轻微的变化，对于线性，平方和立方算法，在最常见的情况下，这个比率很可能会分别趋向于2，4和8.

散点图也会帮助我们确定可能的算法效率类型。一个对数算法的散点图会具有一个下凹的形状。一个线性算法的额散点图趋向于分布在一条直线的周围。属于Θ(nlgn)和Θ(n^2)函数的散点图都会有一个下凸的形状。一个指数算法在垂直轴上很可能需要一种对数刻度，涂上标出的不是M(n)，而是loga M(n)。在这样一种坐标系中，一个真正的指数算法的散点图应该像一个线性函数。

经验分析的一种可能应用是：对于不包含在实验样本中的输入样本，我们可以试着去预测算法会表现出来的性能。例如，如果在样本的实例中，观察到M(n)/g(n)的比率接近某些常数c，对于n的其他值，我们可以用乘以cg(n)的积来近似表示M(n).

本节的末尾，指出算法的数学分析和经验分析的基本区别。数学分析的主要优点是它并不依赖于特定的输入，但它的主要缺点是适用性不强，这一点对于研究平均效率来说尤为明显。经验分析的主要优点是它能够适用于任何算法，但它的结论依赖于实验中使用的特定样本实例和计算机。