数据结构第3讲算法性能分析与度量.ppt

数据结构,2,知识回顾,数据结构的研究内容是什么？数据的逻辑结构、存储结构以及算法抽象数据类型的三元组表示格式是什么，其中的三元指什么？ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名数据对象、关系集、基本操作集什么是算法？算法的描述方法有哪些？,3,知识回顾,将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。算法描述：令k=2当k不大于n时2.1如果这个质数恰等于n，输出k，结束2.2如果nk，但n能被k整除，则输出k，并修改n的值（n=n/k),重复执行2.1。2.3如果n不能被k整除，则用k+1作为k的值,重复执行2.1（演示程序）,如何衡量一个算法的性能,4,1.5算法性能分析与度量,算法的性能标准算法的后期测试算法的事前估计,5,1.5.1算法的性能标准正确性(Correctness)算法应满足具体问题的需求。可使用性（usability）算法设计必须符合抽象数据类型和模块化要求，每个算法只完成一个功能可读性(Readability)算法应该容易阅读。以有利于阅读者对程序的理解。效率效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。健壮性(Robustness)算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。简单性（simplicity）指算法所采用的数据结构和方法的简单程度。算法的简单性便于用户编写、分析和调试,1.5算法性能分析与度量,6,1.5.2算法的后期测试事后测试要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。事后分析要求在算法中的某些部位插装时间函数time()，测定算法完成某一功能所花费时间。,1.5算法性能分析与度量,7,1.5.2算法的后期测试例如顺序搜索(SequenialSearch)算法,1.5算法性能分析与度量,intseqsearch(inta,intn,intx)/在a0,an-1中搜索与给定值/x相等的元素，函数返回其位置.inti=0;while(in;time(,1.5算法性能分析与度量,事实上，算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。,9,1.5.3算法的事前估计主要包括时间复杂性和空间复杂性的分析：问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。空间复杂性：算法所需空间和问题规模的函数。记为S(n)。当n时的时间复杂性，称为渐进空间复杂性。时间复杂性：算法所需时间和问题规模的函数，记为T(n)。当n时的时间复杂性，称为渐进时间复杂性。,1.5算法性能分析与度量,10,空间复杂度度量存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,1.5算法性能分析与度量,11,时间复杂度度量编译时间运行时间程序步语法上或语义上有意义的一段指令序列；而且这段指令序列的执行时间与问题规模无关；例如：声明语句：程序步数为0;表达式：程序步数为1,1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度,例求两个n阶方阵的乘积C=AB,voidMatrixMultiply(intAnn,intBnn,intCnn)for(inti=0;in;i+)for(intj=0;jn;j+)Cij=0;for(intk=0;kn;k+)Cij=Cij+Aik*Bkj;,1.5算法性能分析与度量,2(n+1),n(2n+2),n2,n2(2n+2),n3,一般地，称n是问题的规模。则时间复杂度T(n)是问题规模n的函数,当且仅当存在正整数c和n0，使得T(n)cf(n)对所有的nn0成立，则称该算法的时间增长率在O(f(n)中，记为T(n)=O(f(n)大O表示法,T(n)=O(n3),12,1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度【例】考察函数f(n)=5当n=0时，c=5，所以f(n)=O(1)【例】考察函数f(n)=3n+2当n2时，3n+24n，所以f(n)=O(n)【例】考察函数f(n)=10n2+4n+2当n5时，10n2+4n+211n2，所以f(n)=O(n2)【例】考察函数f(n)=62n+n2当n4时，62n+n272n，所以f(n)=O(2n),13,(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!),1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。对于单个循环而言，程序段的渐进时间复杂度为循环内简单语句执行次数的大O表示加法规则针对并列程序段T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)乘法规则针对嵌套程序段T(n,m)=T1(n)*T2(m)=O(f(n)*g(m),14,15,T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2),for(inti=0;in;i+)for(intj=0;jn;j+)y+;,for(intk=0;kn;k+)x+;,x=0;y=0;,T1(n)=O(1),T2(n)=O(n),T3(n)=O(n2),1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度,1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度voidexam(floatx,intm,intn)floatsum;for(inti=0;im;i+)sumi=0.0;for(intj=0;jn;j+)sumi+=xij;for(i=0;im;i+)couti“:”sumiaj)inttmp=aj-1;aj-1=aj;aj=tmp;/一趟比较,外层循环n-1趟,内层循环n-i次比较,17,1.5算法性能分析与度量,1.5.4算法的渐进分析1.渐进的时间复杂度,基本语句的执行次数是否只和问题规模有关？,18,例：在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。intFind(intA,intn)for(i=0;i2n=16384n=15时，100n2=225002n=32764取n=15满足要求。