《数据结构第二版》由会员分享，可在线阅读，更多相关《数据结构第二版（53页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 （第二版）（第二版）严蔚敏严蔚敏 吴伟民吴伟民 清华大学出版社清华大学出版社主讲：李树主讲：李树全全 电子科技大学电子科技大学电子科技大学电子科技大学计算机学院计算机学院计算机学院计算机学院第一章第一章 绪论绪论1.1 学习学习的意义及要求的意义及要求 1.2 的主要内容的主要内容 1.3 基本术语基本术语 1.4 算法描述及分析算法描述及分析1.1 学习学习的的意义意义及要求及要求一一.意义意义1. 算法和数据结构是算法和数据结构是计算机科学计算机科学的两大支柱的两大支柱 计算机科学早期定义为计算机科学早期定义为计算机科学早期定义为计算机科学早期定义为: : 研究研究研究研
2、究算法算法算法算法的科学的科学的科学的科学 近期定义为近期定义为近期定义为近期定义为: : 研究研究研究研究数据数据数据数据的科学的科学的科学的科学1.1 学习学习的的意义意义及要求及要求2. 数据结构是程序设计的基础数据结构是程序设计的基础Program=Algorithms+Data StructureProgram=Algorithms+Data Structure数据结构数据结构数据结构数据结构是设计是设计是设计是设计OSOS、DBMSDBMS、编译等编译等编译等编译等系统程序系统程序系统程序系统程序和各种和各种和各种和各种应用程序应用程序应用程序应用程序 的重要基础的重要基础的重要基
3、础的重要基础1.1 学习学习的的意义意义及要求及要求3. 是计算机专业的一门综合性是计算机专业的一门综合性专业基础课，是一门理论与实际紧密结合专业基础课，是一门理论与实际紧密结合的基础课。的基础课。是计算机专业本科生必修学位课程是计算机专业本科生必修学位课程是计算机研究生入学考试必考科目是计算机研究生入学考试必考科目是软件人员水平考试内容是软件人员水平考试内容1.1 学习学习的的意义意义及要求及要求4. 与计算机科学技术其他相关与计算机科学技术其他相关领域的关系领域的关系数据结构数据结构问题求解问题求解算法理论算法理论数据模型数据模型设计方法设计方法描述语言描述语言1.1 学习学习的意义及的意
4、义及要求要求二二.要求要求1. 掌握各类掌握各类基本数据结构类型基本数据结构类型 和相应的和相应的存储存储结构结构2. 提高提高阅读阅读 和和编写算法编写算法 的能力的能力3. 能针对给定问题，选择相适应的数据结构，能针对给定问题，选择相适应的数据结构， 并能设计和分析算法并能设计和分析算法1.2 的主要内容的主要内容99080-3 班号班号 3202670 计算机学院办公室电话号码计算机学院办公室电话号码610054 电子科技大学邮编电子科技大学邮编 例例1：结论结论1.杂乱的数据不能表达和交流信息杂乱的数据不能表达和交流信息1.2 的主要内容的主要内容例例例例2:2: 电话号码簿电话号码簿
5、电话号码簿电话号码簿 ( (a a1 1，b b1 1) (a) (a2 2，b b2 2)(a)(an n，b bn n) )其中：其中：其中：其中： a ai i为某人姓名，为某人姓名，为某人姓名，为某人姓名，b bi i为该人的电话号码。为该人的电话号码。为该人的电话号码。为该人的电话号码。要求：设计一个算法，给定一个姓名时，要求：设计一个算法，给定一个姓名时，要求：设计一个算法，给定一个姓名时，要求：设计一个算法，给定一个姓名时， 能查出此人的电话号码。能查出此人的电话号码。能查出此人的电话号码。能查出此人的电话号码。 如果姓名和电话号码的排列次序无规律，如果姓名和电话号码的排列次序无
6、规律， 则只能逐一比较姓名进行查找则只能逐一比较姓名进行查找 如果姓名按字典顺序组织，则查找就快捷多了如果姓名按字典顺序组织，则查找就快捷多了结论结论2.数据之间是有联系的数据之间是有联系的这些联系常常影响算法的选择和效率。这些联系常常影响算法的选择和效率。 DS就是要研究数据之间的联系。就是要研究数据之间的联系。1.2 的主要内容的主要内容例3：大学学生管理机构学校学校学校学校一系八系一系八系一系八系一系八系一年级二年级三年级四年级一年级二年级三年级四年级一年级二年级三年级四年级一年级二年级三年级四年级班班班班班班班班张三李四张三李四张三李四张三李四结论结论数据之间是有结构的数据之间是有结构
7、的例中数据之间呈分层结构（树状结构）例中数据之间呈分层结构（树状结构）DS就是要研究就是要研究数据之间的各类结构数据之间的各类结构。1.2 的主要内容的主要内容例：图书目录管理例：图书目录管理设每个书目含：书名，作者，登录号，分类，出版年月设每个书目含：书名，作者，登录号，分类，出版年月设每个书目含：书名，作者，登录号，分类，出版年月设每个书目含：书名，作者，登录号，分类，出版年月对图书目录常有如下操作：对图书目录常有如下操作：对图书目录常有如下操作：对图书目录常有如下操作： 查找：某书在书库中是否存在？查找：某书在书库中是否存在？查找：某书在书库中是否存在？查找：某书在书库中是否存在？ 插入
8、：购进新书时的登录；插入：购进新书时的登录；插入：购进新书时的登录；插入：购进新书时的登录； 删除：报废或丢失的书，需从目录中去掉；删除：报废或丢失的书，需从目录中去掉；删除：报废或丢失的书，需从目录中去掉；删除：报废或丢失的书，需从目录中去掉；结论结论在某种数据结构上可定义一组运算在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算。就是要研究各类数据结构上的各种运算。1.2 的主要内容综上所述：综上所述： DS主要研究内容：主要研究内容：数据的各种逻辑结构和物理结构，以及它们数据的各种逻辑结构和物理结构，以及它们之间的相应关系；之间的相应关系；对每种结构定义相适应的各种运算
9、；对每种结构定义相适应的各种运算；设计出相应的算法；设计出相应的算法；分析算法的效率。分析算法的效率。 常见的数据结构有：数组、栈、队列、表、常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。串、树、图和文件等。数据结构与问题求解1. 在计算机中建立一个与实际问题有比较密在计算机中建立一个与实际问题有比较密切对应关系的切对应关系的模型模型；2. 计算机内部的计算机内部的数据数据 表示了需要被处理的表示了需要被处理的实际对象，包括其内在的性质和关系；实际对象，包括其内在的性质和关系；3. 处理这些数据的处理这些数据的程序程序 则模拟对象领域中则模拟对象领域中的实际过程；的实际过程；4.
10、将计算机程序的运行将计算机程序的运行结果结果 在实际领域中在实际领域中给予解释，便得到实际问题的解。给予解释，便得到实际问题的解。例1、当你到图书馆借阅书籍时，你要通过计算机检索书目信息。在书目自动检索系统中，有一张按登录号顺序排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表。计算机检索就是按某个特定要求（如给定书名）对书目文件查询。（书目文件）（书名索引）（作者索引）（分类索引）例2、酒店管理系统中的客房分配问题。酒店要求每间客房出租率相等，以保证维持一个平均磨损率。对这一问题可用数据结构中的队列来解决；将酒店所有空闲客房排成一个队列，有客人入住则从队头分配客房，客人结帐离店则
11、将空出的客房插入队尾。这样就能保证客房出租率相等。队头队尾出租队头客房客人离店，空出客房插入队尾注：例1、例2都属于线性数据结构例3、计算机和人对弈问题。计算机和人对弈是因为事先已将对奕的策略输入计算机中。对弈的过程是在一定规则下随机进行，计算机操作对象是对弈过程中可能出现的棋盘状态-称为格局。下面看一下井字棋对弈。目前我们所接触的象棋软件、围棋软件的实现原理和井字棋是一样的。此类数据结构为树型结构例4、一个城市的居民点铺设煤气管道，居民点之间的铺设费用可以估算，要求工程完工后，每个居民点都能通气，并且总的费用最少。我们用图来表示这类问题。其中图的顶点表示居民点，边上的权值表示铺设费用。814
12、29675317.564.582.545.634.544.271.564.528.555.230.475.0(A、费用核算）142935678（B、铺设方案）问题求解例子问题求解例子- -五叉路口交通管理系统设计五叉路口交通管理系统设计五叉路口交通管理系统设计五叉路口交通管理系统设计BACDE对车辆可能行驶方向进行分组，要求任一组中各个方向行驶的对车辆可能行驶方向进行分组，要求任一组中各个方向行驶的车辆可以同时安全行驶。分组越少，可同时行驶的车辆越多，车辆可以同时安全行驶。分组越少，可同时行驶的车辆越多，管理系统的质量就越高。管理系统的质量就越高。有有13个可能通行的方向：个可能通行的方向：A
13、B， AC， AD， BA， BC， BD， DA， DB， DC， EA， EB， EC， ED。交叉路口图式模型交叉路口图式模型将一种通行方向用一个结点表示将一种通行方向用一个结点表示将一种通行方向用一个结点表示将一种通行方向用一个结点表示( (椭圆椭圆椭圆椭圆) )；在不能同时行驶的结点间画一条连线；在不能同时行驶的结点间画一条连线；在不能同时行驶的结点间画一条连线；在不能同时行驶的结点间画一条连线；ABACADBCBDBADBDCDAEBECEAED问题求解：将图中结点进行分组，使有线连接的结点不在同一个组问题求解：将图中结点进行分组，使有线连接的结点不在同一个组里。要解决的问题已借助
14、图的里。要解决的问题已借助图的模型模型模型模型 清楚而严格地表达出来。余下的清楚而严格地表达出来。余下的问题是能否设计一个总能得到最佳的分组方案的问题是能否设计一个总能得到最佳的分组方案的程序程序程序程序。求解方法（求着色问题的近似解）求解方法（求着色问题的近似解）1.1. 选出未着色的结点，并用该新颜色上色；选出未着色的结点，并用该新颜色上色；选出未着色的结点，并用该新颜色上色；选出未着色的结点，并用该新颜色上色；2.2. 寻找仍未着色的结点，如果某结点与新颜色结点寻找仍未着色的结点，如果某结点与新颜色结点寻找仍未着色的结点，如果某结点与新颜色结点寻找仍未着色的结点，如果某结点与新颜色结点没
15、有边相连，则将该结点用该颜色上色。没有边相连，则将该结点用该颜色上色。没有边相连，则将该结点用该颜色上色。没有边相连，则将该结点用该颜色上色。ABACADBCBDBADBDCDAEBECEAED结果：结果：1. AB AC AD BA DC ED2. BC BD EA 3. DA DB4. EB EC问题：设有问题：设有n个正常人和个正常人和n个精神病患者要过一条河，个精神病患者要过一条河，现有一条能容纳现有一条能容纳c(c2n)个人的小船，为防止患者个人的小船，为防止患者伤害正常人，要求无论在河的哪一边，正常人的人数伤害正常人，要求无论在河的哪一边，正常人的人数不得少于患者人数（除非正常人数
16、为不得少于患者人数（除非正常人数为0）。又设每个）。又设每个人都会划船。试设计一个过河的最佳方案，即小船人都会划船。试设计一个过河的最佳方案，即小船来回次数最少的算法。来回次数最少的算法。解：解：1、模型构造：、模型构造： 用一个三元组（用一个三元组（x,y,t)表示渡河过程中的某个表示渡河过程中的某个状态。其中，状态。其中，x表示起始岸上正常人的人数，表示起始岸上正常人的人数，y表表示起始岸上患者人数，示起始岸上患者人数，t表示小船的位置，即：表示小船的位置，即：T=1 表示小船在起始岸边表示小船在起始岸边 0 表示小船在目的岸边表示小船在目的岸边2、再构造一个图，图中的每一个顶点表示一个合
17、、再构造一个图，图中的每一个顶点表示一个合法状态。合法状态所对应的三元组（法状态。合法状态所对应的三元组（x,y,t)必须满必须满足：足：x=0 或或 x=n 或或 x=y.于是，渡河方案的求解就转换成一个图的搜索问题于是，渡河方案的求解就转换成一个图的搜索问题找出从起始顶点（找出从起始顶点（n,n,1)到目的顶点到目的顶点(0,0,0)的一的一条包含边数最少的通路。若该通路不存在，表明该条包含边数最少的通路。若该通路不存在，表明该问题无解。问题无解。3、例如，当、例如，当n=2,c=2时，各合法状态及其间的变时，各合法状态及其间的变换如图：换如图：（2，2，1）（0，2，0）（2，0，0）（
18、1，1，0）（2，1，0）（2，1，1）（0，1，0）（0，2，1）（1，1，1）（0，0，0）1. 基本术语基本术语 数据数据数据数据（Data)Data)：所有能被所有能被所有能被所有能被计算机处理计算机处理计算机处理计算机处理的的的的符号符号符号符号的集合。的集合。的集合。的集合。 数据元素数据元素数据元素数据元素（Data ElementData Element）：）：）：）：是数据这个集合中的是数据这个集合中的是数据这个集合中的是数据这个集合中的一个个体。一个个体。一个个体。一个个体。 设给定数据集合为：设给定数据集合为：设给定数据集合为：设给定数据集合为：D=dD=d1 1，d d
19、2 2，d dn n 则则则则d di i属于属于属于属于D D，并称并称并称并称d di i为为为为数据元素。数据元素。数据元素。数据元素。 数据项数据项数据项数据项（Data ItemData Item）：）：）：）：数据元素常常还可分为若干数据元素常常还可分为若干数据元素常常还可分为若干数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。个数据项，数据项是数据具有意义的最小单位。个数据项，数据项是数据具有意义的最小单位。个数据项，数据项是数据具有意义的最小单位。1. 基本术语基本术语数据对象数据对象（Data Object）: 具有相同特性的具有相同特性的数据元素的集合。数
20、据元素的集合。例如：数据集合例如：数据集合D=0，1，A，B，Z则：则：数据对象正整数数据对象正整数N 0，1，数据对象字母数据对象字母C A，B，Z 数据元素是数据的一个个体，数据元素是数据的一个个体，数据对象是数据的一个子集。数据对象是数据的一个子集。集合线性结构树型结构图型结构基本概念和术语1. 基本术语基本术语数据结构数据结构（Data Structure）：）：是带有结构是带有结构的数据元素的集合。的数据元素的集合。所谓结构就是数据元素之间的关系，即描述数据元所谓结构就是数据元素之间的关系，即描述数据元所谓结构就是数据元素之间的关系，即描述数据元所谓结构就是数据元素之间的关系，即描述
21、数据元素之间的运算及运算规则。素之间的运算及运算规则。素之间的运算及运算规则。素之间的运算及运算规则。用集合的形式描述，数据结构是一个二元组：用集合的形式描述，数据结构是一个二元组：用集合的形式描述，数据结构是一个二元组：用集合的形式描述，数据结构是一个二元组：DS=(DDS=(D，R)R) 其中：其中：其中：其中：D D是数据元素的集合，是数据元素的集合，是数据元素的集合，是数据元素的集合，R R是是是是D D上上上上关系的集合。关系的集合。关系的集合。关系的集合。 简言之，数据元素和其相互关系称为数据结构简言之，数据元素和其相互关系称为数据结构简言之，数据元素和其相互关系称为数据结构简言之
22、，数据元素和其相互关系称为数据结构基本概念和术语数据结构的形式定义：DATA_STRUCTURE=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集例6、复数的数据结构为：COMPLEX=(C,R)其中：C是含两个实数的集合C1,C2；R=P,P是定义在集合C上的一种关系，其中有序偶表示C1是复数的实部，C2是复数的虚部。基本概念和术语例、假设学校的每个课题小组由一位教师，一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至二名本科生。则定义如下数据结构：GROUP=(P,R)其中：P=T,G1, .,Gn,S11,.,Snm 1n3,1m2
23、 R=R1,R2 R1=|1in,1n3 R2=|1in,1jm,1n3,1m2上述数据结构的定义仅是对操作对象的一种数学描述，其中的关系描述的是数据元素间的逻辑关系，又称数据的逻辑结构。1. 基本术语基本术语逻辑结构逻辑结构（Logical Structure）：）：指数据元素之间的结构关系。指数据元素之间的结构关系。物理结构物理结构（Physical Structure）：）：指数据结构在机内的表示，也称为存储结构。指数据结构在机内的表示，也称为存储结构。基本概念和术语假设用两个字长的位串表示一个实数，则可用地址相邻的四个字串表示一个复数。下图（A）表示复数和Z2=-0.7+4.8i的顺序
24、存储结构；图（B）表示复数Z1的链式存储结构，其中实部和虚部之间的关系用值为“0415”的指针来表示3.0-2.3-0.74.80300030206320634(A)-2.33.00415041506110613(B)1. 算法算法描述和算法分析描述和算法分析一一算法算法（Algorithm）算法概念：算法是一个有限的指令集，算法概念：算法是一个有限的指令集， 遵循指令流可以完成特定的功能。遵循指令流可以完成特定的功能。算法基本特性： 有穷性：算法经有限步后结束； 确定性：下一步必须是明确的； 可行性：每一步是可执行的；例：试说明下述过程是否是一个算法：例：试说明下述过程是否是一个算法：1、开
25、始；、开始；2、n=0;3、n:=n+1;4、重复重复3；5、结束。、结束。例：试说明下述不超过例：试说明下述不超过100万次的计数过程是一个算法：万次的计数过程是一个算法：1、开始；、开始；2、n=0;3、n:=n+1;4、若若n=106,则顺次执行则顺次执行5，否则重复，否则重复3；5、结束。、结束。1. 算法算法描述和算法分析描述和算法分析算法与程序的区别算法与程序的区别 算法算法算法算法 是解决问题的一种方法或一个过程，考虑如何将是解决问题的一种方法或一个过程，考虑如何将是解决问题的一种方法或一个过程，考虑如何将是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多
26、种算法。输入转换成输出，一个问题可以有多种算法。输入转换成输出，一个问题可以有多种算法。输入转换成输出，一个问题可以有多种算法。 程序程序程序程序 是用某种程序设计语言对算法的具体实现。是用某种程序设计语言对算法的具体实现。是用某种程序设计语言对算法的具体实现。是用某种程序设计语言对算法的具体实现。主要区别在：主要区别在：有穷性有穷性 和和描述方法描述方法 程序可以是无穷的，例如程序可以是无穷的，例如OS，算法是有穷的；算法是有穷的； 程序是用程序设计语言描述，在机器上可以执行；程序是用程序设计语言描述，在机器上可以执行； 算法还可以用框图、自然语言等方式描述。算法还可以用框图、自然语言等方式
27、描述。算法及其评价 评价一个算法一般从四个方面进行：正确性、运评价一个算法一般从四个方面进行：正确性、运行时间、占用空间和简单性。行时间、占用空间和简单性。 运行时间用时间复杂度来衡量。所谓时间复杂度运行时间用时间复杂度来衡量。所谓时间复杂度是指算法中包含的简单操作次数，一般只计算相是指算法中包含的简单操作次数，一般只计算相应的数量级：应的数量级：O(1),O(log2O(1),O(log2n n),O(n),O(n),O(n),O(n2 2) )等。等。 常用时间复杂度常用时间复杂度有如下关系：有如下关系：O(1) O(log2n) O(n) O(nlog2n) O(n2) . O(n k)
28、 O(2n)1. 算法描述算法描述和算法分析和算法分析二算法描述语言二算法描述语言类类Pascal为了便于理解掌握算法的思想和实质，本为了便于理解掌握算法的思想和实质，本课程采用类课程采用类Pascal语言语言来描述各种算法。来描述各种算法。所有的算法均以过程或函数的形式表示；所有的算法均以过程或函数的形式表示；PROC过程过程名名 (参数参数表表)；算法说明算法说明语句组语句组ENDP； 过程过程名名1. 算法描述算法描述和算法分析和算法分析 FUNC 函数名函数名 (参数参数表表)：类型；：类型；函数说明函数说明语句组语句组 RETURN(f)ENDF； 函数名函数名调用过程语句为：过程名
29、（调用过程语句为：过程名（参数参数表）表）调用函数语句为：变量名：函数名（调用函数语句为：变量名：函数名（参数参数表）表）1. 算法描述算法描述和算法分析和算法分析出错语句：出错语句：ERROR（出错信息出错信息）；）；注释语句：注释内容注释语句：注释内容语句结束符号：；语句结束符号：；语句组符号：语句组符号：基本函数：基本函数：max()、min()、 abs() 、eof 、eoln布尔运算：布尔运算：AND、OR、NOT、CAND、COR1. 算法描述算法描述和算法分析和算法分析赋值语句：变量名：表达式；赋值语句：变量名：表达式；分支语句：分支语句：IF 条件条件 THEN 语句语句EL
30、SE语语句；句；CASE 条件：语句；条件：语句；条件条件n ： 语句语句n； (ELSE 语句语句n+1) ENDC；1. 算法描述算法描述和算法分析和算法分析循环语句：循环语句：FOR FOR 变量名：初值变量名：初值变量名：初值变量名：初值 TOTO 终值终值终值终值 DO DO 循环体；循环体；循环体；循环体；FOR FOR 变量名：初值变量名：初值变量名：初值变量名：初值 DOWNTODOWNTO 终值终值终值终值 DO DO 循环体；循环体；循环体；循环体；WHILE WHILE 条件条件条件条件 DO DO 循环体；循环体；循环体；循环体；REPEAT REPEAT 循环体循环体
31、循环体循环体 UNTIL UNTIL 条件；条件；条件；条件；标准输入输出过程：标准输入输出过程：read（变量表）；变量表）； write（变量表）；变量表）；1. 算法描述和算法描述和算法分析算法分析三算法分析三算法分析如何衡量一个如何衡量一个正确算法正确算法的好坏？的好坏？衡量的三个尺度：衡量的三个尺度：运行所花费的时间（算法的时间特性）；运行所花费的时间（算法的时间特性）；所占用存储空间的大小（算法的空间特性）；所占用存储空间的大小（算法的空间特性）；其他（可读性、易调性、健壮性等）。其他（可读性、易调性、健壮性等）。时间和空间特性的巨大改进源于更好的数据时间和空间特性的巨大改进源于更
32、好的数据结构或算法。结构或算法。1. 算法描述和算法描述和算法分析算法分析语句频度语句频度（Frequency Count）：）：语句可能重复执行的最大次数。语句可能重复执行的最大次数。语句可能重复执行的最大次数。语句可能重复执行的最大次数。时间复杂度时间复杂度（Time Complexity）：）：设算法中所有语句的语句频度为设算法中所有语句的语句频度为设算法中所有语句的语句频度为设算法中所有语句的语句频度为t(n)t(n)，f(n)f(n)是当是当是当是当n n趋向无穷大时与趋向无穷大时与趋向无穷大时与趋向无穷大时与t(n)t(n)为同阶无穷大，为同阶无穷大，为同阶无穷大，为同阶无穷大，则
33、算法的时间复杂度则算法的时间复杂度则算法的时间复杂度则算法的时间复杂度T(n)=O(f(n)T(n)=O(f(n)其中：其中：其中：其中：n n为算法计算量或称为规模（为算法计算量或称为规模（为算法计算量或称为规模（为算法计算量或称为规模（sizesize）；）；）；）； f(n) f(n)是运算时间随是运算时间随是运算时间随是运算时间随n n增大时增大时增大时增大时的增长率；的增长率；的增长率；的增长率； O(f(n)O(f(n)是是是是算法时间特性的量度。算法时间特性的量度。算法时间特性的量度。算法时间特性的量度。1. 算法描述和算法描述和算法分析算法分析例例例例：程序段程序段程序段程序段
34、 语句频度语句频度语句频度语句频度 时间复杂度时间复杂度时间复杂度时间复杂度1. 1. x:=x+1x:=x+1； 1 O(1) 1 O(1) 常数阶常数阶常数阶常数阶2. 2. FOR i:=1 TO n DO x:=x+1FOR i:=1 TO n DO x:=x+1； n O(n) n O(n) 线性阶线性阶线性阶线性阶3. 3. FOR i:=1 TO n DO nFOR i:=1 TO n DO n FOR j:= 1 TO n DO x:=x+1 FOR j:= 1 TO n DO x:=x+1； n2 O(n n2 O(n2 2) ) 平方阶平方阶平方阶平方阶算法及其评价例8、计
35、算下面程序的时间复杂度：For i:=1 to (n-1) do y:=y+1; for j:=0 to (2 * n) do x:=x+1; 其中语句的频度是n-1,语句的频度是(n-1)*(2n+1)=2n2-n-1,则该程序段的时间复杂度T(n)=O(n2)算法及其评价例9、计算下面程序的时间复杂度: i:=1; while (in) do i:=i*2; 语句频度是1，语句频度是f(n),则有：2f(n) n f(n) log2n,取最大值f(n)=log2n该段程序的时间复杂度T(n)=O(log2n)算法及其评价 例例1010、计算下面程序的时间复杂度、计算下面程序的时间复杂度:
36、:A:=0;b:=1; for(i:=2;in;i+) s:=a+b; b:=a; a:=s; T(n)=2+3*(n-1)=3n-1=O(n)算法及其评价 例例1111、计算下面程序中、计算下面程序中order()order()的时间复杂度的时间复杂度: : a=2,5,1,7,9,3,6,8order(int j,int m) int i,temp; if(jm) for(i=j+1;im;i+) if(ai1) 0 (n=1)求解过程：T(n)=T(n-2)+(n-2)+(n-1) =T(n-3)+(n-3)+(n-2)+(n-1) =. =(T(1)+1)+2.+n-1 =0+1+2.
37、+n-1 =n(n-1)/2=O(n2)算法与时间复杂性的关系算法与时间复杂性的关系设：设：设：设：A1A1，A2A2和和和和A3A3是是是是求解同一问题的不同算法，其时间求解同一问题的不同算法，其时间求解同一问题的不同算法，其时间求解同一问题的不同算法，其时间复杂度分别为：复杂度分别为：复杂度分别为：复杂度分别为：O(n)O(n)，O(nlogn)O(nlogn)，O(N!)O(N!)。C1C1和和和和C2C2为为为为计算机，且计算机，且计算机，且计算机，且C2C2的的的的计算速度是计算速度是计算速度是计算速度是C1C1的的的的1010倍。倍。倍。倍。复杂度复杂度复杂度复杂度 C1C1可解规
38、模可解规模可解规模可解规模 C2C2可解规模可解规模可解规模可解规模 可解规模的关系可解规模的关系可解规模的关系可解规模的关系O(n)O(n) N11 N21 N21=10N11 N11 N21 N21=10N11O(nlogn) N12 N22 N22=10N12O(nlogn) N12 N22 N22=10N12O(N!)O(N!) N13 N23 N23=N13+ N13 N23 N23=N13+小常数小常数小常数小常数不必追求高效算法，低效算法可由高速计算机来弥不必追求高效算法，低效算法可由高速计算机来弥补的看法是错误的。补的看法是错误的。第一章第一章 小结小结数据结构概念数据结构概念
39、算法时间复杂度算法时间复杂度作业作业1、设有数据结构、设有数据结构(D,R),其中其中D=(e1,e2,e3,E4,e5,e6,e7),R=r,r=(e1,e2),(e1,e7),(e2,e3),(e2,e4),(e3,e5),(e4,e5),(e2,e6),(e5,e6),(e6,e7).试按图论中图的画法惯例画出试按图论中图的画法惯例画出该数据结构图。该数据结构图。作业作业2、已知、已知6个队个队A,B,C,D,E和和F进行球赛，已经进行球赛，已经比赛过的场次有比赛过的场次有A同同B,C，B同同D,F，E同同C,F.设每个设每个队每周比赛一次，试给出一种调度算法，使得所有队每周比赛一次，试
40、给出一种调度算法，使得所有的队能在最短的时间内相互之间比赛完。的队能在最短的时间内相互之间比赛完。作业作业3 计算计算n!的递归函数的递归函数fac(n)如下，试分析它的如下，试分析它的运行时间。运行时间。Function fac(n:integer):integer; begin (1) if n=1 then (2) fac:=1 else (3) fac:=n*fac(n-1)End; 作业作业4：试编写算法求一元多项式：试编写算法求一元多项式Pn=(aixi)(0In)的值的值Pn(x0).注意本题中的输入为注意本题中的输入为ai,I=0,1,n,x0和和n,输出量为输出量为pn(x0)
