数据结构-算法评价

1、练习n解释n数据元素n数据记录n数据结构n说明如何判断给定数据是否具有线性关系的数据n说明常用的数据存储形式2022-6-231算法复杂度分析第一章 绪论n1.1 数据结构讨论的范畴n1.2 数据结构的基本概念与术语n1.3 算法与算法的分析2022-6-232算法复杂度分析 (Niklaus Wirth) Algorithm+Data Structure = Programsn算法：解决问题的策略、方法n数据结构：问题所涉及的数学模型n程序：解决问题的操作步骤，计算机指令的序列第一章 绪论 1.1 数据结构讨论的范畴2022-6-233算法复杂度分析n数据：计算机能够处理的信息的载体n数据元

2、素：最小的独立数据单位n数据记录：具有独立逻辑意义的数据单位n数据结构：包括三部分内容： 数据的逻辑结构、存储结构、算法第一章 绪论 1.2 数据结构的术语与概念2022-6-234算法复杂度分析n数据逻辑结构：树树图图集合集合第一章 绪论 1.2 数据结构的术语与概念2022-6-235算法复杂度分析n数据存储结构：顺序存储：一般利用系统数据组织结构-数组链接存储：一般利用系统数据组织结构-链表索引存储：利用数据空间以外的索引表辅助存储散列存储：利用散列函数辅助存储第一章 绪论 1.2 数据结构的术语与概念2022-6-236算法复杂度分析n算法描述：流程图 N-S图 自然语言 伪代码第一章

3、 绪论 1.2 数据结构的术语与概念2022-6-237算法复杂度分析第一章 绪论 1.3 算法分析n1.3.1 进行算法分析的目的n1.3.2 算法分析概述n1.3.3 空间复杂度分析n1.3.4 时间复杂度分析2022-6-238算法复杂度分析n1.3.1 算法分析的目的算法分析算法分析：是对一种算法所消耗资源的估计资源资源： 包括硬件设备的需求如内存、磁盘空间等 时间的需求如至少需要进行多少基本运算掌握算法分析的目的掌握算法分析的目的：将对同一问题不同算法的代价 进行比较、对需要实现的算法进行资源限 制与资源需求的估计第一章 绪论 1.3 算法分析2022-6-239算法复杂度分析n对算

4、法分析的认识算法分析的关注问题算法分析的关注问题： 增长率（growth rate)： 当问题规模增长时算法代价增长的趋势 增长率的上限与下限： 对于算法消耗资源代价的上下限估计 能够从代价的角度对一般的程序进行分析比较第一章 绪论 1.3 算法分析2022-6-2310算法复杂度分析n1.3.2 算法分析概述 一般考虑四个方面： 1、算法的正确性 2、算法的简单性 3、算法运行时间消耗 4、算法运行空间消耗第一章 绪论 1.3 算法分析2022-6-2311算法复杂度分析n1.3.2.1 算法的正确性分析：在合理的数据输入条件下，在有限的时间内能够得出正确的结果（证明、软件测试、问题要求、容

5、忍的程度） 第一章 绪论 1.3 算法分析2022-6-2312算法复杂度分析n1.3.2.2 算法的简单性：在可选择范围内的首要选择以支持算法可修改、可维护、可靠性第一章 绪论 1.3 算法分析2022-6-2313算法复杂度分析n1.3.2.3 算法时间分析 算法的时间分析涉及两个问题：1、是否可以用程序的运行时间来评价、度量算法的时间效率？ 2、如何度量算法的时间代价是合理的，是在不同算法间可以比较的？第一章 绪论 1.3 算法评价2022-6-2314算法复杂度分析n程序运行时间涉及的问题：1、CUP、RAM、硬盘、语言、OS、 的速度的差异影响程序的速度。 2、算法执行简单操作的次数

6、，可以 用来估计算法的操作时间。第一章 绪论 1.3 算法评价2022-6-2315算法复杂度分析n算法时间评价的结论：1、不能依据程序的执行时间评价算法的时间代价。 2、依据算法中基本操作的次数用估计算法的时间代价，使得算法之间具有可比性。 3、寻找和确定能够评价和比较算法效率的方法，即建立算法间的可比性。（具体方法下一小节详细介绍）第一章 绪论 1.3 算法评价2022-6-2316算法复杂度分析n1.3.2.4 算法空间消耗：空间复杂度分析 1、程序占用空间 2、数据占用空间 3、算法处理过程中的临时空间第一章 绪论 1.3 算法评价2022-6-2317算法复杂度分析n算法空间消耗分析

7、：空间复杂度分析 1、程序占用空间： 在不同程序之间差异不大 2、数据占用空间：由问题的规模决定 3、算法处理过程中的临时空间： 受到问题规模与算法设计的共同影响第一章 绪论 1.3 算法评价2022-6-2318算法复杂度分析n算法空间占用：临时空间占用的分析 临时空间受到问题规模与算法设计的共同影响，分析实例： 1、数据倒序 2、递归程序第一章 绪论 1.3 算法评价2022-6-2319算法复杂度分析n临时空间占用：数据倒序 25891215headtail15589122headtail15128952headtail15129852第一章 绪论 1.3 算法评价2022-6-2320

8、算法复杂度分析n临时空间占用：数据倒序 25891215head15129852headtailheadheadheadheadtailtailtailtailtail第一章 绪论 1.3 算法评价2022-6-2321算法复杂度分析空间对算法效率的影响1. 方法2:增加存储空间n数据量（问题规模）mn交换次数为m2. 方法1:在原存储空间n数据量（问题规模）mn交换次数为 3/2*m2022-6-2322算法复杂度分析n阶乘递归程序临时空间占用 fun(x)int x; if(x=1) return 1; else return(x*fun(x-1); 第一章 绪论 1.3 算法评价 1 n

9、12022-6-2323算法复杂度分析fun(4)4*fun(3)3*fun(2)2*fun(1)4*3*2*1=24fun(x)int x; if(x=1) return 1; else return(x*fun(x-1); 保留现场保留现场保留现场恢复现场恢复现场恢复现场第一章 绪论 1.3 算法评价2022-6-2324算法复杂度分析fun(4)4*fun(3)3*fun(2)2*fun(1)4*3*2*1=241.保留现场4*fun(3)2.保留现场3*fun(2)3.保留现场2*fun(1)4.恢复fun(2)现场 2*15.恢复fun(3)现场 3*26.恢复fun(4)现场 4*

10、61.5.3 算法评价（空间复杂度分析）2022-6-2325算法复杂度分析fun(x)int x; if(x=1) return 1; else return(x*fun(x-1); 4*3*2*1=241.保留现场 4*fun(3)2.保留现场 3*fun(2)3.保留现场 2*fun(1)4.恢复fun(2)现场 2*15.恢复fun(3)现场 3*26.恢复fun(4)现场 4*61.5.3 算法评价（空间复杂度分析）2022-6-2326算法复杂度分析fun(x)int x; if(x=1) return 1; else return(x*fun(x-1); 在没有发生函数运行终止条

11、件之前,系统一直处于数据保留状态,不断地累加保留数据,直到遇到终止条件为止.空间复杂度n存储要求n算法控制方式n算法计算过程中的临时空间2022-6-2327算法复杂度分析n1.3.3 时间复杂度分析第一章 绪论 1.3 算法评价 1、不能依据程序的执行时间评价算法的时间代价。 2、依据算法中简单操作的次数用估计算法 的时间代价，使得算法之间具有可比性。2022-6-2328算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价 抽象计算机 基本操作（元操作） 基本操作的时间 时间复杂度2022-6-2329算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第

12、一章 绪论 1.3 算法评价 我们可以利用抽象计算机来分析和认识算法的时间复杂性分析 图灵机（Turing Machine）: 一种不受存储限制，进行元操作的，理想计算机，在计算机科学与理论研究中具有非常重要的意义（图灵与图灵奖）。2022-6-2330算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价 元操作- 逻辑计算机提供的基本操作。 - 设提供元操作 k 种：- O1,O2,Ok2022-6-2331算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价 元操作时间- K 种元操作各自占用时间为：- t1,t2,tk202

13、2-6-2332算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价 算法A中元操作Oi的操作次数 ei(N) N-问题的规模2022-6-2333算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价算法时间复杂度： 算法所对应的元操作所消耗的时间 算法元操作所进行的次数（时间复杂度）问题的规模： 求解问题算法时所输入的数据量2022-6-2334算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价 算法A的时间消耗消耗 T(N)=t1e1(N)+t2e2(N)+tkek(N) 算法A的时间复杂度复

14、杂度 T(N)=e1(N)+e2(N)+ek(N)2022-6-2335算法复杂度分析n1.3.3 时间复杂度分析（基本概念）第一章 绪论 1.3 算法评价通过分析： 完成算法所需要的时间，与实现算法的 基本操作的次数、算法的规模有关。算法的时间复杂度是问题规模的函数： 记为： T(n) T :表示算法的时间复杂度 n ：问题规模 2022-6-2336算法复杂度分析n1.3.3 时间复杂度分析（实例分析1-累加）第一章 绪论 1.3 算法评价float sum(m,n)float m ; int n; int i; float s; for ( s=0.0,i=0; in; i+) s+=m

15、i; return(s); 简单操作次数：2+6*n T(n) = 2+6n 赋值 2 加法、赋值、 循环处理 比较、加法、 赋值、跳转ns=0;i=0inS+=mii+2022-6-2337算法复杂度分析n1.3.3 时间复杂度分析（实例分析2 - 矩阵）第一章 绪论 1.3 算法评价mul(a,b,c,n)int a1010,b1010,c1010,n; int i,j; for(i=0;in;i+) for(j=0;jn0时，存在常数ab，满足： T(n) a - n0时，存在常数ab，满足： T(n) a - b f(n)2022-6-2342算法复杂度分析n1.3.3 时间复杂度分析

16、（时间复杂度数量级）第一章 绪论 1.3 算法评价一般情况下，在数学上， f(n)是T(n) 的渐近表达式在直观上， f(n)是T(n) 省略低阶数据项后的高阶数据项 2022-6-2343算法复杂度分析n1.3.3 时间复杂度分析（变化趋势的讨论）第一章 绪论 1.3 算法评价实例：设算法时间复杂度为：T(n)=5n+2 存在简单函数: f(n)= n 5n+2 - = 5 + 2/n 当n=5时 n 存在 a=5 b=6 使得： a 5+2/n b 2022-6-2344算法复杂度分析n1.3.3 时间复杂度分析（变化趋势的讨论）第一章 绪论 1.3 算法评价则算法时间复杂度为：T(n)=

17、5n+2 算法时间复杂度数量级为： f(n)= n 2022-6-2345算法复杂度分析n1.3.3 时间复杂度分析（变化趋势的讨论）实例：for(i=0;in;i+) y=y+1; for(k=0;k2*n;k+) x+; 第一章 绪论 1.3 算法评价2022-6-2346算法复杂度分析实例：for(i=0;in;i+) y=y+1; for(k=0;k2 时 T(n) 2n2+n - = - = 2+1/n f(n) n2 a=2; b=3 T(n) 2 - = 2+1/n 3 f(n) 第一章 绪论 1.3 算法评价2022-6-2349算法复杂度分析 所以, 当 T(n) = 2n2

18、+n 时， T(n) 的时间复杂度数量级为： O(n) = n2第一章 绪论 1.3 算法评价2022-6-2350算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级）第一章 绪论 1.3 算法评价常见的算法的时间复杂度数量级：O(log2n) O(n) O(nlog2n), O(n2) O(2n) O(n!)2022-6-2351算法复杂度分析Log2(n)2022-6-2352算法复杂度分析nlog(n)2022-6-2353算法复杂度分析Log(n)nlog(n)n22022-6-2354算法复杂度分析比较比较2022-6-2355算法复杂度分析n1.3.3 时间复杂度分析（时

19、间复杂度数量级结论）第一章 绪论 1.3 算法评价时间复杂度数量级给我们提供了一个简单工具，可以时间复杂度数量级给我们提供了一个简单工具，可以清楚地对同一问题的不同算法，考察在问题规模变化清楚地对同一问题的不同算法，考察在问题规模变化的情况下，时间代价变化的情况。的情况下，时间代价变化的情况。当我们将算法的核心部分设计基本完成之后，不必完当我们将算法的核心部分设计基本完成之后，不必完成编程，我们就可以估计、比较算法的时间代价，成编程，我们就可以估计、比较算法的时间代价，2022-6-2356算法复杂度分析n典型时间复杂度的程序形式：第一章 绪论 1.3 算法评价实例1： i=1; while

20、( i=n ) i+; ; 频度1 频度n f(n)=n2022-6-2357算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价实例2： i=1; while ( i=n ) i*=2; 频度1 频度 f(n) ？2022-6-2358算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价实例2： i=1; while ( i=n ) i*=2; 频度 f(n) 的分析 循环的功能为 n = 2*2 *2 *2 频度 f(n) 为表达式幂次，即 n = 2f(n)2022-6-2359算法复杂度分析n1.3

21、.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价 频度 f(n) 的分析 循环的功能为 i = 2*2 *2 *2 频度 f(n) 为表达式幂次，即 i = 2f(n) 循环的结果为：i = 2f(n) = n 表达式两边 log ： log22f(n) = log2n f(n) * log22 = log2n2022-6-2360算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价 f(n) * log22 = log2n f(n) = log2n O( log2 n )2022-6-2361算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价实例3： i=1; while ( i=n ) j=1; while(j=n) j*=2; . i+; 复杂度为：n 复杂度为：log2n O(n* log2n)2022-6-2362算法复杂度分析n1.3.3 时间复杂度分析（时间复杂度数量级结论）第一章 绪论 1.3 算法评价实例4： i=1；while ( i=n ) j=1; while(j=i) application code; j+; i+; 运行次数为：1+2+3+n n*(n+1)/2 =（n2+n）* 0.5 f(n)= n2+n O(n)