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

《数据结构 第3讲 算法性能分析解析与度量.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构2知识回顾数据结构的研究内容是什么？数据的逻辑结构、存储结构以及算法抽象数据类型的三元组表示格式是什么，其中的三元指什么？ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名数据对象、关系集、基本操作集什么是算法？算法的描述方法有哪些？3知识回顾将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。算法描述：令k=2当k不大于n时2.1如果这个质数恰等于n，输出k，结束2.2如果n≠k，但n能被k整除，则输出k，并修改n的值（n=n/k),重复执行2.1。2.3如果n

2、不能被k整除，则用k+1作为k的值,重复执行2.1（演示程序）如何衡量一个算法的性能41.5算法性能分析与度量算法的性能标准算法的后期测试算法的事前估计51.5.1算法的性能标准正确性(Correctness)算法应满足具体问题的需求。可使用性（usability）算法设计必须符合抽象数据类型和模块化要求，每个算法只完成一个功能可读性(Readability)算法应该容易阅读。以有利于阅读者对程序的理解。效率效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。健壮性(Robustness)算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应

3、，而不应产生莫名其妙的输出结果。简单性（simplicity）指算法所采用的数据结构和方法的简单程度。算法的简单性便于用户编写、分析和调试1.5算法性能分析与度量61.5.2算法的后期测试事后测试要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。事后分析要求在算法中的某些部位插装时间函数time()，测定算法完成某一功能所花费时间。1.5算法性能分析与度量71.5.2算法的后期测试例如顺序搜索(SequenialSearch)算法1.5算法性能分析与度量intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中

4、搜索与给定值//x相等的元素，函数返回其位置.inti=0;while(i>n;time(&start);intk=seqsearch(a,n,x);time(&stop);doublerunTime=stop-start;cout<<""<

5、me<

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

7、C[n][n]){for(inti=0;i

8、)─大O表