《数据结构 第3讲 算法性能分析与度量》由会员分享，可在线阅读，更多相关《数据结构 第3讲 算法性能分析与度量（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构,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
2、 （演示程序）,如何衡量一个算法的性能,4,1.5 算法性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,5,1.5.1 算法的性能标准 正确性 (Correctness ) 算法应满足具体问题的需求。 可使用性（usability） 算法设计必须符合抽象数据类型和模块化要求，每个算法只完成一个功能 可读性(Readability) 算法应该容易阅读。以有利于阅读者对程序的理解。 效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。 健壮性 (Robustness) 算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。
3、 简单性（simplicity）指算法所采用的数据结构和方法的简单程度。算法的简单性便于用户编写、分析和调试,1.5 算法性能分析与度量,6,1.5.2 算法的后期测试 事后测试要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。 事后分析要求在算法中的某些部位插装时间函数time ( )，测定算法完成某一功能所花费时间。,1.5 算法性能分析与度量,7,1.5.2 算法的后期测试 例如顺序搜索 (Sequenial Search)算法,1.5 算法性能分析与度量,int seqsearch(int a , int n, int x ) /在a0,an-1中搜索与给定值/x相等的
4、元素，函数返回其位置.int i = 0;while ( i n;time( ,1.5 算法性能分析与度量,事实上，算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。,9,1.5.3算法的事前估计 主要包括时间复杂性和空间复杂性的分析： 问题的规模：如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。 空间复杂性：算法所需空间和问题规模的函数。记为 S(n)。当 n 时的时间复杂性，称为渐进空间复杂性。 时间复杂性：算法所需时间和问题规模的函数，记为 T(n)。当 n 时的时间复杂性，称为渐进时间复杂性。,1.5 算法性能分析与度量,10,空
5、间复杂度度量 存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,1.5 算法性能分析与度量,11,时间复杂度度量 编译时间 运行时间 程序步 语法上或语义上有意义的一段指令序列；而且这段指令序列的执行时间与问题规模无关； 例如：声明语句：程序步数为0; 表达式：程序步数为1,1.5 算法性能分析与度量,1.5.4 算法的渐进分析 1.渐进的时间复杂度,例 求两个n阶方阵的乘积C = AB,void Ma
6、trixMultiply (int Ann, 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), n3,一般地，称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数,当且仅当存在正整数c和n0，使得T(n)cf(n)对所有的nn0成立，则称该算法的时间增长率在O(f(n)中，记为T(n) =
7、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
8、.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 ( int i = 0;
9、 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.4 算法的渐进分析 1.渐进的时间复杂度,1.5 算法性能分析与度量,1.5.4 算法的渐进分析 1.渐进的时间复杂度 void exam (float x , int m, int n) float sum ;for (int i = 0; i m; i+) sumi = 0.0; for (int j
10、= 0; j n; j+) sumi += xij;for (i = 0; i m; i+) cout i “ : ” sum i aj) int tmp = aj-1; aj-1 = aj;aj = tmp; /一趟比较 ,外层循环 n-1 趟,内层循环 n-i 次比较,17,1.5 算法性能分析与度量,1.5.4 算法的渐进分析 1.渐进的时间复杂度,基本语句的执行次数是否只和问题规模有关？,18,例：在一维整型数组An中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k）。 int Find(int A , int n) for (i = 0; i 2n = 16384n = 15时，100n2 = 22500 2n = 32764取 n = 15 满足要求。,绪 论,数据结构,算 法,基本概念,逻辑结构,存储结构,数据 数据元素 数据对象 ADT,逻辑结构 数据结构分类,存储结构 常用存储方法,基本概念,算法分析,算法 算法特性 评价算法 描述算法,问题规模 基本语句 时间复杂度 大O记号,关 系,本章小结-知识结构图,21,作业,1.13 1.16 1.17,22,
