第1章数据结构PPT讲稿.ppt

《第1章数据结构PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第1章数据结构PPT讲稿.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第1章数据结构第1页，共51页，编辑于2022年，星期日课程介绍1.为什么要学习数据结构？2.该课程的主要内容是什么？如何学习？3.考核方式？总成绩=平时（30%）+期末（70%）平时=上机实习+平时作业+上课回答问题4.教材：殷人昆，数据结构（面向对象方法与C+语言描述）（第2版）清华大学出版社1.为什么要学习数据结构？2.该课程的主要内容是什么？数据结构=数据+结构（关系）第2页，共51页，编辑于2022年，星期日数据结构数据（的集合）结构物理结构逻辑结构线性结构树结构图结构集合连续非连续顺序表链表顺序存储链式存储邻接矩阵存储邻接表存储顺序存储链式存储第3页，共51页，编辑于2022年，星

2、期日如何学习？1.预习：粗读教材，发现问题2.听课：重点、难点，初步解决问题3.复习：细读教材，解决问题（理解抽象数据类型、看懂C+类的定义和实现）4.做题：巩固知识（C+类的定义和实现）5.实习：验证（调试程序）第4页，共51页，编辑于2022年，星期日上机实习作业：1.顺序表及其应用2.链表及其应用.doc3.栈及其应用4.队列及其应用5.稀疏矩阵及其基本操作6.二叉树及其基本操作7.堆及其基本操作8.Huffman树及其基本操作9.图及其基本操作第5页，共51页，编辑于2022年，星期日第一章第一章 绪论绪论内容提要：内容提要：本章主要介绍本章主要介绍数据结构的基本概念、数据结构的基本概

3、念、术语术语，以及有关，以及有关算法的描述、分析算法的描述、分析的基本的基本常识。常识。第6页，共51页，编辑于2022年，星期日第一章 绪论1.1 数据结构的概念1.1.1 为什么要讨论数据结构？为什么要讨论数据结构？同时出现了如下一些变化：同时出现了如下一些变化：计算机科学是研究信息表示信息表示和信息处理信息处理的科学；信息信息是当今社会的重要资源；计算机产业及计算机科学技术飞速发展，计算机的硬件技术和软件技术都有了极大的发展，计算机应用也已经渗透到了社会的各个领域。计算机由最初的单一科学计算到几乎无所不能；计算机由最初的单一科学计算到几乎无所不能；加工处理的对象由数值型变为数值型和非数值

4、型；加工处理的对象由数值型变为数值型和非数值型；处理的数据量由小变为大、巨大（海量存储、计算）；处理的数据量由小变为大、巨大（海量存储、计算）；数据之间的关系由简单变复杂、很复杂；数据之间的关系由简单变复杂、很复杂；通过前面的学习，我们知道：通过前面的学习，我们知道：第7页，共51页，编辑于2022年，星期日第一章 绪论思路思路2：将一“大堆杂乱无章大堆杂乱无章”的数据交给计算机处理是很不明智的，结果是加工处理的效率会非常低，有时甚至根本无法进行。于是：于是：人们开始考虑如何更有效地描述、表示、处理数据的问题，除了不断提高计算机技术外（其它课程），很重要的一个方面是通过研究、分析问题数据本身本

5、身的特点，利用这些特点提高数据表示和处理的效率。这就是数据结构这就是数据结构 下面举几个例子，目的是加深对数据结构的理解，从中也下面举几个例子，目的是加深对数据结构的理解，从中也可以看出研究数据结构的重要性！可以看出研究数据结构的重要性！信息的表示和组织形式直接影响到数据处理的效率！信息的表示和组织形式直接影响到数据处理的效率！解决思路解决思路1：发展硬件技术，开发出更快、更高级的硬件产品，但有没：发展硬件技术，开发出更快、更高级的硬件产品，但有没有其它途径呢？有其它途径呢？1.1 数据结构的概念第8页，共51页，编辑于2022年，星期日例1 书目自动检索系统登录号：书名：作者名：分类号：出版

6、单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表第9页，共51页，编辑于2022年，星期日例1 书目自动检索系统 问题：问题：图书管理，完成书目的自动检索。数据数据：一本本书籍，更确切地说是每本书的信息，如：书名、作者、出版社、出版日期、书号、内容提要等等。操作：操作：书目检索、入库、借书、还书等。涉及到：涉及到：书目数据逻辑组织、存储方法；检索、入库等操作实现算法。第10页，共51页，编辑于2022年，星期日例2 人机对奕问题(井字棋)树.第11页，共51页，编辑于2022年，星期日例2 人机对奕问题 问题：问题：人机对弈，即人与计算机下棋。数据：数据：各种棋局状态，

7、确切说就是描述棋盘格局的信息。操作：操作：走棋，即选择一种策略使棋局状态发生变化（由一个格局派生出另一个格局）涉及到：涉及到：“格局”数据逻辑组织、存储方法；走棋操作实现算法。第12页，共51页，编辑于2022年，星期日例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图第13页，共51页，编辑于2022年，星期日例3 多叉路口交通灯管理问题 问题：问题：多叉路口的交通灯管理，即在多叉路口应怎样设置交通灯，以保证交通畅通。数据：数据：路口各条道路的信息 操作：操作：设置信号灯（求出各个可以同时通行的路的集合）涉及到：涉及到：路口各条道路信息数据及其关系的

8、逻辑组织、存储方法；信号灯设置的操作实现算法。第14页，共51页，编辑于2022年，星期日第一章 绪论1.1 数据结构的概念数据对象数据对象 Data Object具有相同性质的数据成员（数据元素）的集合，是数据的子集。结构结构 Structure 数据元素之间的关系(Relation)。数据结构数据结构 Data Structure 由一个数据对象以及该对象中的所有数据元素之间的关系组成，即带结构的数据元素的集合。数据项数据项 Data Item 构成数据元素的成份，是数据不可分割的最小单位。1.1.2 数据结构及其术语数据结构及其术语数据数据 Data 用于描述客观事物的数值、字符等一切可

9、以输可以输入到计算机入到计算机中,并由计算机加工处理计算机加工处理的符号集合。数据元素数据元素 Data Element 表示一个事物的一组数据称作一个数据元素。如学生信息可包括：学号、姓名、性别等。第15页，共51页，编辑于2022年，星期日第一章 绪论数据结构数据结构=数据数据+结构结构 记作记作 Data_Structure=(D,R)其中：其中：Data_Structure是数据结构的名称是数据结构的名称 D是数据元素的有限集合（一般为一个数据对象）是数据元素的有限集合（一般为一个数据对象）R是是D上关系的有限集上关系的有限集注：这里说的数据元素之间的关系是指元素之间本身固有的逻辑注：

10、这里说的数据元素之间的关系是指元素之间本身固有的逻辑关系，与计算机无关。关系，与计算机无关。因此又称为：数据的因此又称为：数据的逻辑结构逻辑结构1.1 数据结构的概念 我们研究数据结构的目的是要利用数据之间的关系（结构），因此，我们研究数据结构的目的是要利用数据之间的关系（结构），因此，在存储时既要存储在存储时既要存储数据数据本身，还要存储本身，还要存储关系关系！第16页，共51页，编辑于2022年，星期日第一章 绪论数据在计算机中的存储：数据在计算机中的存储：两种形式两种形式 连续：连续：数据元素逐个连续存放（通过物理相邻来表示关系）非连续：非连续：数据元素不连续存放（如何表示关系？）数据的

11、存储结构数据的存储结构：是数据结构在计算机内的表示，它包括数据：是数据结构在计算机内的表示，它包括数据元素的表示和关系的表示。元素的表示和关系的表示。这样：一个数据结构要存放，一方面一方面要把数据元素存起来要把数据元素存起来，另一方面，还必须把数据元素之间的逻辑关系也表示出来还必须把数据元素之间的逻辑关系也表示出来，那么：要么用数据元素在物理上的相邻来表示逻辑关系用数据元素在物理上的相邻来表示逻辑关系 要么用数据元素的存储地址、索引表、散列函数来表示逻辑关系用数据元素的存储地址、索引表、散列函数来表示逻辑关系顺序存储结构链式存储、索引存储、散列存储1.1 数据结构的概念第17页，共51页，编辑

12、于2022年，星期日第一章 绪论1.2.1 数据类型数据类型 Data Type 一个值的集合值的集合和定义在这个值集上的一组操作一组操作的总称。（1）高级语言中的数据类型实际上包括：数据的逻辑结构逻辑结构、数据的存储结构存储结构及所定义的操作操作的实现。（2）高级语言中的数据类型按值的不同特性分为：原子类型原子类型（如整型、实型、字符型、布尔型）结构类型结构类型（由原子类型按照一定的规则构造而成，如数组、结构体）（3）数据类型逻辑概念与其在计算机程序中的实现有很重要的区别，例如线性表数据类型有两种传统的实现方式：基于数组的顺序表示顺序表示和基于链表的链式表示链式表示；（4）我们可以撇开计算机

13、不考虑，现实中的任何一个问题都可以 定义为一个数据类型称为抽象数据类型。抽象数据类型。1.2 数据结构的抽象形式第18页，共51页，编辑于2022年，星期日第一章 绪论1.2.2 抽象数据类型抽象数据类型（Abstract Data Type 简写：简写：ADT）一个数学模型数学模型及定义在这个模型上的一组操作（或运算）一组操作（或运算）的总称。抽象：抽象：抽象的本质是抽取反映问题本质的东西，舍去复杂系统中非本质的细节。使设计者可以从抽象的概念出发，从整体上考虑。在思考一个复在思考一个复杂问题问题的的解决方案解决方案时，首先，首先应考考虑将它将它抽象抽象简化，否化，否则很很难理解或者理解或者实

14、现它它！1.2 数据结构的抽象形式说明：抽象数据类型通常是指由用户定义，用以表示应用问题的数学模型，由基本的数据类型组成，并包括一组相关的服务。第19页，共51页，编辑于2022年，星期日第一章 绪论1.2 数据结构的抽象形式抽象数据类型=数学模型+操作 (其它教材上对ADT的描述)=数据结构+操作 =数据+结构+操作 它是一种描述用户和数据之间接口的抽象模型，亦即它给出了一种用户自定义的数据类型。三元组表示：（三元组表示：（D，R，P）其中其中D是数据对象，是数据对象，R是是D上的关系集，上的关系集，P是对是对D的基本操作集。的基本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据

15、对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名抽象数据类型的作用：抽象数据类型可以使我们更容易描述现实世界。抽象数据类型的作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树描述棋局关系等。例：用线性表描述学生成绩表，用树描述棋局关系等。第20页，共51页，编辑于2022年，星期日内容回顾:1.数据结构=数据+结构=(D,R)2.结构包括:逻辑结构:集合、线性、树型、图物理结构(存储结构):连续、非连续3.数据类型：（D,R,P）4.抽象数据类型：（D,R,P）区别？第21页，共51页，编辑于2022年，星期日第一章 绪论1.3

16、作为ADT的C+类1.3.1 面向对象的概念面向对象面向对象=对象类继承通信对象类继承通信对象：在应用问题中出现的各种实体、事件、规格说明等。由一组属性值和在这组值上的一组服务（或称操作）构成。类(class)，实例(instance)具有相同属性和服务的对象归于同一类，形成类。类中的一个对象为该类的一个实例。第22页，共51页，编辑于2022年，星期日继承：是面向对象方法最有特色的方面。派生类：载重车，轿车，摩托车，子类、特化类(特殊化类)基类：车辆 父类、超类、泛化类(一般化类)各派生类中的公共部分，包括属性和服务，集中到基类中，派生类中只保留自己特有的属性和服务。这样减少了数据的存储和程

17、序代码的重复。通信 各个类的对象间通过消息传递进行通信。消息：一个类的对象要求另一个类的对象执行某个服务的指令，必要时还要传递调用参数。第23页，共51页，编辑于2022年，星期日第一章 绪论 传统的大型传统的大型结构化程序设计是结构化程序设计是面向过程的，首先着眼于系统要面向过程的，首先着眼于系统要实现的实现的功能功能。一个数据结构可能被多个过程调用，修改数据结构，。一个数据结构可能被多个过程调用，修改数据结构，意味着必须修改相关的过程，这样做烦琐又容易产生错误。意味着必须修改相关的过程，这样做烦琐又容易产生错误。面向对象程序设计（面向对象程序设计（Object-Oriented Progr

18、aming,OOP）程序围绕）程序围绕被操作的数据来设计，被操作的数据来设计，“类类”作为构造程序的基本单位。作为构造程序的基本单位。“类类”具有封装、数据抽象、继承和多态等特点！具有封装、数据抽象、继承和多态等特点！1.3 作为ADT的C+类第24页，共51页，编辑于2022年，星期日第一章 绪论1.3.2 C+中的类中的类例例1：计算圆的周长和面积：计算圆的周长和面积 圆是平面上与圆心等距离的所有点的集合。从图形显示角度看，圆的抽象数据类型包括圆心和半径；而从计量角度看，它所需要的抽象数据类型只需半径即可。如果从计量角度来给出圆的抽象数据类型，那么它的数据取值范围应为半径的取值范围，即为非

19、负实数，而它的操作形式为确定圆的半径（赋值）；求圆的面积；求圆的周长。1.3 作为ADT的C+类第25页，共51页，编辑于2022年，星期日第一章 绪论问题描述：问题描述：给定圆的半径，求其周长和面积ADT定义：定义：ADT circle data:0 r,实数 structure:NULL operations:area 计算面积 s=r2 circumference 计算周长 l=2r END ADT 1.3 作为ADT的C+类第26页，共51页，编辑于2022年，星期日第一章 绪论例例2：掷色子游戏。：掷色子游戏。问题描述：问题描述：每次掷出N个色子，统计每个色子的点数和每次的总 点数，

20、看看谁的高。问题分析：问题分析：该问题的数据包括色子数、每个色子的点数和总点数，色子数是大于0的整数N；每个色子的点数是1-6；总点数是N6N；该问题的操作包括掷色子、输出各个色子的点数、求总点数。ADT定义：定义：ADT dice data:N 色子数；K1,K2Kn 每个色子的点数 S 总点数 structure:N S 6N,S=K1+K2+KN,1Ki 6 operations:toss 掷色子 displaytoss 显示每个色子的点数 total 计算总点数 END ADT1.3 作为ADT的C+类第27页，共51页，编辑于2022年，星期日第一章 绪论例例3：复数的运算：复数的运

21、算问题描述：问题描述：在高级语言中，没有复数类型，但是我们可以借助已 有的数据类型解决复数类型的问题，如复数运算。ADT定义：定义：ADT complex data:c1,c2 c1,c2均为实数 structure:z=c1+c2i operations:create(z,x,y)生成一复数 add(z1,z2,s)复数加法 subtract(z1,z2,difference)复数减法 multiply(z1,z2,product)复数乘法 get_realpart(z)求实部 get_imagpart(z)求虚部 printc(z)输出一复数 END ADT 1.3 作为ADT的C+类第2

22、8页，共51页，编辑于2022年，星期日第一章 绪论 C+对于面向对象程序设计的支持，核心部分就是类的定义，类的定义体现了抽象数据类型的思想：说明与实现的分离信息隐蔽1.3.2 C+中的类对类的成员规定三级存取：公共（public）:其它类的对象或操作可访问，构成类的接口 私有（private）：只能该类的对象和成员函数及友元访问 保护（protected）：除了具有私有成员的特性，允许该类的派生类访问第29页，共51页，编辑于2022年，星期日第一章 绪论1.4 算法定义1.1.算法的定义和特性算法的定义和特性算算法法（Algorithm）：算算法法是是解解决决某某一一特特定定任任务务的的指

23、令的有限序列指令的有限序列。算法具有以下五个特性：算法具有以下五个特性：（1）有有穷穷性性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确确定定性性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。第30页，共51页，编辑于2022年，星期日（3）可行性可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出输出 一个算法有一个或多个输出，这些输出是同输入有特定关系的量。第一章 绪论1.4 算法定义第31页，共51页

24、，编辑于2022年，星期日第一章 绪论2.算法与数据结构的关系算法与数据结构的关系算法算法+数据结构数据结构=程序程序 在计算机解决问题的过程中算法与数据结构是缺一不可的两个方面：问题的数据组织数据结构 数据的处理算法 算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。1.4 算法定义第32页，共51页，编辑于2022年，星期日怎样才能设计一个好的算法呢？要设计一个好的算法通常要考虑以下的要求:正确：算法的执行结果应当满足预先规定的功能和性能要求。可读：一个算法应当思路清晰、层次分明

25、、简单明了、易读易懂。健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果。高效：有效使用存储空间和有较高的时间效率。第33页，共51页，编辑于2022年，星期日第一章 绪论1.5.1 算法的描述1.自然语言描述：容易，但有时罗嗦、有二义性2.图示（流程图、N-S图、PAD图等）：直观清晰，但不易实现4.算法语言（伪代码）算法语言（伪代码）：严谨、简洁，易程序实现3.程序设计语言：可以直接运行，但太严格。1.5 算法的性能分析与度量 为了解决理解与执行这两者之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言

26、中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。第34页，共51页，编辑于2022年，星期日第一章 绪论 我们可以从一个算法的时间复杂度时间复杂度与空间复杂度空间复杂度来评价算法的优劣。一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：硬件的速度。例如使用486机还是使用586机。书写程序的语言。实现语言的级别越高，其执行效率就越低。编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。问题的规模。例如，求100以内的素数与求1000以内的素数其

27、执行时间必然是不同的。1.5 算法的性能分析与度量如何评价算法的优劣呢？如何评价算法的优劣呢？第35页，共51页，编辑于2022年，星期日第一章 绪论 显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模问题的规模（通常用正整数n表示），或者说它是问题规模的函数。1.5 算法的性能分析与度量算法效率的度量分为：事前估计、后期测试。第36页，共51页，编辑于2022年，星期日第一章 绪论先验估计（事前估计）：根据算法

28、的逻辑特征（基本操作的 次数）来估算。后期测试（事后计算）：选择样本数据、运行环境，运行算法 计算出空间、时间。优点：可比性强缺点：不精确，仅仅是估计优点：精确缺点：可比性差，效率低那么，如何撇开计算机本身来估算一个算法的复杂性呢？1.5 算法的性能分析与度量1.5.2 算法效率的度量第37页，共51页，编辑于2022年，星期日第一章 绪论 一个程序的时间复杂度（Time complexity）是指程序运行从开始到结束所需要的时间。算法复杂性的度量属于事前估计。分为：算法复杂性的度量属于事前估计。分为：时间复杂度时间复杂度和和空间复杂度空间复杂度的度量。的度量。一个算法是由控制结构控制结构和原

29、操作原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。(计算T(n)见p29)许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。1.5 算法的性能分析与度量 时间复杂度：时间复杂度：第38页，共51页，编辑于2022年，星期日第一章 绪论1.5.4 O表示的含义表示的含义算法的渐进分析算法的渐进分析 1.5 算法的性能分

30、析与度量1.算法的渐进分析算法的渐进分析 算法的渐进分析简称算法分析。通常将问题的规模作为分析的参数，求算法的时间开销与问题规模n的关系。当且仅当存在正整数c和n0，使得T(n)c*f(n),对所有的nn0成立,则称该算法的时间增长率在O(f(n)中，记为T(n)=O(f(n)。第39页，共51页，编辑于2022年，星期日第一章 绪论例：例：考察T(n)=3n+2。当n=2时，3n+2=2时，10n2+4n+2=5时，10n2+5n=4时，n2=2n，有：6*2n+n2=7*2n 所以，T(n)=O(2n)第40页，共51页，编辑于2022年，星期日第一章 绪论算法分析举例(1)i=1;k=0

31、;while(in)k=k+10*i;i+;T(n)=O(n)这个函数是按线性阶递增的(2)i=0;k=0;do k=k+10*i;i+;while(in);T(n)=O(n)这也是线性阶递增的 例例1：分析下面程序段的时间复杂性：分析下面程序段的时间复杂性 1.5 算法的性能分析与度量第41页，共51页，编辑于2022年，星期日第一章 绪论(3)for(i=1;i=n;i+)for(j=1;j=n;j+)+x;s+=x;T(n)=O(n2)是平方阶递增的(4)for(i=1;i=n;i+)for(j=1;j0)if(x100)x=x-10;y-;else x+;T(n)=O(1)这个程序看起

32、来有点吓人，总共循环运行了1000次，但是我们看到n没有?没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。1.5 算法的性能分析与度量第43页，共51页，编辑于2022年，星期日第一章 绪论(6)i=1;while(i=n)i=i*2;T(n)=O(log2n)设其原操作执行的次数为t(n)于是，2t(n)n 从而有：t(n)log2n1.5 算法的性能分析与度量(7)s=0;for(i=0;i=n;i+)for(j=0;j=i;j+)for(k=0;k=j;k+)s+;T(n)=O(n3)n i j t(n)=1=i=0 j=0 k=0第44页，共51

33、页，编辑于2022年，星期日第一章 绪论 例例2：分析下面函数的复杂性：分析下面函数的复杂性 A是一个含有是一个含有n个不同元素的实数数组，给出求个不同元素的实数数组，给出求A之最大和最小之最大和最小元素的算法如下，分析它的时间复杂性。元素的算法如下，分析它的时间复杂性。算法 SM(A,n,max,min)SM1 初始化 maxmin a1 1SM2 比较 for(i=2;imax)max ai n-1 if(aimin)min ai n-1 T(n)=3n-1 T(n)=O(n)1.5 算法的性能分析与度量第45页，共51页，编辑于2022年，星期日第一章 绪论2.常见的算法时间复杂度：常见

34、的算法时间复杂度：常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。1.5 算法的性能分析与度量3.大大O运算规则运算规则 O(f(n)+O(g(n)=O(max(f(n),g(n)O(f(n)+O(g(n)=O(f(n)+g(n)O(f(n)O(g(n)=O(f(n)g(n)O(cf(n)=O(f(n)第46页，共51页，编辑于2022年，星期日第一章 绪论4.平均时间复杂性平均时间复杂性定义：定义：设一个领域问题的输入规模为n，Dn是该领域

35、问题的所有输入的集合，任一输入IDn，P(I)是I出现的概率，P(I)=1,t(I)是算法在输入I下执行的基本运算次数，则平均时间复杂性平均时间复杂性定义为：T(n)=P(I)*t(I)IDn最好时间复杂性、最坏时间复杂性、平均时间复杂性最好时间复杂性、最坏时间复杂性、平均时间复杂性 对于有些算法，问题规模相同，如果输入集不同，其效率不同 Tmin：最好情况不能代表算法的性能 Tmax：最坏情况可以知道算法至少能达到的性能 Tavg：较好地反映了算法的性能，但并不一定总是可行的！1.5 算法的性能分析与度量第47页，共51页，编辑于2022年，星期日第一章 绪论 例如：查找一个元素是否存在的算

36、法例如：查找一个元素是否存在的算法 int loc(int a,int x)a0=x;i=n;while(ai!=x)i=i-1;return i 最好：最好：T（n）=c O（1）最坏：最坏：T（n）=n+c O（n）平均：平均：T（n）=n/2+c O（n）1.5 算法的性能分析与度量第48页，共51页，编辑于2022年，星期日第一章 绪论5.算法时间复杂性的实质：算法时间复杂性的实质：算法与问题规模及时间的关系。算法与问题规模及时间的关系。同一问题，规模相同，用不同的算法解决，花费时间是不同的；同一问题，规模相同，用不同的算法解决，花费时间是不同的；同一问题，用不同的算法解决，在相同的时

37、间内所解决的问题同一问题，用不同的算法解决，在相同的时间内所解决的问题 规模大小不同；规模大小不同；思考：思考：“复杂性渐进阶比较低的算法比复杂性渐进阶比较高 的算法有效”，这种说法正确吗？另外需要注意：另外需要注意：当两个算法的复杂性渐进阶相同时，必须进一步考察T（n）的常数因子。1.5 算法的性能分析与度量第49页，共51页，编辑于2022年，星期日第一章 绪论1.为什么要讨论数据结构（数据结构的重要性）为什么要讨论数据结构（数据结构的重要性）本章小结本章小结2.数据结构的有关概念及它们之间的关系数据结构的有关概念及它们之间的关系 数据结构、逻辑结构、存储结构、数据结构、逻辑结构、存储结构、数据类型、数据类型、ADT等等3.算法及算法分析基础算法及算法分析基础 算法的定义及特点、算法分析的方法（算法的定义及特点、算法分析的方法（渐进时间复杂渐进时间复杂度度）第50页，共51页，编辑于2022年，星期日作业：1.总结本章主要内容2.自己找出或设计三个算法，并分析其时间复杂度。（要求三个算法的渐进时间复杂度不能相同）第51页，共51页，编辑于2022年，星期日