算法设计与分析

1.2.5 算法的后验分析

前面我们介绍了如何对非递归算法和递归算法进行数学分析，这些分析技术能够在数量级上对算法进行精确度量。但是，数学不是万能的，实际上，许多貌似简单的算法很难用数学的精确性和严格性来分析，尤其在做平均效率分析时。

算法的后验分析（Posteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。其一般步骤如下： 1. 明确实验目的

在对算法做实验分析时，可能会有不同的目的，例如，检验算法效率理论分析的正确性；比较相同问题的不同算法或相同算法的不同实现间的效率，等等，实验的设计依赖于实验者要寻求什么答案。

2. 决定度量算法效率的方法，为实验准备算法的程序实现

实验目的有时会影响，甚至会决定如何对算法的效率进行度量。一般来说，有以下两种度量方法：

⑴ 计数法。在算法中的适当位置插入一些计数器，来度量算法中基本语句（或某些关键语句）的执行次数。

⑵ 计时法。记录某个特定程序段的运行时间，可以在程序段的开始处和结束处查询系统时间，然后计算这两个时间的差。

在用计时法时需要注意，在分时系统中，所记录的时间很可能包含了CPU运行其他程序的时间（例如系统程序），而实验应该记录的是专门用于执行特定程序段的时间。例如，在UNIX中将这个时间称为用户时间，time命令就提供了这个功能。 3. 决定输入样本，生成实验数据

对于某些典型的算法（例如TSP问题），研究人员已经制定了一系列输入实例作为测试的基准，但大多数情况下，需要实验人员自己确定实验的输入样本。一般来说，通常需要确定：

⑴ 样本的规模。一种可借鉴的方法是先从一个较小的样本规模开始，如果有必要再加大样本规模。

⑵ 样本的范围。一般来说，输入样本的范围不要小得没有意义，也不要过分大。此外，还要设计一个能在所选择的样本范围内产生输入数据的程序。

⑶ 样本的模式。输入样本可以符合一定的模式，也可随机产生。根据一个模式改变输入样本的好处是可以分析这种改变带来的影响，例如，如果一个样本的规模每次都会翻倍，可以通过计算T(2n)/T(n)，考察该比率揭示的算法性能是否符合一个基本的效率类型。

如果对于相同规模的不同输入实例，实验数据和实验结果会有很大不同，则需要考虑是否包括同样规模的多个不同输入实例。例如排序算法，对于同样数据集合的不同初始排列，算法的时间性能会有很大差别。

17

4. 对输入样本运行算法对应的程序，记录得到的实验数据

作为实验结果的数据需要记录下来，通常用表格或者散点图记录实验数据，散点图就是在笛卡儿坐标系中用点将数据标出。以表格呈现数据的优点是直观、清晰，可以方便地对数据进行计算，以散点图呈现数据的优点是可以确定算法的效率类型。例如表1.1是对某算法采用计数法得到的实验数据，图1.7是一个典型的散点图。

表1.1 表格法记录实验数据

规模 次数 1000 11,966 2000 24,303 执行次数或时间 3000 39,992 4000 53,010 5000 67,272 6000 78,692 7000 91,274 8000 113,063 9000 129,799

问题规模n 图1.7 典型的散点图

5. 分析得到的实验数据

根据实验得到的数据，结合实验目的，对实验结果进行分析，并根据实验结果不断调整实验的输入样本，经过对比分析，得出具体算法效率的有关结论。

算法的数学分析和实验分析的基本区别是：数学分析不依赖于特定输入，缺点是适用性不强，尤其对算法做平均性能分析时。实验分析能够适用于任何算法，但缺点是其结论依赖于实验中使用的特定输入实例和特定的计算机系统。

实际应用中，可以采用数学分析和后验分析相结合的方式来分析算法。此时，描述算法效率的函数是在理论上确定的，而其中一些必要的参数则是针对特定计算机或程序根据实验数据得来。

1.3 实验项目——求最大公约数

1. 实验题目

求两个自然数m和n的最大公约数。 2. 实验目的

⑴ 复习数据结构课程的相关知识，实现课程间的平滑过渡；

18

⑵ 掌握并应用算法的数学分析和后验分析方法； ⑶ 理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 3. 实验要求

⑴ 至少设计出三个版本的求最大公约数算法；

⑵ 对所设计的算法采用大O符号进行时间复杂性分析；

⑶ 上机实现算法，并用计数法和计时法分别测算算法的运行时间； ⑷ 通过分析对比，得出自己的结论。 4. 实现提示

设m和n是两个自然数，m和n的最大公约数记为gcd(m, n)，是能够同时被m和n整除的最大整数。下面给出求最大公约数三个版本的算法思想，注意算法中没有对输入数据进行校验。

算法1.4——连续整数检测 1．t=min{m, n}; 2. m除以t，如果余数为0，则执行步骤3，否则，执行第4步； 3．n除以t，如果余数为0，返回t的值作为结果，否则，执行第4步； 4．t=t-1，转第2步； 例如，要计算gcd(66, 12)，首先令t=12，因为66除以12余数不为0，将t减1，而12除以11余数不为0，再将t 减1，重复上述过程，直到t＝6，此时12除以6的余数为0并且66除以6的余数为0，则gcd(66, 12)＝6。

算法1.5——欧几里德算法 1. r=m % n; 2. 循环直到r=0 2.1 m=n; 2.2 n=r; 2.3 r=m % n; 3. 输出n; 例如，要计算gcd(66, 12)，因为66除以12的余数为6，再将12除以6，余数为0，则gcd(66, 12)＝6。

算法1.6——分解质因数 1．将m分解质因数； 2．将n分解质因数； 3．提取m和n中的公共质因数； 4．将m和n中的公共质因数相乘，乘积作为结果输出；

19

例如，要计算gcd(66, 12)，首先分解质因数66=2×3×11，12＝2×2×3，然后提取二者的公共质因数2×3，则gcd(66, 12)＝2×3＝6。

严格地说，算法1.6还不能称为一个真正意义上的算法，因为其中求质因数的步骤没有明确定义（该步骤应该得到一个质因数的数组），如何提取m和n中的公共质因数也没有定义清楚，请读者将这个算法补充完整。

阅读材料——人工神经网络与BP算法

人工神经网络（Artificial Neural Networks，简称ANN）是一个以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态响应而进行信息处理。人工神经网络技术与计算机技术的结合，为人类进一步研究模拟人类智能及了解人脑思维的奥秘开辟了一条新途径。

人类对人工神经网络的研究可以追溯到1943年，心理学家W.S.McCuloch和数理逻辑学家W.Pitts最早提出的人工神经网络模型——M-P模型，这是第一个用数理语言描述人脑的信息处理过程的模型，从此开创了神经科学理论研究的新纪元；1969年，人工智能的创始人之一M.Minsky和S.Papert出版了有较大影响的《感知器》一书，指出感知器功能上的局限性，该论点极大地影响了人工神经网络的研究，至此进入了人工神经网络发展史上长达10年的低潮期。进入80年代后，随着计算机科学、生物技术和光电技术等领域学科的迅速发展，人工神经网络的研究进入到了一个新的大发展阶段。

1982年美国生物学家、物理学家J.Hopfield提出了Hopfield网络模型；1985年

D.E.Rumelhart和J. LMcclelland提出了误差反向传播算法（Back-Propagation Algorithm，简称BP算法），成为至今为止影响较大的一种网络学习方法；1992年，Holland用模拟生物进化的方式提出了遗传算法，用来求解复杂优化问题；1995年Mitra把人工神经网络与模糊逻辑理论、生物细胞学说以及概率论相结合提出了模糊神经网络，使得神经网络的研究取得了突破性进展。

人工神经网络是由许多人工神经元按一定规则连接构成的，其互连模式有许多的种类，常见的一种分类是前馈网络和反馈网络。1988年，以美国学者Rumelhart、Hinton和Williams等为首，提出了基于BP算法的多层前向神经网络，成功地解决了多层神经网络中隐含层神经元连接权值的学习问题。该网络模型一经问世，立即受到众多学者的关注，并取得了很大发展。目前，该网络是最常用、最流行、最成熟的人工神经网络。其学习方式采用误差反向传播算法，具有很强的非逻辑归纳特性。理论研究表明：一个三层的前馈神经网络能够模拟任何复杂的非线性系统。图1是三层前向神经网络拓扑结构图。

20