1、 制作 周幸妮前言 Chapter Chapter 0 0Data structures and Algorithms 从新视角来看待旧问题，需要有创造性的思维，这标志着科学的真正进步。爱因斯坦数据结构与其他课程的关系4Web信息处理人工智能数据库操作系统编译原理图形图像算法分析与设计数据结构计算复杂性理论概率统计计算概论集合与图论教学内容 1绪论 3运算特殊的线性表栈和队列4内容特殊的线性表字符串和多维数组2结点逻辑关系为线性的结构线性表 5结点逻辑关系分层次的非线性结构树 7数据的处理方法排序技术8数据的处理方法索引与查找技术6结点逻辑关系任意的非线性结构图 9经典算法绪 论 Chapte
2、r Chapter 1 1Data Structures and Algorithm Analysis主要内容 数据结构的概念 算法设计的基本要求 从时间和空间角度分析算法效率的方法学习目标 了解数据结构课程的意义 掌握数据结构的概念 掌握算法设计与程序设计的步骤 掌握算法效率的分析评价方法CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量1.1从编程说起程序的公式表
3、达12算法+数据结构=程序尼古拉斯尼古拉斯沃斯沃斯Niklaus Wirth1934年年2月月15日日算法是处理问题的策略，数据结构是描述问题信息的数据模型，程序则是计算机按照处理问题的策略处理问题信息的一组指令集 计算机解决问题的过程1314程序的开发程序解题程序解题软件工程软件工程具体工作具体工作建模型需求分析阶段提取问题要完成的功能；分析问题涉及的数据对象，找出数据对象之间的关系。设计设计阶段数据结构设计、软件的结构设计、算法设计 编程编码阶段编写程序代码验证测试软件测试与调试CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事
4、前分析方法算法性能的综合考量1.2程序要处理的数据17数值与非数值问题数值计算数值计算非数值计算非数值计算数值计算，具体地说就是有效利用计算机求解数学问题近似解的方法与过程，可以通过抽象出合适的数学模型，然后设计相应的算法来解决。数值计算问题，以浮点算术运算为主，算法成熟所谓“非数值计算”问题，是为了区分前面提到的“数值问题”而言。非数值问题涉及到的数据及数据间的相互关系，一般无法用数学公式、方程等来描述，如排序问题、检索问题等，需要另外设计数据的描述方法和相应的算法来处理。18从下面的无限序列中计算出的值。输出一个表格，在该表格中显示根据这个序列中的1项、2项、3项等等所得的近似值。在第一次
5、得到3.14之前，必须使用这个序列的多少项？如果是得到3.141呢？3.1415呢？3.14159呢？数值问题的例子.114947454344通用公式数据对象数据间关系数据初始化建模型m=1;i=1-1偶数1奇数m取值i取值项数：当前已经用到的项数i系数：控制序列项的正负号 m4+（-1）*m*4/(2*i+1)例19算法顶部伪代码描述赋初值：累加和 x=4;m=1;项数i=1；根据通用公式,x做循环累加直到 x=3.14 时中断循环输出x及i值；算法细化描述累加和 x=4;m=1;i=1；do x=x+（-1）*m*4/(2*i+1)i增加1；m=m*(-1)直到 x=3.14 时中断循环输
6、出x及i值；设计数值问题的例子20数值问题的例子void main()float x=4;int i=1,m=1;while(1)x=x+(float)(-1)*m*4/(2*i+1);i+;m=m*(-1);if (x=3.14-0.000001&x=3.14+0.000001)break;printf(i=%d,x=%fn,i,x);编程要求对任意给出的一个姓名，查找电话号码非数值问题例子1 电话号码查询客户姓名电话身份证号地址张1138*6101131980*李2152*6101131981*王1139*6101131990*张2139*6101131972*李1188*61011319
7、76*表关键字数据项关键字关键字是能唯一标识一个结点的那些数据项数据元素或结点例方法1客户姓名电话身份证号地址张1138*6101131980*李2152*6101131981*王1139*6101131990*张2139*6101131972*李1188*6101131976*王2138*6101131986*顺序结构顺序结构 顺序顺序查找查找非数值问题例子1 电话号码查询问题涉及的对象每客户及其相应的数据项；对象之间的关系数据元素顺序排列；查找指定数据项，输出相应数据项建模型设计非数值问题例子1 电话号码查询方法1顺序结构顺序结构 顺序顺序查找查找有序结构有序结构 折半查找折半查找方法2客
8、户姓名电话身份证号地址李1188*6101131976*李2152*6101131981*王1139*6101131990*王2138*6101131986*张1138*6101131980*张2139*6101131972*非数值问题例子1 电话号码查询问题涉及的对象每客户及其相应的数据项；对象之间的关系数据元素有序排列；折半查找指定数据项，输出相应数据项建模型设计非数值问题例子1 电话号码查询有序结构有序结构 折半查找折半查找方法2索引索引结构结构 分级分级查找查找客户姓名电话身份证号地址李1188*6101131976*0 x2000李2152*6101131981*张1138*6101
9、131980*0 x4000张2139*6101131972*王1139*6101131990*0 x6000王2138*6101131986*姓氏表内地址数量李0 x2000*张0 x4000*王0 x6000*索引表索引表数据表数据表方法3非数值问题例子1 电话号码查询问题涉及的对象索引表客户姓氏、对应数据表中的地址数据表每个客户及其相应的数据项；对象之间的关系索引表数据元素有序排列数据表数据元素顺序排列；建模型先索引表，后数据表设计非数值问题例子1 电话号码查询索引索引结构结构 分级分级查找查找方法328非数值问题例子1 电话号码查询 数据的组织方式和数据的存储方式，都会影响算法的效率结
10、论29在十字路口，要设置几种颜色的交通灯才可保持正常的交通秩序？BCDA十字路口交通灯管理问题非数值问题的例子2 问题涉及的对象对象之间的关系表示AC、BD不能同时通行BDAC 用 表示AC间有一条通路AC建模型某方向通行时，另外某些方向不能通行四个路口 ABCD，及相应的通路；例30AC AB AD BD BA BCCA CD CB DB DCDA BCDA“图”“数据元素”或“结点”对图中的圆圈上色，同一连线上的两个圆圈不同色且颜色种类最少设计非数值问题的例子2 31非数值问题的例子3rootbinlibuseretcmathdsswsunzhouzhaoStack.cppTree.cpp
11、Queue.cpp树“数据元素”或“结点”计算机文件系统结构的表示与管理例CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量1.3数据结构的引入问题解决信息表述信息处理计算机解题过程先找出问题中要处理的数据及数据间的联系、组织形式、存储方式、表示方法等，设计适合计算机解题的模型按要求有效地解决问题 数据结构研究的问题 经典数据结构数据表示方法数据表示方法数据存储形式数据存储形式数据运算数据运算CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前
12、分析方法算法性能的综合考量1.4 数据结构的要素1.4.11.4.11.4.21.4.2数据结构基本术语数据结构基本术语数据结构的三个要素数据结构的三个要素数据的基本单位 可包含多个数据项38基本概念和术语数据元素由某一数据对象及该对象中所有数据成员之间的关系组成数据元素中的不可分割的最小单位客观对象在计算机中的符号表示数据结构数据项数据数据结构基本术语1.4 数据结构的要素1.4.11.4.11.4.21.4.2数据结构基本术语数据结构基本术语数据结构的三个要素数据结构的三个要素数据结构 数据的逻辑结构数据的逻辑结构 体现各结点间的相邻关系，体现各结点间的相邻关系，由数据本身内在特性所决定，
13、由数据本身内在特性所决定，独立于计算机独立于计算机数据的存储结构数据的存储结构数据元素及其逻辑关系在数据元素及其逻辑关系在计算机存储器内的表示计算机存储器内的表示数据的运算数据的运算对数据施加的操作对数据施加的操作数据结构的三个要素数据结构的三个要素数据逻辑结构集合结点间无关系线性结构结点间一对一关系树形结构结点间是一对多关系图形结构结点间是多对多关系数据的逻辑结构数据的逻辑结构数据的存储结构42数据数据存储结构存储结构 顺序存储顺序存储 结点的逻辑关系由存储结点的逻辑关系由存储单元的邻接关系来体现单元的邻接关系来体现 链式存储链式存储 结点的逻辑关系由结点的逻辑关系由附加的指针字段表示附加的
14、指针字段表示 索引存储索引存储 索引项：（关键字，地址）索引项：（关键字，地址）散列存储散列存储 结点地址结点地址F（关键字）（关键字）数据的运算43数据数据运算运算运算的定义运算的定义建立在数据的逻辑结构上建立在数据的逻辑结构上运算的实现运算的实现以数据的存储结构为基础以数据的存储结构为基础常见运算：初始化 判空 求长度 查找 遍历 取值 置值 插入 删除 CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量1.5 如何设计算法1.5.11.5.11.5.21.5.2算法的定义及表示方法算法的定义及表示方
15、法算法设计与函数设计的关系算法设计与函数设计的关系1.5.31.5.31.5.41.5.4软件设计描述软件设计描述算法设计的一般步骤算法设计的一般步骤1.5 如何设计算法1.5.11.5.11.5.21.5.2算法的定义及表示方法算法的定义及表示方法算法设计与函数设计的关系算法设计与函数设计的关系1.5.31.5.31.5.41.5.4软件设计描述软件设计描述算法设计的一般步骤算法设计的一般步骤47算法 在有限步骤内求解某一问题所使用的一组定义明确的操作序列，能够在有限时间内，对一定的规范的输入获得所要求的输出。算法算法特征 1有穷性：一个算法必须保证在执行有限步骤后结束，而不是无限的。3可行
16、性：每一个操作步骤都必须在有限的时间内完成。4输入：一个算法可以有多个输入，也可以没有输入。2确定性：算法中每一条指令必须有明确的含义，而不能是含糊不清的有歧义。5输出：一个算法可以有一个或多个输出，没有输出的算法是没有实际意义的。算法的表示49可以帮助程序员开发算法的，由字符组成的非正式语言。可以引用任何具有表达力的方法来最清晰、最简洁地表达算法。伪代码本书对算法的描述采用伪代码的方式1.5 如何设计算法1.5.11.5.11.5.21.5.2算法的定义及表示方法算法的定义及表示方法算法设计与函数设计的关系算法设计与函数设计的关系1.5.31.5.31.5.41.5.4软件设计描述软件设计描
17、述算法设计的一般步骤算法设计的一般步骤long factorial(int n);有关函数的概念函数类型函数类型 函数名（形参类型说明表）函数名（形参类型说明表）声明部分；声明部分；语句部分；语句部分；函数的定义形式函数类型函数类型 函数名（形参类型说明表）函数名（形参类型说明表）;函数的声明形式函数名函数名(实参表实参表);函数的调用形式long factorial(int n)int i;long t=1;for(i=1;i=n;i+)t=t*i;return(t);int m;long c；scanf(“%d”,&m);c=factorial(m);输入的数据输入的数据输出的结果输出的结
18、果输出结果的类型输出结果的类型实际参数实际参数C函数实际参数与形式参数的关系52 函数类型函数类型 函数名（函数名（形式参数表形式参数表）声明部分声明部分;语句部分语句部分;函数定义格式函数名（函数名（实际参数表实际参数表）函数调用格式形式参数表中放参数的形式参数表中放参数的定义形式定义形式如基本变量：如基本变量：int xint x如指针：如指针：int int*ptrptr如数组：如数组：int a int a 如结构：如结构：struct node stustruct node stu实际参数表中放参数的实际参数表中放参数的使用形式使用形式如基本变量如基本变量 ：x x如指针：如指针：p
19、trptr如数组：如数组：a a如结构：如结构：stustuC函数实际参数与形式参数的关系算法设计与函数设计的关系功能描述输入信息输出信息函数名形参函数类型接口及功能描述此处输出的含义，是指函数传递给调用者的，不是输出到显示器上的此处信息输入方式是调用者传递给函数，不是通过键盘等方式输入1.5 如何设计算法1.5.11.5.11.5.21.5.2算法的定义及表示方法算法的定义及表示方法算法设计与函数设计的关系算法设计与函数设计的关系1.5.31.5.31.5.41.5.4软件设计软件设计描述描述算法设计的一般步骤算法设计的一般步骤软件设计方法55 根据问题的功能要求，按照输入数据的正常情形、边
20、界或特例情形、异常情形等各种情形，给出测试样例。测试用例设计1给出问题包含信息与信息联系的存储结构，用C语言数据类型描述。数据结构描述2根据问题的功能、输入、输出，对应确定函数类型、形参、返回值。函数结构设计3按照自顶向下逐步求精的方法，描述问题的解决步骤。算法描述4按照细化的伪代码给出代码实现，必要时按照测试样例给出测试结果。程序实现5分析问题的时间复杂度、空间复杂度。算法效率分析61.5 如何设计算法1.5.11.5.11.5.21.5.2算法的定义及表示方法算法的定义及表示方法算法设计与函数设计的关系算法设计与函数设计的关系1.5.31.5.31.5.41.5.4软件软件描述描述方法方法
21、算法设计的一般步骤算法设计的一般步骤算法设计的一般步骤571设定算法初始条件3按问题的普遍规律给出算法处理的流程4考虑临界点或特殊点的处理2确定算法的结束条件5考虑异常情况算法设计实例5858算法设计的例子 求n！递推公式 S=S*Tn!1n1step11*2=sstep2s*3=sstep3s*4=sstep4s*5=sS：累乘之积 T：乘数递推法定义例59算法设计实例 求n！功能描述输入信息输出信息factorialint nint值异常：-1正常：n！的结果测试用例设计1接口及功能描述2情形测试数据预期结果问题的一般情形n1按照n！一般定义得出的值临界点或特殊点n=0，n=1按照n！边界
22、定义得出的值异常情况nn 结束输出结果S第二步细化输入n 设S=1，乘数T=1 do S=S*T T增加1 Until (Tn)输出：S算法描述3算法设计实例 求n！61 一般情形边界值异常情形测试值51001-1测试结果120362880011-1float factorial(int n)int i;float t=1;if(n0)return(-1);for(i=1;i=n;i+)t=t*i;return(t);函数实现4测试结果562伪代码描述要点简洁明晰按程序结构特点描述算法步骤，注意格式缩进。内容完整算法开始阶段初始化信息输入信息算法处理阶段循环要素、判断条件等算法结束阶段输出信息
23、程序结构：顺序、循环、分支63n!的例子#include float factorial(int n);float factorial(int n)int i;float t=1;for(i=1;i=n;i+)t=t*i;return(t);main()float c;int m;printf(input m);scanf(%d,&m);c=factorial(m);printf(The%d!is%8.1f,m，c);函数说明函数调用函数定义CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量1.6如何评价
24、算法的优劣1.6.11.6.11.6.21.6.2算法设计的要求算法设计的要求算法效率的度量方法算法效率的度量方法1.6如何评价算法的优劣1.6.11.6.11.6.21.6.2算法设计的要求算法设计的要求算法效率的度量方法算法效率的度量方法67算法设计的要求 正确性程序不含语法错误对输入数据能得出满足要求的结果随意的数据精心选择的典型、苛刻而带有刁难性的几组数据一切合法的输入数据可读性程序员的效率第一健壮性算法对不合理数据输入应该有反应能力和处理能力高效性时间效率高效率指的是算法执行的时间（时间复杂性）；存储空间少存储量需求指算法执行过程中所需要的最大存储空间（空间复杂性）空间和时间可以互相
25、转化1.6如何评价算法的优劣1.6.11.6.11.6.21.6.2算法设计的要求算法设计的要求算法效率的度量方法算法效率的度量方法69算法性能的事后统计#include long start,stop;time(&start);/*此处放要测定运行时间的函数*/time(&stop);long runTime=stop-start;printf(%ldn ,runTime);例 硬件的速度 程序选用语言 目标代码质量 问题的规模 算法选用的策略算法效率因素 算法时间效率相关因素分析算法性能的事前分析71时间效率空间效率算法性能分析算法的时间效率分析找出与算法运行时间相关的因素与特征函数，从时
26、间角度来评价算法。算法的空间效率分析找出算法运行所需的辅助存储空间特征函数，从空间角度来评价算法。CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量 硬件的速度 程序选用语言 目标代码质量 问题的规模 算法选用的策略算法效率因素 算法时间效率相关因素分析与算法执行时间相关的因素中，哪些是关键因素？算法时间效率相关因素分析算法运行时间=算法中每条语句执行时间之和每条语句执行时间=该语句的执行次数7474语句频度将程序的运行时间表示为其输入的函数若问题的规模为n，一个算法中的语句执行次数称为语句频度或时间频度
27、，记为T(n)。1.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法1.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法
28、的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法77问题的规模与算法的策略每个卡片只看一次，共 100 次将数字1100写在卡片上，乱序后再按序排好。排序时所有卡片的查找次数是多少？先找 1、再找2、找3、最多要看(100+1)*100/2 次法一法二问题规模为n时的比较次数f(n)=n2/2+n/2问题规模为n时的比较次数 f(n)=n例78问题的规模与算法的策略结论一般地，算法所需时间是和输入规模n 同步增长的：l对于同一算法 输入量小，速度快；输入量大，速度慢。l对于不同的算法 有可能在n的某一区间，一个
29、算法的速度高于另一个；而在n的另一区间，情况可能就会相反。l对于不同的算法 规模较小时，算法效率接近；规模扩大，算法效率通常呈上升趋势，各算法之间的差距就比较明显了。791.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法81算法分析规则1234596979899 100例将数字1100写在卡
30、片上，乱序后再按序排好。排序时所有卡片的查找次数是多少？T(n)=n=100T(n)=n=100100 999897965432123614578521627789310最好最好情形情形最坏最坏情形情形平均平均情形情形T(n)=(n+1)T(n)=(n+1)*n/2=5050n/2=5050T(n)=2575T(n)=257582nnii=11（n+1）nn+1ASL=P(n-i+1)=n22n1niiiASLPC在 n 张卡片中找一个指定卡片i的平均查找次数ASLn（Average Search Length）Pi查找表中第i个记录的概率Ci找到该记录时已经比较过的卡片数在 n 张卡片中找n
31、个指定卡片i的平均查找次数ASL111(3)+.+=2224nnnnASLASLn=100时，T(n)=2575算法分析规则算法效率典型情形83最好效率：算法在最优情况下的效率最差效率：算法在最坏情况下的效率平均效率：“典型”或“随机”输入的情况下，算法具有的效率算法效率算法效率典型情形典型情形84算法的上限&下限算法运行时间慢快算法运行的时间上限算法运行的时间下限O表示法表示法 表示法同一算法算法分析是为了得知近似的执行时间，一般考察的是当问题规模n增加时，运算所需时间的上下界。85渐进表示法记号记号定义含义O定义：f(n)O(g(n)若存在两个正常数c和n0，使得当nn0时，f(n)c*g
32、(n)f(n)的渐进上限为g(n)定义：f(n)(g(n)若存在两个正常数c和n0，使得当 n n0时，f（n）c*g(n)f(n)的渐进下限为g(n)定义：f(n)(g(n)若存在正常数c1，c2和n0，使得当n n0时，c1*g(n)f(n)c2*g(n)f(n)的渐进确界为g(n)o定义：f(n)o(g(n)对任意正常数c，若存在n0，使得当n n0时，f(n)cg(n)g(n)为f(n)的非紧却渐进下界说明：说明：f(n)、g(n)均为均为非负函数非负函数 86cg(n)f(n)n0f(n)O(g(n)cg(n)f(n)n0f(n)(g(n)f(n)(g(n)Big O算法的渐进运行时
33、间记号注：注：n0、c、c1、c2均为均为正数正数n0c2g(n)f(n)c1g(n)渐进上限渐进上限渐进下限渐进下限渐进确界渐进确界大O符号（Big O notation）是用于描述函数渐近行为的数学符号。它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。87大O表示法的例子1f(n)=7*2n+n2+n=O(2n)，可以找到c=8,n0=4，使得7*2n+n2+n 8*2n f(n)=10n2+5n+1=O(n2)，可以找到c=11,n0=6，使得10n2+5n+1 11n2 f(n)=3n+2=O(n)，可找到c=4，n0=2，使得3n+2 3n+2lim=3n22n10n
34、5n1lim10nn2nn-7*2 +n+nlim=72当当 n n充分大时，该程序的运行时间和充分大时，该程序的运行时间和 n n 成正比，用成正比，用O(n)O(n)表示；称表示；称f(n)f(n)和和n n是同阶的（数量级相同）。是同阶的（数量级相同）。当当 n n充分大时，该程序的运行时间和充分大时，该程序的运行时间和n n2 2成正比，用成正比，用O(nO(n2 2)表示；称表示；称f(n)f(n)和和n n2 2是同阶的。是同阶的。当当 n n充分大时，该程序的运行时间和充分大时，该程序的运行时间和2 2n n成正比，用成正比，用O(2O(2n n)表示；称表示；称f(n)f(n)
35、和和2 2n n是同阶的。是同阶的。例1.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法91时间复杂度 如果 O(f(n)是某个算法的语句执行次数f(n)的上限，那么我们可以说此算法的渐进时间复杂度（简称时间复杂度)或是执行时间为 O(f(n)定义92矩阵相乘算法时间复杂度f(n)=O(n3
36、)程序语句程序语句 频度频度f(n)f(n)1 1for(i=1;i=n;i+)2 2 for(j=1;j=n;j+)3 3 cij=0;4 4 for(k=1;k=n;k+)5 5 cij+=aik*bkj n 阶矩阵相乘算法的时间复杂度分析（C=A*B）例 算法的时间复杂度的例子1n+1n(n+1)n2n2(n+1)n3 频度和 f(n)=2n3+3n2+2n+13233nnf(n)(2n3n21)limlim=2nnn93时间复杂度结论 算法的渐进分析，关心的是数据规模n逐步增大时资源开销T(n)的增长趋势，具体是考察数量级大小的比较。如果一个算法的最坏情况运行时间的阶要比另外一个算法的
37、低，我们就常常认为前者更为有效。结论94例程序段频度f(n)与规模n时间复杂度O(f(n)1x=x+1;y=x+2234分析下面各程序段的时间复杂度 算法的时间复杂度的例子2for(i=0;in;i+)x+;f(n)123 k f(n)i12222k-12f(n)-1i=i*2222232k2f(n)i=1;while(i=n)i=i*2;for(i=0;in;i+)for(j=0;jn;j+)x+;O(log2n)2f(n)=nO(n2)f(n)=(n+1)+n*(n+1)+n2O(n)f(n)=2n+1O(1)f(n)=2语句i=i*2执行次数最后一次最后一次执行：执行：i=n 时时 2f
38、(n)-1=n 1.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法算法时间复杂度的实际意义96查找的效率问题对于一组有序的数列（5,13,19,21,37,56,64,75,80,88,92），如何查找效率更高？数据513192137566475808892顺序查找次数12345678910
39、11折半查找次数34234134234可能的概率pi1/n1 1*2 20 02 2*2 21 13 3*2 22 2i i*2 2i-1i-1561952113h=1h=1h=2h=2h=3h=3h=logh=log2 2n+1n+1层层378064887592每层查找次数每层查找次数例顺序niii=11（1+n）nn+1ASL=pc=n22一个结点查找成功的平均次数一个结点查找成功的平均次数h(lgn)n(h-1)2+1T(n)=O=O=O(lgn)nn折折半半hh012i-1ii折半i=11(h-1)2+1ASL=pc=(1 2+22+32+.+i 2)=nn查找查找的平均时间复杂度的平
40、均时间复杂度n+1T(n)=O=O(n)2顺顺序序算法时间复杂度的实际意义98算法时间复杂度的实际意义小规模的输入在运行时间上的差别不足以将高效的算法和低效的算法区分开。时间复杂度并不表示一个程序解决问题具体需要花多少时间，而是表示当问题规模扩大后程序运行需要的时间长度增长得有多快。99对于算法分析具有重要意义的函数值c log2n n nlog2n n2 n3 2n 3n=0&Ai!=k)i-;return i;平均情形最坏情形f(n)=n O(f(n)=O(n)f(n)=(1/n)*(1+n)*n/2=(1+n)/2 O(f(n)=O(n)时间复杂度的例子基本语句的执行次数是否只和问题规模
41、有关？例103算法效率一般性分析方法非递归算法决定用哪个(些)参数作为输入规模的度量 找出算法的基本操作(作为一个规律，它总是位于算法的最内层循环)检查基本操作的执行次数是否只依赖输入规模。如它还依赖一些其他的特性，如输入顺序等，则最差效率、平均效率以及最优效率需要分别研究。建立一个算法基本操作执行次数的求和表达式递归算法用递推式的形式来表达基本操作次数决定用哪些参数作为输入规模的度量 找出算法的基本操作 检查一下，对于相同规模的不同输入，基本操作的执行次数是否不同。如果不同，则必须对最差效率、平均效率以及最优效率作单独研究 对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件 解这
42、个递推式，或者至少确定它的解的增长次数1.7 算法性能的事前分析方法1.7.11.7.11.7.21.7.2问题的规模与算法的策略问题的规模与算法的策略算法时间效率的上限与下限算法时间效率的上限与下限1.7.31.7.31.7.41.7.4渐进的上限渐进的上限算法的时间复杂度算法的时间复杂度时间复杂度的综合讨论时间复杂度的综合讨论1.7.51.7.5算法的空间效率分析方法算法的空间效率分析方法从空间角度来评价算法找出算法运行所需的辅助存储空间特征函数。105算法的空间效率分析算法空间 存储空间代码空间：算法本身的存储空间 数据空间：输入输出数据的存储空间 运行空间算法在运行过程中临时占用的存储
43、空间 106nnxaxaxaaxf.)(2210计算多项式的值算法存储空间分析的例子1-12函数结构设计功能描述输入输出计算多项式的值evaluate系数float coef float f(x)变量 float x规模 int n函数名形参函数类型例107算法存储空间分析的例子1-12顶部伪代码描述 计算函数值第一步细化先计算x的幂,存于数组中,再分别乘以相应的系数第二步细化int AN放x的幂float coefN放系数A0=1，i=1当 i n Ai=x*Ai-1;i+;f=0,i=0;当 i n f=f+coefi*Ai;i+;法一108算法存储空间分析的例子1-12算法一#defin
44、e N 100float evaluate(float coef,float x,int n)float f;int AN,i;for(A0=1,i=1;i=n;i+)Ai=x*Ai-1;/*A 放x的幂*/for(f=0,i=0;i0 f=f*x+coefi;i-；法二算法存储空间分析的例子1-12110 算法时间复杂度算法时间复杂度:O(n)空间复杂度：空间复杂度：O(1)算法二#define N 100float evaluate(float coef,float x,int n)float f;int i;for(f=coefn,i=n-1;i=0;i-)f=f*x+coefi;ret
45、urn(f);111算法的空间复杂度定义 S(n)=O(g(n)其中 n 问题规模 g(n)执行算法所需的辅助空间算法空间复杂度S(n)空间复杂度含义O(n)表示每个输入元素都分配到固定的储存空间。O(1)代表算法需要固定的储存空间，与输入量无关若所需存储量依赖于特定的输入，则通常按最坏情况考虑。例112给出fibonacci数列前n项的递归与非递归的算法，试分析它们的算法复杂度。(费氏数列fibonacci数列)fibonacci数列定义 f0=0；f1=1；fn=fn-1+fn-2 (n=2)递归的算法/*递归计算斐波那契数列的第n项*/long Fib(long n)if (n 2*T(
46、n-2)又又T(n-1)T(n-2)T(n)T(n-2)T(n)=T(n-1)+T(n-2)+1 2*2*T(n-2)2*2*2*T(n-3)2*2*T(n-4)2*2*2*T(n-6)2n/2T(n-n)=2n/2大O：渐进上限：渐进下限算法分析的综合例子1-13115Fibonacci数列通项公式fibonacci数列定义 f f0 0=0=0；f f1 1=1=1；f fn n=f=fn-1 n-1+f+fn-2 n-2 (n=2)(n=2)二阶线性递推数列的特征方程二阶线性递推数列的通项公式a=1a=1；b=-1b=-1；c=-1 c=-1 二阶线性递推数列的一般形式(2)(1)()0
47、af nbf ncf n12()nnf nxx20axbxc12152152xx=1515 1115f(n)25n求得数列第n项与n的关系Fibonacci数列通项公式1161+5T(n)(1.618)2 nn1115f(n)25nfibonacci数列定义 f f0 0=0=0；f f1 1=1=1；f fn n=f=fn-1 n-1+f+fn-2 n-2 (n=2)(n=2)T(n)=T(n-1)+T(n-2)+1117Fib函数递归算法时间复杂度分析结论T(n)(2n/2)=(1.414n)T(n)O(2n)大O O：渐进上限：渐进下限 渐进确界T(n)(1.618 n)Fib函数递归算
48、法时间复杂度分析曲线118CONTENTS从编程说起程序要处理的数据数据结构的引入数据结构的要素如何设计算法如何评价算法的优劣算法性能的事前分析方法算法性能的综合考量算法性能的综合考量120若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间时间复杂度空间复杂度逻辑复杂度若该程序使用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快速的算法；算法算法评价评价角度角度相互制约时空转换问题数据数据处理功能测试：测试样例设计数据引用：数据结构描述模块设计：函数结构设计算法设计：自顶向下逐步细化程序设计：编码算法分析：空间时间复杂度分析含义：数据元素的连接关系
49、种类：集合、线性、非线性逻辑结构存储结构运算含义：数据存储到计算机中种类：顺序、链式、索引、散列存储原则：存数值存联系；存得进取得出含义：数据处理定义：基于数据的逻辑结构实现：基于数据的存储结构本章小结本章小结本章小结 数据结构三要素是逻辑、存储与运算：逻辑结构说的是问题中的数据元素如何点点相关联；存储结构把数据值与逻辑关系存放到内存的单元；运算是由算法描述数据处理的方案。一种逻辑关系可以用多种方式来存储，“存数值且存联系”，“存得进并取得出”，存储两规则，设计存的结构时必遵循的法门无二般，存储结构不同，则算法效率有快有慢。算法效率从时间和空间两个方面看，复杂度用“大欧”的方法来估算，用的是算法的渐进上限，和运算规模n相关。122
