第1章数据结构概论-2.ppt

1、算法和算法分析 一、算法的概念和描述： 1、什么是算法 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。,2、 算法描述 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特

2、定关系的量。,3、算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解，便于调试和修改。 (3)健壮性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 (4)高时间效率和高空间效率 时间效率指的是算法的执行时间；空间效率指的是算法的执行所要求的额外的内存空间。对同一个问题，两者一般是矛盾的，在目前的情况下，应首先考虑算法的时间效率。,注意：算法和程序的关系 算法的含义与程序十分相似

3、，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。,二、算法的描述和实现 描述-可采用自然语言、数学语言或约定的符号语言。 实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述-采用Java语言。,一个算法可以借助各种表示工具来描述。 如：从n个整数元素中查找出最大值。 用文字来描述算法： 给n个元素a1an输入数值； 把第1个元素a1赋给用于保存最大值元素的变量x； 把表示下标的变量i赋初值2； 如果ix则将ai赋给x，否则不改变x的值，这使得x始终保存着当前比

4、较过的所有元素的最大值； 使下标i增加1，以指向下一个元素； 转向第d）步继续执行。,算法描述,用流程图来描述算法：,最终用java语言来实现算法：,public class findmax public static void main(String args) int a=1,4,7,2,3; int x=a0; int i=1; while(ix) x=ai; i=i+1; System.out.println(the max element is:+x); ,三、算法分析,时间复杂度 1、时间频度,一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能

5、也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。,同一问题可用不同算法解决，而一个算法的质量优劣将影 响到算法乃至程序的效率。算法分析的目的在于选择合适 算法和改进算法。一个算法的评价主要从时间复杂度和 空间复杂度来考虑。,例1 求下列算法段的语句频度 for(i=1; i=n; i+) for(j =1; j =i ; j+) x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数

6、相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+n=,2、时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数（。记作T(n)=(f(n),称(f(n) 为算法的渐近时间复杂度，简称时间复杂度。 例如，若T(n)=n(n+1)/2,则有 1/4

7、T(n)/n21，故它的时间复杂度为(n2), 即(n)与n2 数量级相同。,算法效率的度量：采用时间复杂度,例1.2 分析以下程序段的时间复杂度 for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; ,/* 1 * /,/* 2 * /,分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是：,则该程序段的时间复杂度： T(n)=, 常见函数的时间复杂度有： O(1)表示算法的时间是一个常数，不依赖于n； O(n)表示算法的时间与n成正比，是线性关系； O(n2)

8、，O(n3) ，O(2n)分别称为平方阶、立方阶和指数阶； O(log2n)为对数阶,例1、x+;s=0; 其时间复杂度仍为(1)，即常量阶。 例2、for(i=0;in; i+) x+;s+=x; 即时间复杂度为线性阶。,语句频度为： 其时间复杂度为：,语句频度为： 其时间复杂度为：,例3、for(i=0;in;i+) for(j=0;jn; j+) cij=0; for(k=0;kn; k+) cij+=aik*bkj; ,语句频度为： 其时间复杂度为：,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3) 指数时间的关系为：O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法运算时间远远超过多项式时