1、 数据结构与算法数据结构与算法 1ppt课件课程安排课程安排 讲授3学时/周， 实验2学时/周（分组） 总成绩：平时（听课：平时（听课 、作业、作业 、 期中期中 ） + 期末期末 教学用书： Robert L. Kruse and Alexander J. Ryba “Data Structures and Program Design in C+”，高教，高教出版社，出版社，2001年年 参考书： 1数据结构，许卓群，张乃孝，杨冬青，唐世渭，高数据结构，许卓群，张乃孝，杨冬青，唐世渭，高等教育出版社，等教育出版社，1987年年 2. 数据结构数据结构 C+与面向对象的途径，张乃孝，裘宗燕，
2、与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，高等教育出版社，1998年年 3数据结构数据结构(C语言版），严蔚敏、吴伟民，清华大学语言版），严蔚敏、吴伟民，清华大学出版社，出版社，1997年年 4. 数据结构与算法，王若梅等著，中山大学出版社，数据结构与算法，王若梅等著，中山大学出版社，2000年年2ppt课件为什么学习数据结构计算机科学是计算机科学是- “一种关于信息结构转换的科学一种关于信息结构转换的科学”(Wegnor) Input Output- “算法的学问算法的学问, 算法是精确定义的一系列规则算法是精确定义的一系列规则,指指出怎样从给定的输入信息经过有限步骤产生所出怎样从给
3、定的输入信息经过有限步骤产生所求的输出信息求的输出信息” (Knuth)信息结构信息结构(数据结构数据结构)和算法是计算机科学的核心和算法是计算机科学的核心课题课题. 两者之间有着本质的联系两者之间有着本质的联系. 数据结构数据结构+算法算法 = 程序程序 Computer system3ppt课件程序程序 = 算法算法 + 数据结构数据结构 数据结构：数据结构： 一种程序构件（一种程序构件（programming construct)、工、工具具; 编程中常用的数据组织形式及其操作的抽象；编程中常用的数据组织形式及其操作的抽象； 编程：编程： 数据结构的选择，数据结构的选择， 算法的设计与度
4、量算法的设计与度量4ppt课件教学目的教学目的 掌握常用的数据结构及其应用掌握常用的数据结构及其应用 学会合理地组织数据，学会合理地组织数据， 有效地表示数据和处有效地表示数据和处理数据理数据 掌握算法设计技术和分析技术掌握算法设计技术和分析技术 提高程序设计质量提高程序设计质量5ppt课件第一章第一章 概论概论 q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构 数据的存储结构6ppt课件什么是数据结构什么是数据结构-示例示例1 例例1 图书馆的书目自动检索系统。图书馆的书目自动检索系统。 所处理
5、的基本数据（所处理的基本数据（数据元素数据元素）： 每本书由（登录号，书名，每本书由（登录号，书名， 作者，出版社作者，出版社, 分类号分类号) 组成；组成；数据元素间的关系（数据元素间的关系（逻辑结构逻辑结构）： 一个按登录号顺序排列的书目表和按书名、作者和一个按登录号顺序排列的书目表和按书名、作者和分类号顺序排列的索引表；分类号顺序排列的索引表；所需的所需的操作操作： 一组作用在这些表上的运算（查询、插入、修改一组作用在这些表上的运算（查询、插入、修改等）；等）；怎样存储这些数据及其关系使得上述操作容易实现怎样存储这些数据及其关系使得上述操作容易实现存储结构存储结构。 7ppt课件什么是数
6、据结构什么是数据结构-示例示例2 例例 2 人机对弈问题（三子棋）。人机对弈问题（三子棋）。数据元素数据元素： 格局（某时刻的棋盘布局）；格局（某时刻的棋盘布局）；格局之间的关系格局之间的关系：一个格局可以派生出几个：一个格局可以派生出几个下一个格局（树状结构，博弈树）；下一个格局（树状结构，博弈树）；操作操作：由某个格局出发，借助于以上的格局树：由某个格局出发，借助于以上的格局树（显式地或非显式地）找出计算机赢的步骤；（显式地或非显式地）找出计算机赢的步骤；存储结构存储结构：如何存储格局及其格局间的关系。：如何存储格局及其格局间的关系。 8ppt课件什么是数据结构什么是数据结构-示例示例3例
7、例 3 3 多岔路口的交通灯管理系统多岔路口的交通灯管理系统。 BACDE数据元素数据元素：通路，：通路， 如：如：A - BA - B通路间的关系通路间的关系（图）：通路为结点，（图）：通路为结点，两节点相邻，如果两通路不能同时两节点相邻，如果两通路不能同时通行。通行。操作操作：上图的着色问题：用最少的颜色，对每个节：上图的着色问题：用最少的颜色，对每个节点着色，相邻节点着不同的颜色。点着色，相邻节点着不同的颜色。存储存储：如何存储通路间的关系：如何存储通路间的关系。9ppt课件第一章第一章 概论概论 q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量
8、算法的度量 数据结构示例 数据结构的概念数据结构的概念 数据的逻辑结构 数据的存储结构10ppt课件数据结构的概念数据结构的概念 数据数据是客观事物的符号表示，是客观事物的符号表示， 是信息的载体是信息的载体 数据元素数据元素是数据的基本单位是数据的基本单位数据结构是相互间具有某些关系的数据元素的数据结构是相互间具有某些关系的数据元素的集合。它包括下面三方面的内容：集合。它包括下面三方面的内容： 1 1） 数据的逻辑结构数据的逻辑结构， 表示数据元素间的表示数据元素间的关系；关系； 2 2）数据的运算数据的运算， 是数据元素集上所允许是数据元素集上所允许的操作；的操作； 3 3）数据的存储结构
9、数据的存储结构， 指如何在计算机上指如何在计算机上数据元素及其关系。数据元素及其关系。11ppt课件第一章第一章 概论概论 q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构数据的逻辑结构 数据的存储结构12ppt课件数据的逻辑结构数据的逻辑结构 数据的逻辑结构是一个二元组（数据的逻辑结构是一个二元组（D, R) , D 是数据是数据元素的有限集，元素的有限集， R 是是D上关系的有限集；上关系的有限集；例如，在示例例如，在示例3中，中，D = AB, AC, AD, BA, BC, BD, DA,
10、 DB, DC, DA, EB, DC,EDR = R1R1 = (AB, EA), (AB, BD), (AB, DA), (AB, BC), 13ppt课件逻辑结构的类型逻辑结构的类型我们将讨论我们将讨论 R 含有一个关系的情况含有一个关系的情况, 即即 R = R1. 根据根据R1的特性的特性, 数据结构数据结构(D, R1) 可分为下列几种可分为下列几种: D = d1, d2, , dn 1. 集合集合: 数据元素同数据元素同“属于一个集合属于一个集合”. R1 = 2. 线性结构线性结构: R1 = (d1, d2), (d2, d3), , (d(n-1), dn), 即除开始和
11、终结节点即除开始和终结节点d1, dn外外,每个节点有每个节点有一个前驱和一个后继一个前驱和一个后继3. 树状结构树状结构: (D, R1) 构成树构成树, 即每个元素最多有即每个元素最多有一个前驱一个前驱, 可以有多个后继可以有多个后继4. 图状结构图状结构: (D, R1)构成一个图构成一个图. 14ppt课件第一章第一章 概论概论 q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构 数据的存储结构数据的存储结构15ppt课件数据的存储结构数据的存储结构数据（逻辑）结构的存储包含数据（逻辑）结构
12、的存储包含数据元素的存储数据元素的存储及其及其逻逻辑关系辑关系的存储的存储 设设M M为内存的一片存储区域为内存的一片存储区域. . 将数据结构存储到计算将数据结构存储到计算机内机内, ,我们需要建立一个映射我们需要建立一个映射( (存储映像):): S : D - M S : D - M 即对于即对于D D中的每个数据元素中的每个数据元素d, S(d) M, d, S(d) M, 并且并且这个映射具有明显地或者隐含地体现这个映射具有明显地或者隐含地体现R R的能力的能力. . 根据存储映像的特点根据存储映像的特点, , 存储结构可分为存储结构可分为: : 顺序存储顺序存储结构、链式存储结构、
13、索引和散列结构、链式存储结构、索引和散列等。等。16ppt课件存储结构的分类存储结构的分类: 顺序结构顺序结构 顺序的方法顺序的方法: : 将逻辑上相邻的元素存储到物将逻辑上相邻的元素存储到物理上相邻的存储位置理上相邻的存储位置. . 常用于线性的数据结常用于线性的数据结构构. .例如例如, D = d1, d2, d3, d4, d5, D = d1, d2, d3, d4, d5 R = (d1,d2), (d2, d3), (d3, R = (d1,d2), (d2, d3), (d3, d4),(d4, d5)d4),(d4, d5)假定一个结点占一个单元假定一个结点占一个单元, ,
14、d1 d1存放于存放于200200号单元号单元. .d1d2d3d4d520020120220320417ppt课件存储结构的分类存储结构的分类: 链式结构链式结构 这种结构是给结点附加一个指针字段这种结构是给结点附加一个指针字段, 指出其后继指出其后继节点的位置节点的位置, 即存放结点的存储单元分为两部分即存放结点的存储单元分为两部分: 数据项指针项指针项可以有多个, 以指示多个后继. 例如, R = (d1, d2), (d1, d3), (d2, d4), (d2, d5), (d3, d6)d1d2d3d6d5d4d1d2d3d4d5d6空指针18ppt课件索引索引(Indexing)
15、的方法的方法 在线性结构中，将每个节点的序号作为其索引在线性结构中，将每个节点的序号作为其索引号。号。 索引的存储结构就是用节点的索引号来索引的存储结构就是用节点的索引号来确定节点的存储地址。确定节点的存储地址。数据存储区12345索引表存储索引号及地址M存储映像：Z - M19ppt课件 假设每个节点占用假设每个节点占用p p个单元且顺序存储，个单元且顺序存储， q q为开时节点的存储位置，那么第为开时节点的存储位置，那么第 i i 个个节点的存储位置为节点的存储位置为 （ i-1)i-1)* *p + qp + q 存储映像可以是非线性的。存储映像可以是非线性的。20ppt课件散列（散列（
16、hashing) 的方法的方法散列的方法是用结点的值来确定其地址。散列的方法是用结点的值来确定其地址。假设每个数据元素都有一个关键字，假设每个数据元素都有一个关键字， K K是关键是关键字的集合。函数：字的集合。函数： 称为称为散列函数。 最好的散列函数应满足不同的关键字具有不同最好的散列函数应满足不同的关键字具有不同的地址。如果不同的关键字对应的地址相同，的地址。如果不同的关键字对应的地址相同，则称为则称为“碰撞碰撞”（冲突）。（冲突）。 h : K - M21ppt课件 以上四种方法可以组合使用。例如，以上四种方法可以组合使用。例如， 先用先用散列的方法存储表，发生碰撞时，散列的方法存储表
17、，发生碰撞时， 用一个用一个链表存储所有的同义词。链表存储所有的同义词。 逻辑结构相同，但存储结构不同，则认为逻辑结构相同，但存储结构不同，则认为是不同的数据结构。是不同的数据结构。 如顺序表和链表具有如顺序表和链表具有相同的逻辑结构，但存储结构分别为顺序相同的逻辑结构，但存储结构分别为顺序结构和链表结构。结构和链表结构。22ppt课件第一章第一章 概论概论q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量23ppt课件数据类型数据类型(Data Type) 一般的高级语言都提供了一些一般的高级语言都提供了一些数据类型数据类型, , 如整数如整
18、数型型, , 字符型等字符型等. . 数据类型是一个值的集合和定义数据类型是一个值的集合和定义在此集合上的一组操作的总称在此集合上的一组操作的总称. . 用户还可以定义用户还可以定义自己的数据类型自己的数据类型. . 数据类型可分为数据类型可分为原子类型( (不可分解的不可分解的, ,如如int, int, boolbool, char , char 等等) ) 和和结构类型( (由其他类型构成由其他类型构成) ) 数据类型为程序员提供了极大的方便数据类型为程序员提供了极大的方便: : 它将数据它将数据集合及其上的操作与其实现细节集合及其上的操作与其实现细节分离开来来, ,或者说或者说将将数据
19、的逻辑表示和运算数据的逻辑表示和运算与它们的与它们的实现实现相分离。相分离。程序员只需要了解此集合由哪些值构成程序员只需要了解此集合由哪些值构成, , 可以进可以进行那些运算行那些运算. . 24ppt课件抽象数据类型抽象数据类型(ADT) 我们把数据元素集合我们把数据元素集合( (或者一个数据模型或者一个数据模型) )及其上的及其上的一组操作的数学说明称为一组操作的数学说明称为抽象数据类型抽象数据类型(Abstract (Abstract Data Types),Data Types),常用常用ADTADT表示。表示。 例如，表示圆的例如，表示圆的ADTADT： 数据模型：表示圆的半径和圆心
20、的三个实数；数据模型：表示圆的半径和圆心的三个实数； 操作：构造一个给定圆心和半径的圆；求圆的面积操作：构造一个给定圆心和半径的圆；求圆的面积等等 一个数据结构是一个一个数据结构是一个ADTADT的实现。的实现。 现代程序设计使用信息隐蔽和数据封装，使得现代程序设计使用信息隐蔽和数据封装，使得ADTADT的使用和实现相分离，的使用和实现相分离，ADTADT的使用和的使用和 ADTADT的实现可的实现可以同时进行，以同时进行，ADTADT实现的修改不影响实现的修改不影响ADTADT的使用。的使用。 本课程介绍的数据结构将由抽象数据结构描述本课程介绍的数据结构将由抽象数据结构描述. .25ppt课
21、件ADT在在OO语言中的实现语言中的实现 在在C+C+中，一个中，一个ADTADT与其实现构成一个与其实现构成一个class,class,或者说或者说抽象数据类型可以由抽象数据类型可以由C+C+的的类来描述，来描述， ADTADT的每个运的每个运算对应一个成员函数。算对应一个成员函数。例如，表示圆的例如，表示圆的class class Circle private: float r, x, y; public: Circle(float v1,float v2, float v3); float area ()= return pi*r*r; ; 一个抽象数据类型中的数据元素集可以是任意时，一
22、个抽象数据类型中的数据元素集可以是任意时，即即多态ADTADT，这样的，这样的ADTADT可用可用template来描述。来描述。26ppt课件第一章第一章 概论概论q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量27ppt课件算法的概念算法的概念 一个一个算法算法是对特定问题求解步骤的一种描述是对特定问题求解步骤的一种描述, ,它它是指令的有穷序列是指令的有穷序列. . 算法具有以下特性算法具有以下特性: : 1) 1) 有穷性有穷性: : 一个算法总是在执行有穷步后结束一个算法总是在执行有穷步后结束 2) 2) 确定性确定性: : 算法的
23、每一步都必须是明确地定义的算法的每一步都必须是明确地定义的. . 3) 3) 可行性可行性: : 算法中的每一步都是可以通过已经实现的算法中的每一步都是可以通过已经实现的操作来完成的操作来完成的 4) 4) 输入输入: : 一个算法有零个或者多个输入一个算法有零个或者多个输入, , 这些输入这些输入取自于特定的对象集合取自于特定的对象集合 5) 5) 输出输出: :一个算法有一个或者多个输出，它们是与一个算法有一个或者多个输出，它们是与输入有特定关系的量输入有特定关系的量28ppt课件算法的描述算法的描述算法的描述可以用下列语言描述：算法的描述可以用下列语言描述： 自然语言自然语言 程序设计语
24、言程序设计语言 介于自然语言和程序设计语言的伪代码介于自然语言和程序设计语言的伪代码 框图框图29ppt课件算法的设计要求算法的设计要求算法的设计应满足：算法的设计应满足：1 1）正确性正确性：对于合法的输入产生符合要求的输出；：对于合法的输入产生符合要求的输出；2 2）可读性可读性：算法应该易读、便于交流，：算法应该易读、便于交流， 这也是保证算这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法正确性的前提；添加注释也是一种增加可读性的办法；法；3 3）健壮性健壮性：当输入非法时，：当输入非法时， 算法还能做出适当的反应算法还能做出适当的反应而不会崩溃，而不会崩溃， 如输出错误信息
25、；算法中应该考虑适如输出错误信息；算法中应该考虑适当的错误处理；当的错误处理；4 4）效率高且内存消耗小效率高且内存消耗小：效率高指运行时间短。存储：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。指算法执行过程中所需的最大存储空间。30ppt课件算法设计算法设计例 假设有假设有n(=1)n(=1)个整数个整数a1, a2, a1, a2, , an. , an. 要求要求对此数列由小到大进行排序。对此数列由小到大进行排序。显然这个数列构成一个线性结构。我们选择顺显然这个数列构成一个线性结构。我们选择顺序存储结构，即用一个数组序存储结构，即用一个数组A A存储此数列及排存储此数列及
26、排序后的数列。序后的数列。思路：思路： 1 1 从未排好序的数列中选出最小的元素，将从未排好序的数列中选出最小的元素，将其放到排好序的数列后其放到排好序的数列后 2 2 重复这个过程，直至排序结束。重复这个过程，直至排序结束。31ppt课件a1a2a3an找出最小元素aja1a2a3anaj交换a1和aja1a2a3anaj找出最小元素aja1a2a3anaj交换a2 和aj32ppt课件 进一步细化：假设n个数存放在一个数组A0.n-1中1. 循环 i 以1 步长， 从0到 n-2, 执行 （1）j i /Ai 存储从Ai 到An-1的最小整数 (2) 循环 k以1为步长, 从i+1到n-1
27、, 执行 若Ak Aj, 则 j k / 从Ai到An中选出最小整数 (3) t Ai; Ai Aj ; Aj t / 交换Ai, Aj2. 算法结束. 33ppt课件void selectSort (int a, const int n) / 将整数列a0, , an-1按非递减序排列 for (int i = 0; i n -1; i+) int j = i; / 找出ai到an-1的最小数aj for (int k = i + 1; k n, k+) if (ak aj) j = k; / j指示当前的最小数 /交换ai和aj int temp t = ai; ai= aj; aj =
28、t; 34ppt课件模板（Template)前一程序只适用于整数列的排序。事实上，此算法适前一程序只适用于整数列的排序。事实上，此算法适用于任何（定义了比较运算）类型的序列。用于任何（定义了比较运算）类型的序列。 我们可我们可以用以用C+C+提供的模板机制来设计一个更通用的排序算提供的模板机制来设计一个更通用的排序算法。法。一个模板函数是适用于很多类型的函数一个模板函数是适用于很多类型的函数: : 在这些类型在这些类型上运算遵从相同的模式。上运算遵从相同的模式。 它带有类型参数的函数，它带有类型参数的函数， 当类型参数用特定的参数代换时，编译器生成针对此当类型参数用特定的参数代换时，编译器生成
29、针对此类型的特定函数。类型的特定函数。同样，一个模板类是带有类型参数的类，它适用于多同样，一个模板类是带有类型参数的类，它适用于多种类型。通过简单的类型代换，编译器便可生成代换种类型。通过简单的类型代换，编译器便可生成代换类型的类。类型的类。35ppt课件template class dataList1private: T *element; int arraySize; void swap(const int m1, const int m2); int minKey(const int low, const int high);public: dataList(int size = 10)
30、: arraySize(size), element(new Tsize) dataList()delete element; void sort();36ppt课件template void dataList : swap(const int m1, const int m2) T temp = elementm1; elementm1=elementm2; elementm2= temp;template int dataList:minKey(const int low, const int high) int min = low; for (int k=low+1;k=high;k+)
31、 if(elementk elementmin) min = k; return min;37ppt课件template void dataList:sort() for(int i =0; iarraySize-1; i+) int j = minKey(i, arraySize-1); if (j!= i ) swap(j,i); 38ppt课件第一章第一章 概论概论q什么是数据结构什么是数据结构q抽象数据类型抽象数据类型q算法的概念算法的概念q算法的度量算法的度量39ppt课件算法分析算法分析解决同一问题的算法可以有多种。解决同一问题的算法可以有多种。 我们希望从中我们希望从中选出最优的
32、算法，效率高或者存储空间小。选出最优的算法，效率高或者存储空间小。 为为此，我们需要对算法进行评估，分析。通常有两此，我们需要对算法进行评估，分析。通常有两种方法：种方法： 事后统计事后统计：不同算法的程序运行在同一组输入上，：不同算法的程序运行在同一组输入上，根据时间和空间的统计来比较优劣。根据时间和空间的统计来比较优劣。 缺陷：事缺陷：事先编写程序；先编写程序； 依赖于程序运行的软硬件环境。依赖于程序运行的软硬件环境。 习题习题: : 试统计函数试统计函数sort()sort()在不同大小输入上的运在不同大小输入上的运行时间行时间. .40ppt课件算法分析算法分析 事前估计事前估计：一种
33、不考虑算法的程序运行软：一种不考虑算法的程序运行软硬件环境的分析方法。一个算法的运行工硬件环境的分析方法。一个算法的运行工作量的大小只依赖于问题的规模。作量的大小只依赖于问题的规模。通常考虑两个度量：通常考虑两个度量： 时间复杂度：算法执行的操作的总数作为时间复杂度：算法执行的操作的总数作为问题规模的函数。问题规模的函数。 空间复杂度：算法执行时所占用的存储空空间复杂度：算法执行时所占用的存储空间作为问题规模的函数。间作为问题规模的函数。41ppt课件时间复杂度时间复杂度对于给定规模的问题，计算算法运行的总对于给定规模的问题，计算算法运行的总“步数步数”： 在算法中选取一种基本操作作为在算法中
34、选取一种基本操作作为“程序步程序步”（多种不同的操作可视为一个程序步，或（多种不同的操作可视为一个程序步，或者不同的操作具有不同的权）；者不同的操作具有不同的权）； 统计算法从开始到运行终止时所需总程序统计算法从开始到运行终止时所需总程序步数步数T, T, 并将其视为问题规模并将其视为问题规模n n的函数的函数T(n). T(n). T(n) T(n) 称为算法的时间复杂度。称为算法的时间复杂度。42ppt课件例 迭代累加求和 float sum(int a, const int n) float s = 0.0; / 计一步 for (int i = 0; i n; i+ ) s += ai
35、; / 每次循环计步: 赋值 return s; 总计步数:n + 问题的规模即数组的规模n 43ppt课件 包含函数调用的赋值语句的程序步数：x = sum (A, n); 总步数：调用的步数 + 1 即 (n + ) + 1 基本运算的完成时间不应该依基本运算的完成时间不应该依赖于所涉及参数值赖于所涉及参数值44ppt课件求总程序步数(数组的大小n为问题的规模) ：void selectSort (int a, const int n) for (int i = 0; i n -1; i+) int j = i;/计一次 for (int k = i + 1; k n, k+) if (a
36、k aj) j = k;/ if 语句最多计步 /此循环总步数= 2*(n-i-1) int temp t = ai; ai= aj; aj = t; / 计3步 / n-1 次循环, 每次 1 + *(n-i-1) + 3/总计 T(n) = n-2i=0(1 + (n-i-1) + 3) = （n+4)*(n-1)/ T(n) 与输入有关系.45ppt课件 时间复杂度时间复杂度T(n)T(n)可能依赖于输入，即不同可能依赖于输入，即不同的输入（相同的规模）其复杂度不同，譬的输入（相同的规模）其复杂度不同，譬如排序算法此时可以计算平均复杂度或如排序算法此时可以计算平均复杂度或者最坏情况复杂度
37、者最坏情况复杂度 平均复杂度平均复杂度(The Average Case)(The Average Case)：所有可：所有可能输入数据集的期望值能输入数据集的期望值 最坏情况复杂度最坏情况复杂度(The Worst Case)(The Worst Case)：估算：估算最坏情况下时间复杂度的一个上界这也最坏情况下时间复杂度的一个上界这也是通常所指的复杂度是通常所指的复杂度46ppt课件 复杂度的度量通常计算到数量级如果复杂度的度量通常计算到数量级如果f(n)f(n)是一是一个函数，并且存在一个常数个函数，并且存在一个常数c, c, 当当n n充分大时，充分大时，则记为则记为T(n) = O(
38、f(n)如如 T(n) = 3n2 +12n, 则则T(n) = O(n2)累加求和的例子累加求和的例子: : T(n) = O(n)排序的例子排序的例子: T(n) = O(n2) ) 注意：我们不写注意：我们不写T(n)=O(3n2), 或者或者T(n) = O(n3), 应该取最小的上界。应该取最小的上界。 常见的复杂度：常见的复杂度：O(1), O(log2 n), O(n), O(nlog2 n) , O(n2), O(2n), O(n!)T(n) = c f(n)47ppt课件nT(n)200log2n100n5n22n20102000100048ppt课件 T1(n) = 100
39、nlog n , T2(n) = n2, 假设问题规模为n=28规模nT1(n)花费时间T2(n)花费时间1000.06秒秒0.01秒秒10001秒秒1秒秒1000013秒秒100秒秒1000002分分166分分100000033分分16666分分=11.5天天49ppt课件更快的机器还是更快的算法更快的机器还是更快的算法 换一个快换一个快10倍的机器能否解决更大的问题呢？倍的机器能否解决更大的问题呢？T(n)n n变化变化 n/n10n100010000n=10n1020n5005000n=10n105nlogn25018423nn10n7.372n270223n=101/2n3.162n1
40、316n=n+3n:原机器一小时解决问题规模，n:新机器一小时解决问题规模50ppt课件大大O表示法表示法 加法法则加法法则：(n) = T1(n) + T2(n) = O(f1(n) + O(f2(n) = O(max(f1(n), f2(n)即：如果两个程序段的复杂度分别为即：如果两个程序段的复杂度分别为O(f1(n)和和O(f2(n), 则将这两个程序段顺序连接的程序的复杂则将这两个程序段顺序连接的程序的复杂度为度为O(max(f1(n), f2(n). 例如，考虑以下的程序段：例如，考虑以下的程序段： action1(); / action1的时间复杂度为O(f1(n) actions
41、(); /action2的时间复杂度为O(f2(n) 此程序段的时间复杂度为此程序段的时间复杂度为O(max(f1(n), f2(n).51ppt课件 乘法法则：乘法法则：(n) = T1(n) T2(n) = O(f1(n) O(f2(n) = O(f1(n) f2(n)例例 如，下面的程序段如，下面的程序段： for (i = 1; i = n , i+ ) action()这里，这里， 如果以如果以action的时间代价为单位，则的时间代价为单位，则 for 循环的代循环的代价为价为T1(n)=O(n)。假设假设action的时间复杂度为的时间复杂度为O(f(n), 按乘按乘法法则，此程
42、序段的时间法杂度为法法则，此程序段的时间法杂度为 O(n f(n). 如果一个程序的执行代价为如果一个程序的执行代价为O(f1(n), 但其单位是另一个但其单位是另一个程序的执行代价，而后一个程序的执行代价为程序的执行代价，而后一个程序的执行代价为O(f2(n), 则则原程序的执行代价为原程序的执行代价为O(f1(n) f2(n).52ppt课件空间复杂度空间复杂度 计算算法运行过程所占用的存储量作为问计算算法运行过程所占用的存储量作为问题规模的函数题规模的函数 S(n) = O(f(n). . 通常以简单变量的存储空间为单位通常以简单变量的存储空间为单位 算法的存储空间包括：算法的存储空间包
43、括： 1 1）程序本身、常量和变量等所需空间）程序本身、常量和变量等所需空间 2 2）程序运行中动态申请的空间和递归调）程序运行中动态申请的空间和递归调用所需空间用所需空间 通常考虑除输入和程序以外的空间通常考虑除输入和程序以外的空间. . 如果如果相对于输入是常数相对于输入是常数, , 则称为原地工作则称为原地工作. . 如如sum sum 和和selectSortselectSort. . 53ppt课件Notation T(n) is said to be (g(n), if there exist two positive constants c and n0 such that T(
44、n)cg(n) For example, for selectSort(), T(n)= (n2 ) An algorithm is said to be (h(n) if it is O(h(n) and (h(n). For selectSort(), T(n) = (n2) T(n) = (h(n), if the limit of T(n)/h(n) is a nonzero constant.54ppt课件小结和要求小结和要求 理解数据结构和算法的内容理解数据结构和算法的内容 理解和掌握抽象数据类型的概念理解和掌握抽象数据类型的概念 掌握使用程序设计语言描述数据的存储结构掌握使用程序
45、设计语言描述数据的存储结构 掌握算法的概念，算法的定义和特点掌握算法的概念，算法的定义和特点 理解设计算法的一般要求理解设计算法的一般要求 掌握算法的设计与描述掌握算法的设计与描述 掌握算法时间复杂度的概念、表示法和基本掌握算法时间复杂度的概念、表示法和基本分析方法分析方法55ppt课件上机实习上机实习1.定义集合的定义集合的ADT并实现之（包括集合的交并实现之（包括集合的交, 并并, 判判定是否为空定是否为空, 求基数等运算）。求基数等运算）。2. 编写一个程序创建（英文）文本文件的索引：统编写一个程序创建（英文）文本文件的索引：统计一个文本文件每个词出现的所有行号并按字典序计一个文本文件每
46、个词出现的所有行号并按字典序排列之。进一步统计文件的行数和总字数。排列之。进一步统计文件的行数和总字数。3. 编写一个汉字输入方法。编写一个汉字输入方法。4. 实现一个排序算法实现一个排序算法. a) 利用事后统计法观察其时间复杂度利用事后统计法观察其时间复杂度. (利用某种方利用某种方法生成足够大的输入法生成足够大的输入, 将输入和输出存到文件中以将输入和输出存到文件中以便于观察便于观察. ) b) 利用事前估计法估算其复杂度利用事前估计法估算其复杂度, 并用大并用大O表示法表表示法表示之示之. c) 你是如何确保你的排序是正确的你是如何确保你的排序是正确的?能否给出一种函能否给出一种函数测试排序的正确性数测试排序的正确性?56ppt课件
