西安交通大学自动化系本科生课程西安交通大学自动化系本科生课程数据结构与算法数据结构与算法Data Structure and Algorithms西安交通大学自动化系西安交通大学自动化系杜友田杜友田duytmail.xjtu.edu.cn2数据结构课程简介 【课程内容】数据数据的各种的各种逻辑结构逻辑结构和和物理结构物理结构（存储结构）（存储结构），以及它们之间的相应，以及它们之间的相应关系关系并并并并对每种结构定义相适应的各种对每种结构定义相适应的各种运算运算设计出相应的设计出相应的算法算法分析算法的分析算法的效率效率 常用数据结构类型常用数据结构类型： 线性表、栈和队列、串、线性表、栈和队列、串、数组和特殊矩阵、树和二叉树、图。数组和特殊矩阵、树和二叉树、图。3【学习目的】为后续专业课程打下算法与数据结构方面的知为后续专业课程打下算法与数据结构方面的知 识基础；识基础；掌握必要的软件设计方面的技能。掌握必要的软件设计方面的技能。 【学习要求】掌握各类掌握各类数据结构类型数据结构类型和相应的和相应的存储结构存储结构提高阅读和编写提高阅读和编写算法算法的能力的能力能针对给定问题，能针对给定问题，选择选择相适应的数据结构，并相适应的数据结构，并能能设计和分析算法设计和分析算法。 数据结构课程简介 前期课程前期课程数据结构数据结构计算机基础计算机基础C语言语言离散数学离散数学后期课程后期课程操作系统操作系统编译原理编译原理数据库原理数据库原理软件工程软件工程承上承上启下启下4【课程体系】数据结构课程简介 是计算机专是计算机专业各类考试中业各类考试中的必考课程的必考课程C语言语言数据结构数据结构软件工程软件工程掌握基本编掌握基本编程方法程方法掌握数据掌握数据组织组织和和处理处理的方法的方法掌握软件开发掌握软件开发的系统方法的系统方法基本要求课程关系5数据结构课程简介 【课程体系】与先修课C+语言程序设计的联系和区别C语言侧重于通过编写不太复杂的程序而理解掌握语言的特性语言的特性和语言的运用语言的运用。数据结构侧重于给出解决问题的策略和方法策略和方法，即研究算法；还要求算法的时空效率高算法的时空效率高，算法结构和可结构和可读性好、容易验证读性好、容易验证等等。对问题的数据表示数据表示和求解所采取的观点也有大大的提高，通过定义数据结构及其上的操作以解决问题。解决某个问题的程序，如果是用“就事论事”的策略写成的，在C语言中是合格的，在数据结构中过去的算法可能就不再合格了。数据结构课程简介 6数据结构的发展1968年在国外规定为一门独立的课程，美国D.E.Knuth 教授的著作计算机程序设计技巧第一卷基本算法出版，系统阐述数据的逻辑结构和存储结构及其操作；20世纪60年代末70年代初提出“数据结构+算法=程序设计”的思想；20世纪70年代中期到80年代初，各种版本的数据结构著作问世；我国从1978年开设本课程，目前，它不仅是计算机专业教学计划中的核心课程之一，而且是其他非计算机专业的主要选修课程之一；发展方向：面向专门领域中特殊问题的数据结构；从抽象数据类型的观点讨论数据结构。数据结构课程简介 7【参考书目】n数据结构数据结构（C C语言版）语言版）, ,严蔚严蔚敏敏，吴伟民，吴伟民，清华大学出版社清华大学出版社n数据结构题集数据结构题集, ,严蔚严蔚敏敏，吴伟民，清华大，吴伟民，清华大学出版社学出版社 T.H.Cormen, et al. Introduction to Algorithms (2nd Edition). MIT Press, 2002.科曼等著科曼等著, , 潘金贵译潘金贵译. . 算法导论算法导论( (第第2 2版版). ). 北京北京: : 机机械工业出版社械工业出版社, 2006. , 2006. 8数据结构课程简介 【教学方式】课堂讲授（课堂讲授（48学时）上机实验（学时）上机实验（8学时）学时）数据结构课程简介 【考核方式】考勤：考勤： 10分分作业：作业： 10分分实验：实验： 20分分考试：考试： 60分分9【一些期望】大胆提问，积极沟通大胆提问，积极沟通认真完成作业和实验认真完成作业和实验涉猎相关的书籍教材涉猎相关的书籍教材【联系方式】杜友田，电信学院杜友田，电信学院 自动化系自动化系 系统工程研究所系统工程研究所 智能网络与网络安全教育部重点实验室智能网络与网络安全教育部重点实验室办公室：科学馆办公室：科学馆251251Tel：82663467(O),13572275205E-mail:duytmail.xjtu.edu.cn10数据结构课程简介 第一章第一章 绪绪 论论1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 1.4 算法和算法分析算法和算法分析 1.4.1 1.4.1 算法算法 1.4.2 1.4.2 算法设计的要求算法设计的要求 1.4.3 1.4.3 算法效率的度量算法效率的度量 1.4.4 1.4.4 算法的存储空间的需求算法的存储空间的需求111.1 什么是数据结构问题机外表示处理要求逻辑结构基本运算数学模型存储结构编程实现实现建模求解计算机求解问题的步骤计算机求解问题的步骤: :l 分析问题分析问题；l 建立求解问题的建立求解问题的数学数学模型模型并并设计算法设计算法通过算通过算 法来表示法来表示对象数据及其相互关系对象数据及其相互关系；l 实现：实现：编编制制程序程序模拟对象领域中的求解过程模拟对象领域中的求解过程。12例例1 1 图书馆的书目检索自动化系统图书馆的书目检索自动化系统登录号：书名：作者名：分类号： ： ：书目卡片书目文件按书名按作者名按分类号索引表线性表131.1 什么是数据结构树.141.1 什么是数据结构例例2 2 计算机和人计算机和人 对奕问题对奕问题例例3 3 田径赛的时间安排问题田径赛的时间安排问题田径赛的时间安排问题田径赛的时间安排问题图姓名姓名项目项目1项目项目2项目项目3丁丁1跳高跳高跳远跳远100M马马2标枪标枪铅球铅球张张3标枪标枪100M200M李李4铅球铅球200M跳高跳高王王5跳远跳远200M1 1 1 1、任一选手所选中的项目中应该两两有边相连；、任一选手所选中的项目中应该两两有边相连；、任一选手所选中的项目中应该两两有边相连；、任一选手所选中的项目中应该两两有边相连；2 2 2 2、任一两个有边相连的顶点颜色不能相同。、任一两个有边相连的顶点颜色不能相同。、任一两个有边相连的顶点颜色不能相同。、任一两个有边相连的顶点颜色不能相同。15跳高跳高跳远跳远标枪标枪铅球铅球200M100M1.1 什么是数据结构跳高跳高跳远跳远铅球铅球标枪标枪100M200M跳高跳高111011跳远跳远110011铅球铅球101101标枪标枪001111100M110111200M111111用矩阵形式表示的图用矩阵形式表示的图0：两个项目无冲突；：两个项目无冲突；1：两个项目有冲突。：两个项目有冲突。161.1 什么是数据结构例例4 4 铺设煤气管道问题铺设煤气管道问题假设要在假设要在n n个居民区之间个居民区之间铺设煤气管道，设任意铺设煤气管道，设任意两个居民区之间都可以两个居民区之间都可以架设管道，但每条管道架设管道，但每条管道的的费用费用成本不同，求投成本不同，求投资最少管道铺设方案。资最少管道铺设方案。CBAED325416216945364740CBAED32162136171.1 什么是数据结构问题问题逻辑结构逻辑结构(模型模型)物理结构物理结构(存储存储)运算运算(算算法法) 分析分析设计设计编码编码测试测试数据结构就是研究数据的数据结构就是研究数据的逻辑结构逻辑结构、物理结构物理结构及其及其相互关系相互关系，并定义相应的，并定义相应的运算运算。数据结构的三个方。数据结构的三个方面：面：1逻辑结构逻辑结构数据之间的逻辑关系（抽象出来的数数据之间的逻辑关系（抽象出来的数学模型）学模型）2物理结构物理结构数据在计算机中如何表示数据在计算机中如何表示3运算运算解决具体问题的基本操作解决具体问题的基本操作算法设计，依赖于计算机如何存储问题的数学模型。算法设计，依赖于计算机如何存储问题的数学模型。181.1 什么是数据结构Niklaus Wirth (尼克劳斯尼克劳斯沃斯沃斯)： 世界著名计算机科学家，世界著名计算机科学家，PASCAL语言发明人语言发明人 Data structure + Algorithm = Programming数据结构数据结构+算法算法=程序设计程序设计程序设计程序设计：为计算机处理问题编制一组指令集：为计算机处理问题编制一组指令集算法算法：处理问题的策略处理问题的策略数据结构数据结构：问题的数学模型、：问题的数学模型、存储结构、运算等存储结构、运算等191.1 什么是数据结构概括地说概括地说：数据结构是一门讨论数据结构是一门讨论“描述描述现实世界实体现实世界实体的数学模型的数学模型(非数值计算非数值计算)及其上的操作及其上的操作在计算在计算机中如何机中如何表示和实现表示和实现”的学科。的学科。1.1 什么是数据结构数据数据(Data):(Data):是对信息的一种符号表示。在计算机是对信息的一种符号表示。在计算机科学中是指所有科学中是指所有能输入到计算机中能输入到计算机中并并被计算机程序被计算机程序处理处理的的符号的总称符号的总称。数据元素数据元素(Data Element):(Data Element):是数据的基本单位，在是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个一个数据元素可由若干个数据项数据项组成。数据项组成。数据项是数据的不可分割的最小单位。是数据的不可分割的最小单位。1.2 基本概念和术语21姓名姓名地址地址李1XXX李2XXX张1XXX张2XXX王1XXX王2XXX22数据元素数据元素例例: : 通讯录通讯录1.2 基本概念和术语数据项数据项数据结构数据结构(Data Structure)(Data Structure)：是相互之间存在一种或是相互之间存在一种或多种多种特定关系特定关系的的数据元素的集合数据元素的集合。数据之间的相互关系称为数据之间的相互关系称为逻辑结构逻辑结构，通常分为四类基，通常分为四类基本结构：本结构： 集合：集合：数据元素除同属于一种类型外，别无其它数据元素除同属于一种类型外，别无其它关系。关系。 线性结构：线性结构：数据元素之间存在一对一的关系。数据元素之间存在一对一的关系。 树型结构：树型结构：数据元素之间存在一对多的关系。数据元素之间存在一对多的关系。 图状结构：图状结构：数据元素之间存在多对多的关系。数据元素之间存在多对多的关系。231.2 基本概念和术语结构1.2 基本概念和术语（b）线性结构）线性结构（c）树状结构）树状结构（d）图状或网状结构）图状或网状结构逻辑结构示意图逻辑结构示意图（a）集合）集合【数据结构的形式定义数据结构的形式定义】： Data_StructureData_Structure=(D=(D, ,S)S) 其中，其中，D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有限集。上关系的有限集。例：复数的数据结构定义如下：例：复数的数据结构定义如下： Complex=(CComplex=(C，R)R) C C是含两个实数的集合是含两个实数的集合C1C1，C2C2，表示复数的实部，表示复数的实部和虚部。和虚部。 R=R=C1C1，C2C2 ，表示，表示C1,C2C1,C2之间存在有序偶的关之间存在有序偶的关系。系。251.2 基本概念和术语二元组(two-tuple)数据表示+关系表示该定义仅是对操作对象的一种数学描述，或者说，是从操作对象抽该定义仅是对操作对象的一种数学描述，或者说，是从操作对象抽象出来的数学模型。其中的象出来的数学模型。其中的“关系关系”描述的是数据间的逻辑关系。描述的是数据间的逻辑关系。数据结构在计算机中的表示称为数据的数据结构在计算机中的表示称为数据的存储结构存储结构： 结点结点（数据元素）和（数据元素）和数据域数据域（数据项）；（数据项）； 顺序存储结构：顺序存储结构：用数据元素在存储器中的相对位置来用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系表示数据元素之间的逻辑关系； 链式存储结构：链式存储结构：在每一个数据元素中增加一个存放地在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。址的指针，用此指针来表示数据元素之间的逻辑关系。26数据的逻辑结构与存储结构密切相关数据的逻辑结构与存储结构密切相关: :算法设计算法设计 逻辑结构逻辑结构算法实现算法实现 存储结构存储结构1.2 基本概念和术语关系表示数据表示(简单、不灵活简单、不灵活)(复杂、灵活复杂、灵活)元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储271.2 基本概念和术语1536元素元素2 21400元素元素1 11346元素元素3 3元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 . . . . . 14001400 元素元素2 2 15361536 . . . . . 15361536 元素元素3 3 13461346链式存储链式存储h281.2 基本概念和术语数据类型数据类型( (DTDT) )：一个一个值的集合值的集合及定义在该集合上的及定义在该集合上的一组操一组操作，作，用以刻画操作对象的特性。用以刻画操作对象的特性。 在高级语言中，包含：在高级语言中，包含：原子类型原子类型 - - 值不可分解值不可分解intint, char, unsigned char, char * , char, unsigned char, char * 等等结构类型结构类型 可以分解可以分解数组等数组等在底层硬件系统中，包含：在底层硬件系统中，包含：位、字节、字等原子类型（与、或、移位等）位、字节、字等原子类型（与、或、移位等） “数据类型数据类型”的作用：的作用：对计算机来说，解释计算机内存信息的手段对计算机来说，解释计算机内存信息的手段对用户来说，实现信息隐蔽，将用户不必了解的细节对用户来说，实现信息隐蔽，将用户不必了解的细节封装在类型中。封装在类型中。1.2 基本概念和术语29抽象数据类型（抽象数据类型（ADTADT）：）：一个一个数学模型数学模型以及定义在该模型上的以及定义在该模型上的一组操作一组操作。ADTADT实际上定义了一个数据结构的实际上定义了一个数据结构的逻辑结构逻辑结构以及在以及在此结构上的此结构上的一组算法一组算法, ,包含了该数据结构的全部内容。包含了该数据结构的全部内容。 ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT ADT 抽象数据类型名抽象数据类型名抽象数据类型与数据类型的联系：抽象数据类型与数据类型的联系：同数据类型本质上是一个概念，其同数据类型本质上是一个概念，其“抽象抽象”主要在于数学主要在于数学模型的数学抽象特性；模型的数学抽象特性；范畴更广，可以根据用户需要进行定义。范畴更广，可以根据用户需要进行定义。301.2 基本概念和术语逻辑结构逻辑结构 ADT （对用户透明）User 1User 2User n.实现1实现2实现3311.2 基本概念和术语例例例例1 1抽象数据类型复数的定义：抽象数据类型复数的定义：抽象数据类型复数的定义：抽象数据类型复数的定义：ADTComplexADTComplex 数据对象：数据对象：数据对象：数据对象：D De1,e2e1,e2e1,e2e1,e2RealSetRealSet 数据关系：数据关系：数据关系：数据关系：R1R1e1e1是复数的实数部分是复数的实数部分是复数的实数部分是复数的实数部分,e2,e2是复数的虚数部分是复数的虚数部分是复数的虚数部分是复数的虚数部分 基本操作：基本操作：基本操作：基本操作：InitComplexInitComplex(&Z,v1,v2)(&Z,v1,v2)操作结果：构造复数操作结果：构造复数操作结果：构造复数操作结果：构造复数Z,Z,其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数v1v1和和和和v2v2的值。的值。的值。的值。GetRealGetReal(Z,&(Z,&realPartrealPart) )初始条件：复数已存在。初始条件：复数已存在。初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用操作结果：用操作结果：用realPartrealPart返回复数返回复数返回复数返回复数Z Z的实部值。的实部值。的实部值。的实部值。GetImagGetImag(Z,&(Z,&ImagPartImagPart) )初始条件：复数已存在。初始条件：复数已存在。初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用操作结果：用操作结果：用ImagPartImagPart返回复数返回复数返回复数返回复数Z Z的虚部值。的虚部值。的虚部值。的虚部值。Add(z1,z2,&sum)Add(z1,z2,&sum)初始条件：初始条件：初始条件：初始条件：z1,z2z1,z2是复数。是复数。是复数。是复数。操作结果：用操作结果：用操作结果：用操作结果：用sumsum返回两个复数返回两个复数返回两个复数返回两个复数z1,z2z1,z2的和值。的和值。的和值。的和值。ADTComplexADTComplex321.2 基本概念和术语还可以实现其它操作，譬如：还可以实现其它操作，譬如：复数相乘，复数共轭等。复数相乘，复数共轭等。C C语言实现语言实现1.2 基本概念和术语typedefstruct float realpart； float imagpart；complex；/-存储结构的定义存储结构的定义void GetReal( complex Z, float &realpart )； / 返回复数 Z 的实部值void Getimag( complex Z, float &imagpart )； / 返回复数 Z 的虚部值/-基本操作的函数原型说明基本操作的函数原型说明数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等线性结构线性结构非线性结构非线性结构顺序存储顺序存储链式存储链式存储线性表线性表树形结构树形结构图形结构图形结构小结：数据结构的三个方面：小结：数据结构的三个方面：1.2 基本概念和术语34n预定义常量和类型预定义常量和类型ntypedeftypedef n算法用函数描述算法用函数描述n赋值语句赋值语句n选择语句选择语句n循环语句循环语句1.3 抽象数据类型的表示和实现35n 结束语句结束语句n 输入输出语句输入输出语句n 注释注释n 基本函数基本函数n 逻辑运算逻辑运算本本课课程采用类程采用类C C语言语言( (介于伪代码和介于伪代码和C C语言语言) )描述各描述各种抽象数据类型的表示和实现。种抽象数据类型的表示和实现。预定义常量和类型：预定义常量和类型：/函数结果状态代码函数结果状态代码 #define TRUE #define TRUE 1 1 #define FALSE #define FALSE 0 0 #define OK #define OK 1 1 #define ERROR #define ERROR0 0 #define INFEASIBLE #define INFEASIBLE-1-1 #define OVERFLOW #define OVERFLOW-2-2 typedeftypedef intint Status Status / StatusStatus是函数的类型是函数的类型, ,其值是函数结果状其值是函数结果状态代码态代码 typedeftypedef xxx xxx ElemTypeElemType typedeftypedef：类型定义描述。类型定义描述。361.3 抽象数据类型的表示和实现算法用函数描述：算法用函数描述： 注意注意C+C+中的引用调用。中的引用调用。 例例1:c中的指针调用中的指针调用.void main() int a, b; a=5; b=3; swan(&a, &b); printf(a, b);void swan(int *x, int *y) int temp; temp=*x; *x=*y; *y=temp;例例2:c+中的引用调用中的引用调用.void main() int a, b; a=5; b=3; swan(a, b); printf(a, b);void swan(int &x, int &y) int temp; temp=x; x=y; y=temp;371.3 抽象数据类型的表示和实现赋值语句：赋值语句： 简单赋值：简单赋值： 变量名变量名=表达式；表达式； 串联赋值：串联赋值： 变量名变量名1=变量名变量名2=变量名变量名k=表达式；表达式； 成组赋值：成组赋值： （变量名（变量名1，变量名，变量名k）=（表达式（表达式1，表达式，表达式k）；）； 结构变量名结构变量名=结构变量名；结构变量名； 结构变量名结构变量名= （表达式（表达式1，表达式，表达式k）；）； 变量名变量名 =表达式；表达式； 变量名变量名起始下标起始下标.终止下标终止下标=变量名变量名起始下标起始下标.终止下标终止下标； 交换赋值：交换赋值： 变量名变量名变量名；变量名； 条件赋值：条件赋值： 变量名变量名=条件表达式？表达式条件表达式？表达式T：表达式：表达式F；381.3 抽象数据类型的表示和实现选择语句：选择语句： 条件语句条件语句1：if(表达式表达式)语句；语句； 条件语句条件语句2：if(表达式表达式)语句；语句； else 语句；语句； 开关语句：开关语句： switch(表达式表达式) case 值值1：语句序列语句序列1; break; ；case 值值n ： 语句序列语句序列n; break；default ： 语句序列语句序列n+1; 391.3 抽象数据类型的表示和实现循环语句：循环语句： for循环：循环：for(表达式表达式1; 表达式表达式2; 表达式表达式3) 循环语句循环语句; while 循环：循环：while(条件表达式条件表达式)循环语句循环语句; do-while循环：循环：do 循环语句循环语句; while(条件表达式条件表达式);40结束语句：结束语句： 函数结束：函数结束： return(表达式表达式); 或或 return; case结束：结束：break; 异常结束：异常结束： exit(异常代码异常代码)；1.3 抽象数据类型的表示和实现输入输出语句：输入输出语句： 输入语句：输入语句： scanf(格式串格式串，变量名，变量名1，变量名，变量名n) ； 输出语句：输出语句： printf(格式串格式串，表达式，表达式1，表达式，表达式n) ；41注释：注释： 单行注释：单行注释： / 文字序列文字序列 多行注释：多行注释： /* 文字序列文字序列 */逻辑运算约定：逻辑运算约定：&, | (同同C语言语言)1.3 抽象数据类型的表示和实现基本函数基本函数：max(表达式表达式1,2,n),min(表达式表达式1,2,n),abs(表达式表达式)floor(表达式表达式),ceil(表达式表达式),eof(文件变量文件变量)例：抽象数据类型Triplet表示和实现#defineOK1#defineOVERFLOW-2顺序存储结构顺序存储结构typedefElemType*Triplet;/*由由InitTriplet分配三个元素存储空间分配三个元素存储空间*/基本操作的函数说明基本操作的函数说明StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3)/构造三元组构造三元组T,依次置依次置T的三个元素的初值为的三个元素的初值为v1,v2和和v3StatusGet(TripletT,inti,ElemType&e)/1i3,用用e返回返回T的第的第i元的值元的值基本操作的实现基本操作的实现StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3)T=(ElemType*)malloc(3*sizeof(ElemType);if(!T)exit(OVERFLOW);/分配存储失败分配存储失败T0=v1,T1=v2,T2=v3;returnOK;1.3 抽象数据类型的表示和实现421.4.1 1.4.1 算法算法( (algorithm) )算法：算法：一个有穷的指令集，这些指令为解决某一特定一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。任务规定了一个运算序列。算法的特性：算法的特性：（1 1）有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束（2 2）确定性确定性 每步定义都是确切每步定义都是确切的，同输入则同输出的，同输入则同输出（3 3）可行性可行性 算法由可实现的基本运算构成算法由可实现的基本运算构成（4 4）输入输入 有有0 0个或多个输入个或多个输入（5 5）输出输出 有一个或多个输出有一个或多个输出( (处理结果处理结果) )1.4 算法和算法分析43例：求数组元素例：求数组元素a0到到an的平均值。的平均值。float average(int a, int n) int k; float temp=0.0; if(n=0) printf(“input error!n”); return(0); else for(k=0;kn;k+) temp+=ak; return(“average=%fn”,temp/n); 441.4 算法和算法分析1.4.2 1.4.2 算法设计的要求算法设计的要求(1)(1)正确性正确性(Correctness)(Correctness)：算法应满足具体问题的需求。算法应满足具体问题的需求。(2)(2)可读性可读性(Readability)(Readability)：算法应该好读。以有利于阅读者对算法应该好读。以有利于阅读者对程序的理解。程序的理解。(3)(3)健壮性健壮性(Robustness)(Robustness)：算法应具有容错处理。当输入非法算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。结果。(4)(4)效率与存储量需求：效率与存储量需求：效率指的是算法执行的时间；存储量效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。这两者与问需求指算法执行过程中所需要的最大存储空间。这两者与问题的规模有关。题的规模有关。451.4 算法和算法分析1.4.3 1.4.3 算法效率的度量算法效率的度量事后测试事后测试 采用时间函数计算此算法的执行时间。采用时间函数计算此算法的执行时间。算法的算法的执执行时间通常取决于以下因素：行时间通常取决于以下因素：a. a. 算法选用的策略算法选用的策略b. b. 问题的规模问题的规模c. c. 使用的程序语言使用的程序语言d. d. 编译程序所产生的机器代码的质量编译程序所产生的机器代码的质量e. e. 机器执行指令的速度机器执行指令的速度461.4 算法和算法分析算法本身算法本身问题相关问题相关运行平台运行平台事先分析事先分析 只考虑算法本身只考虑算法本身 事先分析事先分析 假假定定每每条条语语句句的的执执行行时时间间为为单单位位时时间间。算算法法的的时时间间复复杂杂度度是该算法中所有语句的执行频度之和。是该算法中所有语句的执行频度之和。例例1：求两个方阵的乘积：求两个方阵的乘积CA*Bfor(i=0;in;i+)/n+1for(j=0;jn;j+)/n(n+1)Cij=0;/n*nfor(k=0;kn;k+)/n*n*(n+1)Cij+=Aik*Bkj/n*n*n471.4 算法和算法分析频度：频度：语句可能重复执行的最大次数语句可能重复执行的最大次数。问题的规模：问题的规模：算法求解问题的输入量，用整数算法求解问题的输入量，用整数n n表示。表示。 时间复杂度：时间复杂度：一个算法的时间复杂度是该算法的时间耗一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数费，一般地说，时间复杂度是问题规模的函数-T T(n(n) )。渐近时间复杂度：渐近时间复杂度：通常算法中基本操作重复执行的次数通常算法中基本操作重复执行的次数是问题规模是问题规模n n的某个函数的某个函数f(nf(n) )。若。若随着随着n n的增大，算法执的增大，算法执行时间和行时间和f(nf(n) )增长率相同，即增长率相同，即 则记作则记作T(nT(n)= )= O O(f(n(f(n)，称作算法的，称作算法的渐近时间复杂度渐近时间复杂度，简称简称时间复杂度时间复杂度。481.4 算法和算法分析49【定理定理】若若f(nf(n)=a)=am mn nm m+a+am-1m-1n nm-1m-1+ +a+a1 1n+an+a0 0是一个是一个m m次多项次多项 式，则式，则f(nf(n)=)=O(nO(nm m) )。 证明：证明： 所以有所以有f(nf(n)=)=O(nO(nm m) )。1.4 算法和算法分析【推论推论】时间复杂度由频度的时间复杂度由频度的最高阶项最高阶项来决定。来决定。2 2、一般情况下，对循环语句只考虑循环体语句的执行次数，而、一般情况下，对循环语句只考虑循环体语句的执行次数，而忽略该语句中步长加一、终值判别、循环转移等成份。因此，忽略该语句中步长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。的循环语句中最内层语句的频度所决定的。例例2：x=0;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k1&change;-i)change=FALSE;for(j=0;jaj+1)ajaj+1;change=TURE;最好情况：最好情况：0 0次；最坏情况：次；最坏情况：1+2+3+1+2+3+n-1=n(n-1)/2+n-1=n(n-1)/2。平均时间复杂度为平均时间复杂度为:O(n:O(n2 2) )1.4 算法和算法分析以下是最常用的计算算法时间的多项式，其关系为：以下是最常用的计算算法时间的多项式，其关系为： O(1)O(1)O(lognO(logn)O(nO(n)O(nlognO(nlogn)O)O(n(n2 2)O(n)O(n3 3)O(2)O(2n n)O(nO(n!)!)O(nO(nn n) )2n5n2100n200log2nn3531.4 算法和算法分析54 下表给出了复杂性为下表给出了复杂性为f(f(n n) )的程序在每秒执行的程序在每秒执行1010亿亿条指令的计算机上执行时所需要的时间。条指令的计算机上执行时所需要的时间。1.4 算法和算法分析1.4.4 1.4.4 算法的存储空间需求算法的存储空间需求 空间复杂度空间复杂度: :算法所需存储空间的度量，记作算法所需存储空间的度量，记作: : S(nS(n)=)=O(f(nO(f(n) ) 其中其中n n为问题的规模为问题的规模( (或大小或大小) )。例：数组逆序问题。例：数组逆序问题。 算法算法1 1：for(ifor(i=0; in; i+) bn-i-1=0; in; i+) bn-i-1=aiai; for(ifor(i=0; in; i+) =0; in; i+) aiai=bibi; 该算法需额外使用该算法需额外使用n n个存储单元，个存储单元，S(nS(n)= )= O(nO(n) ) 算法算法2 2：for(ifor(i=0; in/2; i+)=0; in/2; i+) x= x=aiai; ; aiai=an-i-1; an-i-1=x; =an-i-1; an-i-1=x; 该算法需额外使用该算法需额外使用1 1个存储单元，个存储单元，S(nS(n)= O(1)= O(1)551.4 算法和算法分析