[调试程序可以证明算法的正确性]程序算法的正确性和效率

【jiaoan.jxxyjl.com--高中信息技术教案】

1、算法的正确性判定

研究计算机算法的目的是为了有效地求出问题的解，用计算机语言描述的算法要在计算机上运行，这引出了对算法效率的分析和讨论。例如在象棋比赛中，对任意给出的一种棋局，可以设计一种算法判断这一棋局的输赢，算法需要从开局起对所有棋子可能进行的移动、移动前后的每一对策作检查，做出应走的棋步。计算步骤是有穷的，但在计算机上运算这一算法需要很长的时间。这就说明计算机只能运行在有穷步内终止的算法。    设计出算法后，应证明该算法对所有可能的合法输入都能计算出正确的结果，这一工作称为算法确认。算法确认与描述实现这一算法的手段无关，例如可以用不同计算机语言来实现这一算法。用算法语言描述构成的程序在计算机上运行，也应证明该程序是正确的，这一工作称为程序证明。    对程序的测试包括调试和作时空分布图。调试程序是在抽象数据集上执行程序，确定是否会产生错误的结果，如果出现错误，进行修改，再做测试。调试只能指出程序有错误，而不能指出程序不存在错误。程序的正确性证明是计算机科学一个重要的研究领域。作时空分布图是用各种给定的测试数据，去调试已经证明是正确的程序，测定一个算法得出运算结果所用去的时间和空间，给出时空分布图，验证对算法所作的分析是否正确，找出算法最优化的有效逻辑位置，优化算法的效率。

2、算法的最优性

求解一个问题，如果规定了算法所允许的运算类型，则所有可能的算法构成了解决这个问题的一个算法类，判断一个算法是否最优的依据，是该算法的平均性态分析。若在选择的算法类中，如果一个算法比所有的算法执行的基本运算少，此算法应该是最优的。    判断一个算法是否最优，并不需要对算法类中的每一个算法逐个进行分析，可以根据这个算法类的特性，确定所需运算次数的下界，在算法类中所有运算次数等于这个下界的算法是最优的，这也说明最优算法不是惟一的。需要做两件工作确定解决一个问题至少需要多少次运算：① 设计一个有效率的算法a，分析a并找到一个函数f，使对尺度为n的输入，a最多做f(n)次基本运算；② 对某一函数g，证明一个定理，表明对所考虑的算法类中的任何一个算法，存在一个尺度为n的输入，使算法至少要做g(n)次基本运算。    若函数f与g相等，则算法a是最优的；若不相等，则可能存在一个更好的算法或更好的下界。

3、分析算法

   （1） 分析算法的两个主要内容    要分析一个算法首先要确定使用哪些算法以及执行这些算法所用的时间。运算可以分为两类，一类是基本运算，包括加、减、乘、除四种基本的整数算术运算以及浮点算术、比较、对变量赋值和过程调用等。这些运算所用的时间不同，但都是花费一个固定量的时间。另一类运算由一些基本运算的任意长序列组成，以两个字符串的比较运算为例，可以看做是一系列字符比较指令运算，而字符比较指令可以使用移位和位比较指令。比较两个字符的运算时间是固定的，是某一个常数值，而比较两个字符串的运算时间值则与字符串的长度相关。    其次是确定能反映出算法在各种情况下工作的测试数据集，设计和编制出能够产生最优、最差运算结果的输入数据配置，这些数据配置能够代表可能出现的典型情况。数据配置的设计是创造性的工作，应能最大限度地适应算法，反映算法运行的环境和功能要求。   （2） 分析算法的两个阶段    对一个算法作出分析分为两个阶段，即事前分析和事后测试。    事前分析（priori analysis），求出该算法的一个时间界限函数，用于对计算时间的渐进表示，假定某一算法的计算时间是f(n)，其中变量n表示输入或输出量，它可以是两者之和，也可以是它们之一的一种测度，例如数组的维数、图的边数等，f(n)与机器和语言有关。g(n)是在事前分析中确定的某个形式很简单的函数，是独立于机器和语言的函数，例如nm、logn、2n、n!等。给出定义：    若存在两个正常数c和n0，对于所有的n≥n0，下式成立                ｜f(n)｜ ≤ c｜ g(n)｜记作                     f(n)= o(g(n))    因此，当讲一个算法具有o(g(n))的计算时间时，指的是若该算法用n值不变的同一类数据在某台机器上运行时，所用的时间是小于｜ g(n)|的一个常数倍，所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)，在确定f(n)的数量级时总是试图求出最小的g(n)，使得f(n)= o(g(n))。    事后测试（posteriori testing），收集该算法的执行时间和实际占用空间的统计资料，是在对算法进行设计、确认、事前分析、编码和调试后要做的工作，即作时空性能分布图，事后测试的结果与所用机器相关。要确定算法的精确计算时间，必须了解时钟的精确度以及计算机所用操作系统的工作方式。为避免因所用机器不同而出现误差，有两种可以选用的方法：一种方法是增加输入规模，直到得到算法所需的可靠的时间总量；第二种方法是取足够大的算法重复因子r，将该算法执行r次，然后用总的时间去除以r。    例如，对于事前分析为o(g(n))时间的算法，选择按输入不断增大其规模的数据集，用这些数据集在计算机上运行算法程序，得出算法所使用的时间，画出这一数量级的时间曲线，并与事前分析所得出的曲线比较。

本文来源：https://jiaoan.jxxyjl.com/gaozhongxinxijishujiaoan/31922.html