∥如果T的三个元素按升序排列则返回1,否则返回0 return(t0}<=r1])&(r1<=T2]); ∥ IsAscending Status IsDescending(Triplet T) ∥如果T的三个元素按降序排列,则返回1,否则返回0。 wun(r0]>=r[)&&(叫1]>=r(2); ∥ IsDescending Status Max(Triplet T, Elem Type &e) ∥用e返回指向T的最大元素的值。 e=(T(0>=r{1)?(N0)>*r2])?0:r2]) (r[1>=T2])?r[1]:r2]); nturn OK ∥Hx Status Min(triplet T, Mlenfype &e)i ∥用e返回指向T的最小元素的值。 e=(r(0!<=r[1])?(r(0]<=r[2])?70】:f2]) ;(N1<=r2])?m[1:T2]); return OK ∥Min 14算法和算法分析 141算法 算法( Algorithm)是对特定问题求解步骤的一种描述它是指令的有限序列,其中 每一条指令表示一个或多个操作;此外,一个算法还具有下列五个重要特性: (1)有穷性一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且 每一步都可在有穷时间0内完成; (2)确定性算法中每一条指令必须有确切的含义读者理解时不会产生二义性。 并且,在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的 输出。 (3)可行性一个算法是能行的即算法中描述的操作都是可以通过已经实现的基 本运算执行有限次来实现的。 (4)输人一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。 (5)输出一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的 量 142算法设计的要求 通常设计一个“好"的算法应考虑达到以下目标: (1)正确性③( Correctness)算法应当满足具体问题的需求。通常-个大型问题的 需求,要以特定的规格说明方式给出而一个实习问题或练习题,往往就不那么严格,目前 d在此有穷的概念不是纯数学的而实际上是合理的可接受的。 ②有关算法正确性的严证明请念阅参考书目[8 13
多数是用自然语言描述需求它至少应当包括对于输入、输出和加工处理等的明确的无歧 义性的描述。设计或选择的算法应当能正确地反映这种需求,否则算法的正确与否的衡 量准则就不存在了。 正确”一词的含义在通常的用法中有很大差别大体可分为以下四个层次;a程序不 含语法错误;b.程序对于几组输入数据能够得出满足规格说明要求的结果;c.程序对于精 心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;d 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。显然,达到第d层意 义下的正确是极为困难的,所有不同输入数据的数量大得惊人,逐一验证的方法是不现实 的。对于大型软件需要进行专业测试而一般情况下通常以第c层意义的正确性作为衡 量一个程序是否合格的标准。 (2)可该性( Readability)算法主要是为了人的阅读与交流其次才是机器执行。可 读性好有助于人对箅法的理解;晦涩难的程序易于隐藏较多错误难以调试和修改。 (3)健壮性( Robustness)当输入数据非法时,算法也能适当地作出反应或进行处 理,而不会产生莫明其妙的输出结果。例如,一个求凸多边形面积的算法,是采用求各三 角形面积之和的策略来解决问题的。当输入的坐标集合表示的是一个四多边形时不应 继续计算,而应报告输入出错。并且,处理出错的方法应是返回一个表示错误或错误性质 的值,而不是打印错误信息或异常并中止程序的执行,以便在更高的抽象层次上进行处 理 (4)效率与低存储量需求通俗地说,效率指的是算法执行时间。对于同一个问题 如果有多个算法可以解决,执行时间短的算法效率高。存储量需求指算法执行过程中所 需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。求100个人的 平均分与求1000个人的平均分所花的执行时间或运行空间显然有一定的差别。 143算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度 量。而度量一个程序的执行时间通常有两种方法: (1)事后统计的方法。因为很多计算机内部都有计时功能,有的甚至可精确到亳秒 级不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两 个缺陷:一是必须先运行依据算法编制的程序;二是所得时间的统计量依赖于计算机的硬 件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析 估算的方法。 (2)事前分析估算的方法。一个用高级程序语言编写的程序在计算机上运行时所消 耗的时间取决于下列因素: 依据的算法选用何种策略 b.问题的规模,例如求100以内还是1000以内的素数; C.书写程序的语言对于同一个算法实现语言的级别越高执行效率就越低; d.编译程序所产生的机器代码的质量 e.机器执行指令的速度
显然,同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计 算机上运行时效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的 撤开这些与计算机硬件、软件有关的因素,可以认为一个特定算法“运行工作量”的大小, 只依赖于问题的规模(通常用整数量n表示),或者说,它是何题规模的函数。 一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作) 构成的则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法,通常的 做法是从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作,以 该基本操作重复执行的次数作为算法的时间量度。 例如在如下所示的两个NXN矩阵相乘的算法中,“乘法”运算是“矩阵相乘问题” 的基本操作。整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比记 作T(n)=O(n3)9。 for(i=li i<=n;++ i) for(=1; j<=n;++i) [,j=0; for(k=l; k<=n; ++k) c[,j]+a[.k]*顷k,j]; 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数∫(n),算法 的时间量度记作 T(n)=o((n)) 它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同称作算法的 渐近时间复杂度( Asymptotic Time Complexity),简称时间复杂度 显然,被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正 比的原操作,多数情况下它是最深层循环内的语句中的原操作它的执行次数和包含它的 语句的频度相同。语句的频度( Frequency Coun)指的是该语句重复执行的次数例如在 下列三个程序段中, a){++x;s=0; (b)for(1=l;1<n;++i){++x;s+=x;} (c) for(= j<n;++ for(k=1: k<n;++*)1++x;s+= x; I 含基本操作“x增1"的语句的频度分别为1,n和n2,则这三个程序段的时间复杂度分别 为O(1),O(n)和O(n2),分别称为常量阶线性阶和平方阶。算法还可能呈现的时间复 杂度有:对数阶O(logn),指数阶O(2")等。不同数量级时间复杂度的性状如图17所 示。从图中可见,我们应该尽可能选用多项式阶O(n2)的算法,而不希望用指数阶的算 法 一般情况下,对一个问题(或一类算法)只需选择一种基本操作来讨论箅法的时间复 ①“O”的形式定义为12:若f(m)是正整数n的一个函,则xn=0(/(m)丧示存在一个正的常数M,使得当 ≥n时都满足|x,|≤Mf(n)。 15
300 100n 200 1000 51015 图17常见函数的增长率 杂度即可,有时也需要同时考虑几种基本搡作,甚至可以对不同的操作赋以不同权值,以 反映执行不同操作所需的相对时间,这种做法便于综合比较解决同一问题的两种完全不 同的算法 由于算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以糟确计算基 本操作执行次数(或语句频度)的情况下,只需求出它关于n的增长率或阶即可。例如, 在下列程序段中, for(i=2; i<n;++i) far(j=2;j<i-1;+j)|++x;叫[i,j=x; 语句++x的执行次数关于n的增长率为n2,它是语句频度表达式(n-1)(n-2)/2中增 长最快的项。 有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例如在下列起泡排序的算法中, void bubble sort(int a[], int n)t ∥将a中整数序列重新排列成自小至大有序的整数序列。 Eor(i=n-1, change= TRUE; i>1&& change;--i) change FALSE for(」=0;j<i;+j if(a[j]>a[j+1)la[j+→aj+1]; change=mRuE↓ ∥ bubble.ort 交换序列中相邻两个整数”为基本操作。当a中初始序列为自小至大有序基本操作的 执行次数为0;当初始序列为自大至小有序时基本操作的执行次数为n(n-1)/2.对这 类算法的分析,一种解决的办法是计算它的平均值即考虑它对所有可能的输入数据集的 期望值,此时相应的时间复杂度为算法的平均时间复杂度。如假设a中初始输入数据可 能出现n!种的排列情况的概率相等,则起泡排序的平均时间复杂度Tmx(n)=0(n2, 然而,在很多情况下,各种輪入数据集出现的概率难以确定算法的平均时间复杂度也就 难以确定。因此另一种更可行也更常用的办法是讨论算法在最坏情况下的时间复杂度, 即分析最坏情况以估算算法执行时间的一个上界。例如,上述起泡排序的最坏情况为a 16
中初始序列为自大至小有序,则起泡排序算法在最坏情况下的时间复杂度为 T(n)=0(n2)。在本书以后各章中讨论的时间复杂度除特别指明外,均指最坏情况下 的时间复杂度。 实践中我们可以把事前估算和事后统计两种办法结合起来使用。以两个矩阵相乘为 例若上机运行两个10×10的矩阵相乘,执行时间为12ms,则由算法的时间复杂度 (n)=O(n3)可估算两个31×31的矩阵相乘所需时间大致为(31/10).12ms≈38m 144算法的存储空间需求 类似于算法的时间复杂度,本书中以空间复杂度( space complexity)作为算法所需存 储空间的量度,记作 S(n)=o(f(n) 其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所 用指令、常数变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为 实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关则 只需要分析除输入和程序之外的额外空间,否则应同时考虑输入本身所需空间(和输入数 据的表示形式有关)。若额外空间相对于输入数据量来说是常数,则称此算法为原地工 作第10章讨论的有些排序算法就属于这类。又如果所占空间量依赖于特定的输入,则 除特别指明外均按最坏情况来分析