数据结构算法性能分析与量.pptx

《数据结构算法性能分析与量.pptx》由会员分享，可在线阅读，更多相关《数据结构算法性能分析与量.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1知识回顾将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。算法描述：1.令k=22.当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 （演示程序）如何衡量一个算法的性能第1页/共21页2 21.5 算法性能分析与度量 算法的性能标准算法的性能标准 算法的后期测试算法的后期测试 算法的事前估计算法的事前估计第2页/共21页3 31.5.1算法的性能标准 正确性正确性 (Correctness)算法应满足具体问题的需

2、求。可使用性（可使用性（usabilityusability）算法设计必须符合抽象数据类型和模块化要求，每个算法只完成一个功能 可读性可读性(Readability)算法应该容易阅读。以有利于阅读者对程序的理解。效率效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。健壮性健壮性 (Robustness)算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。简单性（简单性（simplicitysimplicity）指算法所采用的数据结构和方法的简单程度。算法的简单性便于用户编写、分析和调试1.5 算法性能分析与度量第3页/共21页4

3、41.5.2算法的后期测试事后测试要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。事后分析要求在算法中的某些部位插装时间函数time()，测定算法完成某一功能测定算法完成某一功能所花费时间。所花费时间。1.5 算法性能分析与度量第4页/共21页5 51.5.2 1.5.2 算法的后期测试算法的后期测试例如顺序搜索例如顺序搜索(Sequenial Search)(Sequenial Search)算法算法1.5 算法性能分析与度量int seqsearch(int a,int n,int x)int seqsearch(int a,int n,int x)/在在a0,an-1a

4、0,an-1中搜索与给定值中搜索与给定值/x/x相等的元素，函数返回其位置相等的元素，函数返回其位置.int i=0;int i=0;while(i n&ai!=x)while(i n&ai!=x)i+;i+;if(i=n)return-1;if(i=n)return-1;return i;return i;第5页/共21页6 6 1.5.2 1.5.2 算法的后期测试算法的后期测试插装插装 time()time()的计时程序的计时程序void TimeSearch()void TimeSearch()int a1001,n;int a1001,n;double start,stop;doub

5、le start,stop;for(int j=0;j=1000;j+)for(int j=0;jn;cinn;time(time(&start);start);int k=seqsearch(a,n,x);int k=seqsearch(a,n,x);time(time(&stop);stop);double runTime=stop-start;double runTime=stop-start;cout n runTime endl;cout n runTime endl;1.5 算法性能分析与度量事实上，算法运行时间要事实上，算法运行时间要受输入规模、利用编译程受输入规模、利用编译程序

6、生成的目标代码的质量、序生成的目标代码的质量、计算机程序指令系统的品计算机程序指令系统的品质和速度等制约。质和速度等制约。第6页/共21页7 71.5.3算法的事前估计主要包括时间复杂性和空间复杂性的分析：问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。空间复杂性：算法所需空间和问题规模的函数。记为 S(n)。当 n 时的时间复杂性，称为渐进空间复杂性。时间复杂性：算法所需时间和问题规模的函数，记为 T(n)。当 n 时的时间复杂性，称为渐进时间复杂性。1.5 算法性能分析与度量第7页/共21页8 8空间复杂度度量 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长

7、成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间1.5 算法性能分析与度量第8页/共21页9 9时间复杂度度量 编译时间 运行时间uu程序步F语法上或语义上有意义的一段指令序列；而且这段指令序列的执行时间与问题规模无关；F例如：声明语句：程序步数为0;表达式：程序步数为11.5 算法性能分析与度量第9页/共21页1.5.4 算法的渐进分析1.1.渐进的时间复杂度例例 求两个求两个n阶方阵的乘积阶方阵的乘积C=A Bvoid MatrixMultiply(int A

8、nn,int Bnn,int Cnn)for(int i=0;i n;i+)for(int j=0;j n;j+)Cij=0;for(int k=0;k n;k+)Cij=Cij+Aik*Bkj;1.5 算法性能分析与度量2(n+1)n(2n+2)n2 n2(2n+2)n3T(n)=3n3+5n2+4n+2语句的频度之和是语句的频度之和是n的函数的函数一般地，称一般地，称 n n 是问题的规模。则时间复杂度是问题的规模。则时间复杂度 T(n)T(n)是问题规模是问题规模 n n 的函数的函数当且仅当存在正整数当且仅当存在正整数c和和n0，使得，使得T(n)cf(n)对所对所有的有的nn0成立，

9、则成立，则称该算法的时间增长率在称该算法的时间增长率在O(f(n)中，记为中，记为T(n)=O(f(n)大大O表示法表示法 T(n)=O(n3)1010第10页/共21页1.5 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)11

10、 11(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)第11页/共21页1.5 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)1212第12页/共21页1313T(n)=T1(n)+T2(n)+T3(n

11、)=O(max(1,n,n2)=O(n2)for(int i=0;i n;i+)for(int j=0;j n;j+)y+;for(int k=0;k n;k+)x+;x=0;y=0;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)1.5 1.5 算法性能分析与度量算法性能分析与度量1.5.4 1.5.4 算法的渐进分析算法的渐进分析1.1.渐进的时间复杂度渐进的时间复杂度第13页/共21页1.5 1.5 算法性能分析与度量1.5.4算法的渐进分析1.渐进的时间复杂度void exam(float x ,int m,int n)float sum ;for(int i=0;i m

12、;i+)sumi=0.0;for(int j=0;j n;j+)sumi+=xij;for(i=0;i m;i+)cout i “:”sum i endl;渐进时间复杂度为渐进时间复杂度为T(m,n)=T(m,n)=O(max(T3,T4)=O(mn)T1(m)=O(m)T2(n)=O(n)T3(m,n)=T1(m)T2(n)=O(mn)T4(m)=O(m)1414第14页/共21页1.5 1.5 算法性能分析与度量1.5.4算法的渐进分析1.渐进的时间复杂度void bubbleSort(int a,int n)/冒泡排序/对表 a 逐趟比较,n 是表当前长度 for(int i=1;i=i

13、;j-)if(aj-1 aj)int tmp=aj-1;aj-1=aj;aj=tmp;/一趟比较 外层循环外层循环 n-1 趟趟内层循环内层循环 n-i 次比较次比较1515第15页/共21页1.5 1.5 算法性能分析与度量1.5.4算法的渐进分析1.渐进的时间复杂度基本语句的执行次数是否只和问题规模有关？1616例：在一维整型数组A A n n 中顺序查找与给定值k k相等的元素（假设该数组中有且仅有一个元素值为k k）。int Find(int A,int n)for(i=0;i n;i+)if(Ai=k)return i;return-1;循环体语句的频度不仅循环体语句的频度不仅与与

14、n 有关，还与有关，还与 A 中中各元素的取值以及各元素的取值以及 k 的的取值有关取值有关结论：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。第16页/共21页1.5 1.5 算法性能分析与度量1.5.4算法的渐进分析2.渐进的空间复杂度算法执行过程中所需要的空间有：算法本身占用的空间，取决于算法的长度输入输出数据占用的空间，取决于问题，与算法无关辅助存储空间，即算法临时开辟的存储空间，与算法有关算法的空间复杂度是对算法的执行过程需要的辅助空间进行度量。通常记作 S(n)=O(f(n)其中，n是问题规模，分析方法与时间复杂度类似1717第17页/共21页绪绪 论论数据结构数据结构算算 法法基本概念逻辑结构存储结构数据数据元素数据对象ADT逻辑结构数据结构分类存储结构常用存储方法基本概念算法分析算法算法特性评价算法描述算法问题规模基本语句时间复杂度大O记号关 系本章小结本章小结-知识结构图知识结构图1919第19页/共21页作业1.131.161.172020第20页/共21页感谢您的观看。第21页/共21页