数据结构常见问题：12单元4 算法及描述

1、数据结构课程常见问题 -单元3 算法及描述1算法及描述解析：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。常见的算法有：穷举法，分治法，筛选法，构造法，贪心法，动态规划等。一般说来，算法可以用自然语言、流程图和程序来描述。下面通过一个具体的例子来说明算法的描述方法。例1、H数问题（Hnum）问题描述所谓数，是指该数除以外最多只有2，3，5，7四种因子，如630即为数，而22不是。要求对键盘输入的自然数，求出第个数。如=30，应输出49。规定要求的数不超出长整型数的范围。算法分析从数的定义可以看出，如果一个数是数，那么将它的2，3，5，7四种因子去掉以

2、后必然是剩下1。下面就根据数的这一特性用穷举法来解决这个问题。首先用自然语言描述该算法。算法1_1：穷举法计算第n个H数第一步：从键盘输入一个自然数给N；第二步：将h置为1，order置为1； 表示第一个数为1第三步：如果order=n ，则转第七步；否则转第四步；第四步：h增加1，并将k的值置为h；第五步：将k中的2，3，5，7四种因子去掉；第六步：如果k=1，则order 增加1；第七步：输出h；以上描述中第五步的描述不够明确，下面对去掉k中因子i作更进一步的说明:第1步：如果k是i的倍数，则转第2步，否则算法结束；第2步：将k置为k/i；第3步：转第1步；有了上述用自然语言描述的算法后，

3、就很容易编写出求解数问题的程序（Hnum1.pas），借助计算机来计算结果了。程序中将2，3，5，7存放在数组mark中。参考程序1program Hnum1(input，output);const mark:array 1.4 of integer=(2，3，5，7);var i，h，k，n，order:longint;begin write(Input n:); readln(n); h:=1; order:=1; while order2000时，更是无法满足竞赛的时间要求（一般每个测试点的时限为1秒）。后面将讨论这一问题的更高效的算法。2算法的特性解析：算法是求解问题的步骤或规则的描述

4、，至于用什么工具实现或由谁去执行，算法描述中并没有规定。现代算法通常是作为编程的依据而言的。一个算法虽然与用什么语言去遍程、在什么计算机上运行没有必然的关联，但作为算法设计者来说，对于算法的一些重要特性是应该掌握的。一个算法应该具有下列特性： 有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。 确定性：算法的每一步，必须是确切地定义的，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 输入：一个算法有0个或多个输入。它们是在算法开始前对算法给定的量，这些输入取自于特定对象的集合。 输出

5、：一个算法有一个或多个输出。它们是同输入有某种特定关系的量。 可行性：算法应该是可行的。这意味着算法中所有有待实现的运算都是相当基本的，也就是说，它们原则上都是能够精确地进行的，甚至人们仅用笔和纸做有穷次运算即可完成。3算法的评价解析：对于解决同一个问题，往往能够设计出许多不同的算法。例如，对于数据的排序问题，我们可以用选择排序、冒泡排序、插入排序、快速排序、希尔排序等多种算法，对于这些排序算法，他们各有优缺点，其算法性能如何有待用户的评价。因此，对问题求解的算法优劣的评定称为“算法评价”。算法评价的目的，在于从解决同一问题的不同算法中选择出较为合适的一种算法，或者是对原有的算法进行改造、加工

6、，使其更优、更好。一般对算法进行评价主要有四个方面：（1）算法的正确性正确性是设计和评价一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正确的算法是指在合理的输入数据下，能在有限的运行时间内得到正确的结果。通过对数据输入的所有可能情况的分析和上机调试，以证明算法是否正确。（2）算法的简单性算法简单有利于阅读，也使得证明算法正确性比较容易，同时有利于程序的编写、修改和调试。但是算法简单往往并不是最有效。因此，对于问题的求解，我们往往更注意有效性。有效性比简单性更重要。（3）算法的运行时间：时间复杂性算法的运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行简单操作

7、（如赋值操作，比较操作等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做“算法的时间复杂性”。它是一个算法运行时间的相对量度，一般用数量级的形式给出。度量一个程序的执行时间通常有以下两种方法：一种是“事后统计”的方法。因为很多计算机内部都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用另一种“事前分析估算”的方法。 “事前分析估算”的方法基于：一个用高级程序语

8、言编写的程序在计算机上运行时所消耗的时间取决于下列因素：依据的算法选用何种策略。不同算法、不同策略所消耗的CPU时间显然是不同的； 问题的规模。例如求100以内还是1 000 000以内的素数； 书写程序的语言。对于同一个算法，实现语言的级别越高，执行效率就越低； 编译程序所产生的机器代码的质量：编译器的区别、版本会有所不同； 机器执行指令的速度。显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的

9、规模（通常用整数量n表示），或者说，它是问题规模的函数。一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间度量。例如，在如下所示的两个N*N的矩阵相乘的算法中，“乘法”运算是“矩阵相乘问题”的基本操作。整个算法的执行时间与该基本操作（乘法）重复执行的次数n3 成正比，记作T（n）=O（n3）。 for i:=1 to n do for j:=1 to n do begin c

10、i，j:= 0; for k:=1 to n do ci，j:= ci，j+ai，k * bk，j end;一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作：T（n）= O（f（n）它表示问题规模n的增大、算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。显然，被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数，例如：在下列三个程序段中，x:=x+1for i:=1 to

11、n do x:=x+1;for j:=1 to n do for k:=1 to n do x:=x+1含基本操作“x增1”的语句x:=x+1的频度分别为1，n和 n2 ，则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。算法还可能呈现的时间复杂度有：对数阶O（log n），指数阶O（2n）等。在n很大时， 不同数量级时间复杂度显然有O（1）O（log n）O（n）O（nlog n）O（n2） O（n3）O（2n），可以看出，在算法设计时，我们应该尽可能选用多项式阶O(nk )的算法，而不希望用指数阶的算法。一般情况下，对一个问题(或一类算法)只需

12、选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋以不同权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以计算基本操作执行次数(或语句频度)的情况下，只需求出它关于n的增长率或阶即可，一般可忽略常数项、底阶项、甚至系数。 例如，在下列程序段中:for i:=2 to n do for j:=2 to i-1 do x:=x+1语句x:=x+1执行次数关于n的增长率为n2 ，它是语句频度表达式(n-1)(n-2)/2中增长最快的一项。4、算法所

13、占用的存储空间：空间复杂性算法在运行过程中临时占用的存储空间的大小被定义为“算法的空间复杂性”。空间复杂性包括程序中的变量、过程或函数中的局部变量等所占用的存储空间以及系统为了实现递归所使用的堆栈两部分。算法的空间复杂性一般也以数量级的形式给出。类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的量度，记作S(n)=O(f(n)其中n为问题的规模(或大小)。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外

14、空间，否则应同时考虑输入本身所需空间(和输入数据的表示形式有关)。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析，即以所占空间可能达到的最大值作为其空间复杂度。5、时间和空间复杂性的计算和讨论下面我们通过一个实例，了解算法的时间复杂性和空间复杂性的计算方法。例2、计算y=anxn+an-1xn-1+an-2xn-2+a1x+a0的值。问题分析该问题计算的规模在于n的大小，n越大计算量也越大，乘积和累加的次数也愈多，这里n就是问题的规模。对于该问题的求解的基本条件是：已知x的值和系数a0an。（与问题规模n有关，空间

15、的单元是固定的，若相差几个单元，可以忽略不计）算法2_1：y=a0 ;for k:=1 to n do begin s:=ak ; for j:=1 to k do s:=s*x y:=y+s ; end ;writeln ( y=， y ) ;在该运算中所需存储单元a0，a1， ，an ，以及固定的几个简单变量，所以其空间复杂性与规模n成正比，即为O（n）。而时间复杂性是内循环乘法计算和外循环的累加计算，计算y共用乘法次数是：1+2+3+n=n(n+1)/2， 加法仅n次，而在计算机内部实现乘法要比加法花费更多的时间，所以该算法的时间复杂性为O（n(n+1)/2）O（n*n/2）O（n2）。算法2_2：算法2_1中的乘法运算有重复计算：xk不需要每次从1，x， x2，x3， ， xk乘法去实现，只要在原先xk-1基础上再做一次乘法就可以得到xk 的结果，多用一个b数组存放1，x， x2，x3， ， xn，该问题的空间复杂性为O（2n）O(n)。b0:=1 ;for k:=1 to n do bk:= nk-1 *x ;y:=a0 ;for k:=1 to n do y:=y+ak*bk ;writeln(y=，y);此算法用了两次单循环命令，共用了2n次乘法和n次加法，时间复杂性为O（2n）O(n)