数据结构1-2算法分析

1、2. 算法分析,算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。,1,2,3,Step1：寻找鸡蛋。分钟后仍没找到，打电话给老婆，终于找到。 Step2：洗鸡蛋。 Step3：打鸡蛋。轻轻磕，用力磕，用大力磕。 Step4：清理操作台上的鸡蛋清。 Step 5：清理碗中的鸡蛋壳。用筷子夹，用勺子舀，用手抓，成功了（现在知道为什么要洗鸡蛋了吧）。 Step6：搅拌。清理脸上、手上和衣服上的鸡蛋清。 Step 7：发现碗中的鸡蛋没剩下多少，又拿出两枚，重复 Step 8：打火，打不着。还是打不着。怎么打也打不着。 Step 9：打电话问

2、老婆。 Step 10：拧开气阀，终于打着了。 Step 11：擦红花油，简单处理脸部灼伤。 Step 12：放油。 Step 13：倒掉红花油，重新放入花生油。哎，一字之差！ Step 14：等待油热，并幻想老婆吃鸡蛋时被表扬。 Step 15：救火，扇子扇，水泼，火越烧越大。 Step 16：在浓烟中爬着去找电话。 Step 17：在电话旁思考火警电话是、还是。,4,haha()/*only a joke,do nothing.*/ main()printf(请稍等.您将知道世界的未日.); while(1) haha(); ,算法的五个重要的特性：,(1) 有穷性：在有穷步之后结束，每一

3、步都在有穷时间内完成。,5,算法的五个重要的特性：,(1) 有穷性：在有穷步之后结束，每一步都在有穷时间内完成。,(2) 确定性：每一条指令必须有明确的含义，算法只有唯一的一条执行路径。,(3) 可行性：可通过基本运算有限次执行来实现。,6,输入：有0个或多个输入； 输出：有一个或多个输出； getsum(int num)int i,sum=0; for(i=1;i=num;i+) sum+=i; ,算法的五个重要的特性：,无输出的算法没有任何意义 !,7,确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在相同的条件下，算法对于相同的输入只能得出相同的输出。 下面代码有何问

4、题？ float average(int *a,int num) /* num为数组a元素个数 */ int i; double sum=0; for(i=0;i=num;i+) sum+=*(+a); return sum/num; main() int score9=1,2,3,4,5,6,7,8,9; printf(%f,average(score,9); ,8,考虑下列两段描述： (1) 描述一 void exam1() n2; while (n%20) nn+2; printf(%dn,n); ,华中科大考研题,(2) 描述二 void exam2() y=0; x=5/y; pri

5、ntf(“%d,%dn”,x,y); ,这两段描述是否满足算法的特征,若不满足试问它们违反了哪些特征？,9,解： (1)算法是一个死循环,违反了算法的有穷性特征。 (2)算法包含除零错误,违反了算法的可行性特征。,10,算法的描述,编写算法时，可采用自然语言、流程图、计算机语言描述。,欧几里德算法,m,n,r,例：欧几里德算法辗转相除法求两个自然数 m 和 n 的最大公约数,11, 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束；否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。,例：欧几里德算法,自然语言,算法的描述方法自然语言,12,算法的描

6、述方法自然语言,优点：容易理解 缺点：冗长、二义性、不易转成程序,13,例：欧几里德算法,算法的描述方法流程图,优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次,14,int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n; ,程序设计语言,例：欧几里德算法,算法的描述方法程序设计语言（伪代码）,15,16,伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。

7、 优点：表达能力强，抽象性强，容易理解,算法的描述方法伪代码,17,（1）正确性（Correctness） 无语法错误 无逻辑错误,算法设计的要求：,（2）可读性（Readability） 晦涩难懂的程序易隐藏错误难以调试维护,18,（3）健壮性（Robustness） 输入数据非法时，不会产生莫名其妙的错误。,算法设计的要求：,（4）效率与低存储的要求,19,算法设计的目标,正确性 可使用性（用户友好性） 可读性 健壮性（很好的容错性） 高效率与低存储量需求,20,算法设计的步骤：,问题描述 模型的选择 算法设计和正确性证明 算法的程序实现 算法分析,21,效率与存储量分析,22,算法分析（

8、Algorithm Analysis）：对算法所需要的计算机资源时间和空间进行估算。 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）,算法分析,23,同一问题可以采用多种算法实现。如何比较算法执行效率？ 算法选用的策略 问题的规模：求解的输入量 采用的程序语言 编译程序的好坏 机器执行速度 因此，使用绝对时间单位衡量算法的效率不合适,24,问题规模：输入量的多少 基本语句（程序步）：被视为算法基本运算的一般是最深层循环内的语句。,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,问题规模：n 基本语句：x+,算法分

9、析,25,在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作： T(n)=O(f(n),26,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,算法分析,算法分析大O符号,27,算法的时间复杂度,一个没有循环的算法的基本运算次数与问题规模

10、无关： O（1）常数阶,一个只有一重循环的算法的基本运算次数与问题规模呈线性增大关系： O（n）线性阶,28,算法的时间复杂度,O(1) O(log2(n)O(n)(n2)O(n3)O(2n),29,例： 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #define MAX 20 /*定义最大的方阶*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+) for (j=0;jn;j+) Cij=Aij+Bij; ,30,该算法中的基本运算是两重循环中最深层的语句C

11、ij=Aij+Bij,分析它的频度,即： T(n)= =O(n2),31,例： 分析以下算法的时间复杂度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); ,基本语句或基本操作,32,解：该算法的基本操作是语句s+,其频度： T(n)= =O(n3) 则该算法的时间复杂度为O(n3)。,33,最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的， 通常假设等概率分布,结论：如果问题规模相同，时间代价与输入数据有关，

12、则需要分析最好情况、最坏情况、平均情况。,1.4 算法及算法分析,最好情况、最坏情况、平均情况,34,Void bubble_sort(int a, int n) /起泡排序：将a中整数序列按照升序重新排列 For(i=n-1, change=TRUE; i=1 change = TRUE ,35,分析： 输入集合升序：基本操作次数为0 输入集合逆序：操作次数为：n(n-1)/2 T(n)= =4 =O(n2),36,分析下面语句的时间复杂度：,i=1; while(i=n) i = i*2; 分析：,37,设语句i = i*2的语句频度为f(n)，则有2 f（n）=n，即f（n）=log2n

13、，所以该程序段的时间复杂度T（n）= O(log2n)。,分析下面语句的执行次数：,i=0; s=0; n=100; do i = i+1; s = s+10*i while(NOT(in) AND (sn); 分析：,38,该程序段中，循环语句的执行次数为4（这时i = 4，s = 100），do循环中先执行循环体，后判断条件，直到条件为真时退出循环。,算法空间复杂度度量,一个算法一般占用三部分存贮空间 算法本身占用 输入、输出数据占用： 算法运行中临时占用空间（可变部分） 算法的空间性能以一个算法运行过程中临时占用的存储空间作为度量标准算法空间复杂度，记作S(n)=O(f(n) 时间和空间

14、相互之间有一种制约关系，何者为重需视具体情况而定。,39,算法空间复杂度度量,若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。,40,41,基本操作的实现：,本书约定： 常量的定义： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 数据元素类型约定为：ElemType typedef int Status; /函数类型，函数结果状态代码,41,练习： 1、有下列运行时间函数,分别写出相应的大O表示的运算时间。 (1) T1 (n)=1000; (2) T2 (n)=n2 +1000n; (3) T3(n)= 3n3+100n2+n+1; 2、分析下面语句的时间复杂度： for(i=1;i=n;i+) (2) i=1;k=0; for(j=1;j=i;j+) w