论文部分内容阅读
摘要：我们以前应用过许多算法分析，虽然这些技术能够成功应用于许多简单的算法，但即使有许多高级技术的支持，数学也远不是万能的。实际上我们能够证明，即使许多貌似简单的算法也是很难用数学的精确性和严格性来分析的。除了可以对算法的效率做数学分析以外，另一种主要的方法是对算法的效率做经验分析。
关键词：算法；效率；伪随机数；散点图
中图分类号：TP302文献标识码：A文章编号：1009-3044(2008)20-30281-02
Empirical Analysis of Algorithms
LI Zhan-xin
（Guangdong Technical School of Metallurgy，Guangzhou 511430，China）
Abstract：Algorithmic analysis has been put into application in many ways.And it has been applied in many simple algorithm successfully. Though this technology has been supported by many other advanced techniques, mathematics are not definitely omnipotent. In fact it has been proved that it is difficult to analyze many seemingly simple algorithm through the accuracy and preciseness of mathematics.Besides mathematic analysis of efficiency of algorithm, we can focus on the empirical analysis of it.
Key words：Algorithms;efficiency;pseudo-random number;scatter diagram
我们常常希望算法具有许多良好的特性，除了正确性，最重要的的特性就是“效率”了。实际上，有两种算法效率：时间效率和空间效率。对特定算法设计技术使问题求解的有效策略。下面这个方案清楚地描述了算法分析中的经验分析。
1 对算法效率做经验分析的通用方案
(1)了解实验的目的。
(2)决定用来度量效率的量度M和度量单位（操作次数还是直接时间）。
(3)决定输入样本的特性（它的范围和大小等）。
(4)为实验准备算法（或者若干算法）的程序实现。
(5)生成输入样本。
(6)对输入样本运行算法（或者若干算法），并记录观察到的实验数据。
(7)分析获得的实验数据。
在做算法的经验分析时，我们的目标往往不尽相同。可选的目标包括：检验算法效率理论上的结论的精确性，比较相同问题的不同算法或者相同算法的不同实现的效率，先假定算法的效率类型，然后在特定的计算机上确定实现该算法的程序效率。显而易见，这种实验的设计依赖于实验者打算探寻什么答案。
2 对算法的效率进行度量的方法
第一种方法就是在算法的程序实现中插入一些计数器来对算法执行的基本操作次数进行计数。这常常是一种简单的操作，我们只要留心程序的哪些地方可以会出现基本操作，并保证对每次基本操作都进行计数。虽然这项工作常常很简单，我们每次修改完程序以后还要对程序做测试，一方面保证它能够正确解决问题，另一方面保证它对基本操作的计数是正确的。
第二种方法是记录待讨论算法的程序实现的运行时间。最简单的做法是利用系统命令，就像UNIX中的time命令一样。另一种测量程序段运行时间的做法是，在程序段德刚开始处（tstart）和才结束时（tfinish）查询系统的时间，然后计算着两个时间的差（tfinish—tstart）。再C和C++中，我们可以用clock函数来达到这个目的；在Java中，System类的currentTimeMillis()方法提供了这个功能。
然而，我们应该了解这样一些事实。第一，一般来说，系统时间并不是十分精确的，对相同程序的相同输入重复运行多次，可能会得到有轻微差异的统计结果。一个明显的补救办法是进行多次这样的度量，然后取它们的平均值或中值作为该样本的观察值。第二，由于现代计算机的速度很快，程序的运行时间可能被报告为0，使得记录完全失败。解决这种困境的标准做法是用一个特定的循环多次运行這段程序，度量总运行时间，然后除以循环的重复次数。第三，在一个运行分时系统（像UNIX）的计算机上，所报告的时间很可能包含了CPU运行其他程序的时间，很明显这完全有悖于实验的初衷。所以我们应该引起注意，并要求系统提供专门用于运行我们的程序的时间（在UNIX中，这个时间称为“用户时间”，time命令中就提供了这个功能）。
因此，度量物理运行时间存在着一些弊端，既有原则上的，也有技术上的，而统计基本操作的运行次数就没有这些缺陷。但另一方面，物理运行时间提供了特定运行环境下的算法性能的详细信息。这些信息对于实验者来说，要比算法的渐进效率类型更重要。另外，对程序不同部分的运行时间进行度量能够提示出程序性能的瓶颈，而对于算法基本操作进行抽象分析是做不到这一点的。搜这样的数据——称为剖面，对于算法运行时间的经验分析来说是宝贵的资源；大多数环境中都提供了相关的系统工具，我们通常可以使用这些工具来获得我们所需要的数据。
3 对算法的效率进行度量的样本输入
无论决定用计时方法还是用基本操作计数法来度量效率，我们都必须确定实验的输入样本。一般来说，我们的目标是用一个样本来代表一类“典型”的输入，所以，我们面临的挑战是理解什么输入是“典型”输入。对于有些类型的算法，比如旅行商问题算法，研究人员制定了一系列输入实例用来作为测试的基准。但更常见的情况是，输入样本必须由实验者来确定。一般来说，我们必须做几方面的决定：样本的规模（一种比较明智的做法是，先从一个相对较小的样本开始，以后如有必要再加大），输入样本的范围（一般来说，既不要小的没有意义，一不要过分大）以及一个在所选择范围为产生输入的程序。就最后一个方面来说，输入的规模即可以符合一种模式（例如，1000，2000，3000，……10000或者500，1000，2000，4000，……128000），也可以随机产生（例如，在最大值和最小值之间均匀分布）。
根据一个模式来改变输入规模的主要高处是，我们很容易分析这种改变所带来的影响。例如，如果一个样本的规模每次都会翻倍，我们可以计算所观察到的度量M之间的比率M(2n)/M(n)，看一看该比率所揭示的算法典型性能是否属于一个基本的效率类型。输入规模不随机变化的主要弊病是存在这种可能性，即我们所研究的算法在我们所挑选的样本上正好表现出非典型的行为。例如，如果所有样本的规模都是偶数，但所研究的算法对于奇数规模的输入却运行得十分缓慢，得出的经验结论就会使人误入歧途。
对于实验样本的规模，我们需要重点考虑的另一个因素是，是否需要包括同样规模样本的多个不同实例。如果我们预测，对于相同规模的不同实例，我们观测到的度量值会有相当的不同，那么，让样本中的每一种规模都包括多个实例是比较明智的（统计学中有许多很成熟的方法帮助实验者来作这种决定）。当然，如果样本中包含相同规模的若干实验，应该计算并研究每种每种规模的观察结果的平均值或者中值，而不是仅仅研究单独的样本点。
4 算法经验分析中的结果分析
对于算法效率的实验分析来说，大多数情况下都需要产生一些随机数。即使我们决定对输入规模应用的一种模式，我们仍然希望输入的实例会自动随机产生。目前，在一台数字式的计算机上产生随机数还是一个难题，因为原理上，这个问题只能近似解决。这就是为什么计算机科学家倾向于把这种数称为伪随机数。从实用的角度看，获得这种数的最简单和最自然的方法是利用计算机语言的函数库提供的随机数发生器。典型情况下，它会输出一个均匀分布在0和1区间中的（伪）随机变量的值。如果需要一个另外一种随机变量，我们应该做一个相应的变换。例如，x是一个均匀分布在0≤x＜1区间上的连续随机变量，变量y=l+x?骔(r-l)」就会均匀地分布在l和r-l间的整数上，其中l和r是两个整数(r＜l)。
另外，有几个已知的生成（伪）随机数的算法，我们可以选择一个来实现。它们中使用最广泛、研究最彻底的一个算法是所谓的线性同余法。
这段简单的算法代码会令人误以为求伪随机数并不复杂，其实如何选择算法参数才是真正的难点。基于复杂的数学分析，这里给出一部分建议：seed可以任意选择，并且常常将它设为当前的日期或者时间；m应该是一个较大数，出于方便的考虑，可以把它定为2w，w是计算机的字长；a可以是0.01m和0.99m间的任何整数，除了a mod 8=5以外，它的值不要体现出任何模式；可以选择1作为b的值。
作为实验结果的经验数据需要记录下来，然后拿来作分析。数据可以用数值的形式记录在表格中或者表现为散点图的形式，散点图就是在笛卡尔儿坐标系中用点将数据标出。任何时候只要可行，都应该同时使用这两种方法，因为这两种方法各有利弊。
以表格呈现数据的主要优点是，我们可以很方便地对它们进行计算。例如，我们可以计算M(n)/g(n)的比率，其中g(n)是所讨论算法的效率类型的候选对象。如果该算法的确属于Θ(g(n))，那么很可能当n变得越来越大时，这个比率会趋向于一个大于0的常数（注意，一个粗心的新手有时会假设这个常数必须为1，这显然是不符合Θ(g(n))的定义的）。我们也可以计算M(2n)/M(n)的比率，看一看当输入的规模翻倍的时候，运行时间是如何变化的。
另一方面，散点图这种形式也会帮助我们确定可能的算法效率类型。一个对数算法的散点图会具有一个上凸的形状，这把它同其它效率类型区分开来。一个线性算法的散点图趋向于分布在一条直线的周围，或者更一般地来说，包含在两根直线的当中区域。属于Θ(nlgn)和Θ(n2)的函数的散点图都会具有一个下凹的形状，使我们很难把它们区分开来。一个立方算法的散点图也具有一个下凹的形状，但它的量度值顯示出非常快速的增长。一个指数算法在垂直轴上很可能需要一种对数刻度，我们在图上标出的不是M(n)，而是logaM(n)(2或者10常常被用作对数的底)。在这样一种坐标系中，一个真正的指数算法的散点图应该像一个线性函数，因为M(n)≈can意味着logbM(n)≈logbc+nlogba。
经验分析的一种可能应用是：对于不包含在实验样本中的输入样本，我们可以试着去与测算法会表现出来的性能。例如，如果在样本实例中，我们观察到的M(n)/g(n)的比率接近某些常数c，对于n的其他值，我们可以用cg(n)的积来近似表示M(n)。这种做法虽然有道理，但我们应该小心使用，尤其对于那些在样本值范围以外的n值来说（相对于专门处理样本范围内的值内推法来说，数学家把
这种方法称为外推法），而且，用这种方法得到的估计值常常不做精确度声明。当然，我们也可以使用标准的数据统计技术来做分析和预测。然而，请注意，大多数这种技术都是基于特定的概率假定，这种假定与所讨论的实验数据可能符合，也可能不符合。
5 结语
最后，我们应该指出算法的数学分析和经验分析的基本区别。数学分析的主要优点是它并不依赖于特定的输入，但它的主要缺点是适用性不强，这一点对于研究平均效率来说尤其明显。经验分析的主要优点是它能够适用于任何算法，但它的结论依赖于实验中使用的特定样本实例和计算机。
参考文献：
[1] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,2006.
[2] Anany Levitin.算法设计与分析[M].潘彦,译.北京:清华大学出版社,2007.
关键词：算法；效率；伪随机数；散点图
中图分类号：TP302文献标识码：A文章编号：1009-3044(2008)20-30281-02
Empirical Analysis of Algorithms
LI Zhan-xin
（Guangdong Technical School of Metallurgy，Guangzhou 511430，China）
Abstract：Algorithmic analysis has been put into application in many ways.And it has been applied in many simple algorithm successfully. Though this technology has been supported by many other advanced techniques, mathematics are not definitely omnipotent. In fact it has been proved that it is difficult to analyze many seemingly simple algorithm through the accuracy and preciseness of mathematics.Besides mathematic analysis of efficiency of algorithm, we can focus on the empirical analysis of it.
Key words：Algorithms;efficiency;pseudo-random number;scatter diagram
我们常常希望算法具有许多良好的特性，除了正确性，最重要的的特性就是“效率”了。实际上，有两种算法效率：时间效率和空间效率。对特定算法设计技术使问题求解的有效策略。下面这个方案清楚地描述了算法分析中的经验分析。
1 对算法效率做经验分析的通用方案
(1)了解实验的目的。
(2)决定用来度量效率的量度M和度量单位（操作次数还是直接时间）。
(3)决定输入样本的特性（它的范围和大小等）。
(4)为实验准备算法（或者若干算法）的程序实现。
(5)生成输入样本。
(6)对输入样本运行算法（或者若干算法），并记录观察到的实验数据。
(7)分析获得的实验数据。
在做算法的经验分析时，我们的目标往往不尽相同。可选的目标包括：检验算法效率理论上的结论的精确性，比较相同问题的不同算法或者相同算法的不同实现的效率，先假定算法的效率类型，然后在特定的计算机上确定实现该算法的程序效率。显而易见，这种实验的设计依赖于实验者打算探寻什么答案。
2 对算法的效率进行度量的方法
第一种方法就是在算法的程序实现中插入一些计数器来对算法执行的基本操作次数进行计数。这常常是一种简单的操作，我们只要留心程序的哪些地方可以会出现基本操作，并保证对每次基本操作都进行计数。虽然这项工作常常很简单，我们每次修改完程序以后还要对程序做测试，一方面保证它能够正确解决问题，另一方面保证它对基本操作的计数是正确的。
第二种方法是记录待讨论算法的程序实现的运行时间。最简单的做法是利用系统命令，就像UNIX中的time命令一样。另一种测量程序段运行时间的做法是，在程序段德刚开始处（tstart）和才结束时（tfinish）查询系统的时间，然后计算着两个时间的差（tfinish—tstart）。再C和C++中，我们可以用clock函数来达到这个目的；在Java中，System类的currentTimeMillis()方法提供了这个功能。
然而，我们应该了解这样一些事实。第一，一般来说，系统时间并不是十分精确的，对相同程序的相同输入重复运行多次，可能会得到有轻微差异的统计结果。一个明显的补救办法是进行多次这样的度量，然后取它们的平均值或中值作为该样本的观察值。第二，由于现代计算机的速度很快，程序的运行时间可能被报告为0，使得记录完全失败。解决这种困境的标准做法是用一个特定的循环多次运行這段程序，度量总运行时间，然后除以循环的重复次数。第三，在一个运行分时系统（像UNIX）的计算机上，所报告的时间很可能包含了CPU运行其他程序的时间，很明显这完全有悖于实验的初衷。所以我们应该引起注意，并要求系统提供专门用于运行我们的程序的时间（在UNIX中，这个时间称为“用户时间”，time命令中就提供了这个功能）。
因此，度量物理运行时间存在着一些弊端，既有原则上的，也有技术上的，而统计基本操作的运行次数就没有这些缺陷。但另一方面，物理运行时间提供了特定运行环境下的算法性能的详细信息。这些信息对于实验者来说，要比算法的渐进效率类型更重要。另外，对程序不同部分的运行时间进行度量能够提示出程序性能的瓶颈，而对于算法基本操作进行抽象分析是做不到这一点的。搜这样的数据——称为剖面，对于算法运行时间的经验分析来说是宝贵的资源；大多数环境中都提供了相关的系统工具，我们通常可以使用这些工具来获得我们所需要的数据。
3 对算法的效率进行度量的样本输入
无论决定用计时方法还是用基本操作计数法来度量效率，我们都必须确定实验的输入样本。一般来说，我们的目标是用一个样本来代表一类“典型”的输入，所以，我们面临的挑战是理解什么输入是“典型”输入。对于有些类型的算法，比如旅行商问题算法，研究人员制定了一系列输入实例用来作为测试的基准。但更常见的情况是，输入样本必须由实验者来确定。一般来说，我们必须做几方面的决定：样本的规模（一种比较明智的做法是，先从一个相对较小的样本开始，以后如有必要再加大），输入样本的范围（一般来说，既不要小的没有意义，一不要过分大）以及一个在所选择范围为产生输入的程序。就最后一个方面来说，输入的规模即可以符合一种模式（例如，1000，2000，3000，……10000或者500，1000，2000，4000，……128000），也可以随机产生（例如，在最大值和最小值之间均匀分布）。
根据一个模式来改变输入规模的主要高处是，我们很容易分析这种改变所带来的影响。例如，如果一个样本的规模每次都会翻倍，我们可以计算所观察到的度量M之间的比率M(2n)/M(n)，看一看该比率所揭示的算法典型性能是否属于一个基本的效率类型。输入规模不随机变化的主要弊病是存在这种可能性，即我们所研究的算法在我们所挑选的样本上正好表现出非典型的行为。例如，如果所有样本的规模都是偶数，但所研究的算法对于奇数规模的输入却运行得十分缓慢，得出的经验结论就会使人误入歧途。
对于实验样本的规模，我们需要重点考虑的另一个因素是，是否需要包括同样规模样本的多个不同实例。如果我们预测，对于相同规模的不同实例，我们观测到的度量值会有相当的不同，那么，让样本中的每一种规模都包括多个实例是比较明智的（统计学中有许多很成熟的方法帮助实验者来作这种决定）。当然，如果样本中包含相同规模的若干实验，应该计算并研究每种每种规模的观察结果的平均值或者中值，而不是仅仅研究单独的样本点。
4 算法经验分析中的结果分析
对于算法效率的实验分析来说，大多数情况下都需要产生一些随机数。即使我们决定对输入规模应用的一种模式，我们仍然希望输入的实例会自动随机产生。目前，在一台数字式的计算机上产生随机数还是一个难题，因为原理上，这个问题只能近似解决。这就是为什么计算机科学家倾向于把这种数称为伪随机数。从实用的角度看，获得这种数的最简单和最自然的方法是利用计算机语言的函数库提供的随机数发生器。典型情况下，它会输出一个均匀分布在0和1区间中的（伪）随机变量的值。如果需要一个另外一种随机变量，我们应该做一个相应的变换。例如，x是一个均匀分布在0≤x＜1区间上的连续随机变量，变量y=l+x?骔(r-l)」就会均匀地分布在l和r-l间的整数上，其中l和r是两个整数(r＜l)。
另外，有几个已知的生成（伪）随机数的算法，我们可以选择一个来实现。它们中使用最广泛、研究最彻底的一个算法是所谓的线性同余法。
这段简单的算法代码会令人误以为求伪随机数并不复杂，其实如何选择算法参数才是真正的难点。基于复杂的数学分析，这里给出一部分建议：seed可以任意选择，并且常常将它设为当前的日期或者时间；m应该是一个较大数，出于方便的考虑，可以把它定为2w，w是计算机的字长；a可以是0.01m和0.99m间的任何整数，除了a mod 8=5以外，它的值不要体现出任何模式；可以选择1作为b的值。
作为实验结果的经验数据需要记录下来，然后拿来作分析。数据可以用数值的形式记录在表格中或者表现为散点图的形式，散点图就是在笛卡尔儿坐标系中用点将数据标出。任何时候只要可行，都应该同时使用这两种方法，因为这两种方法各有利弊。
以表格呈现数据的主要优点是，我们可以很方便地对它们进行计算。例如，我们可以计算M(n)/g(n)的比率，其中g(n)是所讨论算法的效率类型的候选对象。如果该算法的确属于Θ(g(n))，那么很可能当n变得越来越大时，这个比率会趋向于一个大于0的常数（注意，一个粗心的新手有时会假设这个常数必须为1，这显然是不符合Θ(g(n))的定义的）。我们也可以计算M(2n)/M(n)的比率，看一看当输入的规模翻倍的时候，运行时间是如何变化的。
另一方面，散点图这种形式也会帮助我们确定可能的算法效率类型。一个对数算法的散点图会具有一个上凸的形状，这把它同其它效率类型区分开来。一个线性算法的散点图趋向于分布在一条直线的周围，或者更一般地来说，包含在两根直线的当中区域。属于Θ(nlgn)和Θ(n2)的函数的散点图都会具有一个下凹的形状，使我们很难把它们区分开来。一个立方算法的散点图也具有一个下凹的形状，但它的量度值顯示出非常快速的增长。一个指数算法在垂直轴上很可能需要一种对数刻度，我们在图上标出的不是M(n)，而是logaM(n)(2或者10常常被用作对数的底)。在这样一种坐标系中，一个真正的指数算法的散点图应该像一个线性函数，因为M(n)≈can意味着logbM(n)≈logbc+nlogba。
经验分析的一种可能应用是：对于不包含在实验样本中的输入样本，我们可以试着去与测算法会表现出来的性能。例如，如果在样本实例中，我们观察到的M(n)/g(n)的比率接近某些常数c，对于n的其他值，我们可以用cg(n)的积来近似表示M(n)。这种做法虽然有道理，但我们应该小心使用，尤其对于那些在样本值范围以外的n值来说（相对于专门处理样本范围内的值内推法来说，数学家把
这种方法称为外推法），而且，用这种方法得到的估计值常常不做精确度声明。当然，我们也可以使用标准的数据统计技术来做分析和预测。然而，请注意，大多数这种技术都是基于特定的概率假定，这种假定与所讨论的实验数据可能符合，也可能不符合。
5 结语
最后，我们应该指出算法的数学分析和经验分析的基本区别。数学分析的主要优点是它并不依赖于特定的输入，但它的主要缺点是适用性不强，这一点对于研究平均效率来说尤其明显。经验分析的主要优点是它能够适用于任何算法，但它的结论依赖于实验中使用的特定样本实例和计算机。
参考文献：
[1] 严蔚敏,吴伟民.数据结构（C语言版）[M].北京:清华大学出版社,2006.
[2] Anany Levitin.算法设计与分析[M].潘彦,译.北京:清华大学出版社,2007.