《数据结构第1次课第一章基本概念(更改的)》由会员分享，可在线阅读，更多相关《数据结构第1次课第一章基本概念(更改的)（59页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 绪论绪论 计算机是一门研究利用计算机进行信息表示和处理的科学。涉计算机是一门研究利用计算机进行信息表示和处理的科学。涉及：及： 信息的表示信息的表示 信息的处理信息的处理 而信息的表示又直接关系到处理信息的程序的效率。随着计而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个个“好好”的程序，必须分析待处理的对象的特征及各对象之间存的程序，必须分析待处理的对
2、象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。在的关系，这就是数据结构这门课所要研究的问题。数据结构数据结构-独立的学科始于独立的学科始于19681968年，但在此之前有关内容已散见年，但在此之前有关内容已散见 于编译原理和操作系统的教材之中。于编译原理和操作系统的教材之中。 -1968 -1968年，美国的图灵奖年，美国的图灵奖”获得者克努特（获得者克努特（D.E.KnuthD.E.Knuth）开创课程体系。）开创课程体系。为什么要学习数据结构？为什么要学习数据结构？1、电子计算机的主要用途：、电子计算机的主要用途： 计算机是一门研究利用计算机进行信息表示和处理的计算机
3、是一门研究利用计算机进行信息表示和处理的科学。涉及：科学。涉及：信息的表示信息的表示和和信息的处理。信息的处理。早期：早期： 主要用于数值计算。主要用于数值计算。后来：后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。具有一定结构关系的数据）。 提高提高程序的效率、编写出一个程序的效率、编写出一个“好好”的程序。必须分的程序。必须分析待处理的对象的特征及各对象之间存在的关系，这就是析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。数据结构这门课所要研究的问题。第一章第一章 绪论绪论用计算机
4、解决问题的过程用计算机解决问题的过程建立模型建立模型构造求解算法构造求解算法选择存储结构选择存储结构编写程序编写程序测试测试描述问题的描述问题的共性共性描述问题的求描述问题的求解方法解方法将问题涉及的数据将问题涉及的数据存储到计算机中存储到计算机中分析问题的过程分析问题的过程数据结构的作用数据结构的作用进行更为复杂的算进行更为复杂的算法设计法设计选择合理的存储选择合理的存储结构结构提高编程技术提高编程技术数据结构课程的形成和发展数据结构课程的形成和发展形成阶段形成阶段l6060年代初期，年代初期，“数据结构数据结构”有关的内容散见于操作系有关的内容散见于操作系统、编译原理和表处理语言等课程。统
5、、编译原理和表处理语言等课程。l19681968年，美唐纳德年，美唐纳德克努特克努特(Donald Ervin Knuth)(Donald Ervin Knuth)教教授开创了数据结构的最初体系，授开创了数据结构的最初体系，计算机程序设计技计算机程序设计技巧巧第一卷第一卷基本算法基本算法 ，“数据结构数据结构”被列入美国被列入美国一些大学计算机科学系的教学计划。一些大学计算机科学系的教学计划。发展阶段：发展阶段：l数据结构的概念不断扩充，包括了网络、集合代数论、数据结构的概念不断扩充，包括了网络、集合代数论、关系等关系等“离散数学结构离散数学结构”的内容。的内容。l7070年代后期，年代后期，
6、8080年代初，我国高校陆续开设该课程。年代初，我国高校陆续开设该课程。介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门核心课程。一门核心课程。数据结构课程数据结构课程所处的地位：所处的地位：学习提要学习提要掌握本课程所涉及到的基本名词、术语和掌握本课程所涉及到的基本名词、术语和概念，特别是数据的概念，特别是数据的逻辑结构逻辑结构和和存储结构存储结构之间的关系及性质。之间的关系及性质。了解抽象数据类型的定义、表示和实现方了解抽象数据类型的定义、表示和实现方法。法。理解理解算法设计的五个要素算法设计的五个要素和基本要求；掌和基本要求；掌握算法效率的度量方法
7、，着重学习算法的握算法效率的度量方法，着重学习算法的时间复杂度时间复杂度分析。分析。教学重点教学重点数据、数据元素、数据项；数据、数据元素、数据项；逻辑结构和存储结构在概念上的联系与区逻辑结构和存储结构在概念上的联系与区别；别；数据结构及其三个组成部分；数据结构及其三个组成部分；抽象数据类型和数据抽象；抽象数据类型和数据抽象；评价算法优劣的标准及方法。评价算法优劣的标准及方法。1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 算法和算法的衡量算法和算法的衡量 1.4.1 算法算法 1.4.2 算法设计的要求算
8、法设计的要求 1.4.3 算法效率的度量算法效率的度量 1.4.4 算法的存储空间的需求算法的存储空间的需求1.1 1.1 什么是数据结构什么是数据结构什么是数据结构什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大众所周知，计算机的程序是对信息进行处理。在大众所周知，计算机的程序是对信息进行处理。在大众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数多数情况下，这些信息并不是没有组织的，信息（数多数情况下，这些信息并不是没有组织的，信息（数多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构据）之间往往
9、具有重要的结构关系，这就是数据结构据）之间往往具有重要的结构关系，这就是数据结构据）之间往往具有重要的结构关系，这就是数据结构的内容。的内容。的内容。的内容。(数据结构在软件开发中的地位数据结构在软件开发中的地位)系统分析系统分析系统设计系统设计系统实现系统实现系统维护系统维护系统设计系统设计1.1 1.1 什么是数据结构什么是数据结构什么是数据结构什么是数据结构Niklaus Wirth Algorithm + Data Structures = Programs程序程序: :算法算法: : 数据结构数据结构: : 为计算机处理问题编制的为计算机处理问题编制的 一组指令集一组指令集 处理问题
10、的策略处理问题的策略问题的数学模型问题的数学模型( (信息表示信息表示) ) 一元二次方程求解一元二次方程求解 例如例如: : 数值计算的程序设计问题数值计算的程序设计问题 代数方程组代数方程组 环流模式方程环流模式方程 ( (球面坐标系球面坐标系) )全球天气预报全球天气预报 例一：电话号码查询系统例一：电话号码查询系统算法：算法：? ?模型：模型：? ?设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N N N N个人的名字和其相应的电话号个人的名字和其相应的电话号个人的名字和其相应的电话号个人的名字和其相应的电话号码，假定按
11、如下形式安排：码，假定按如下形式安排：码，假定按如下形式安排：码，假定按如下形式安排： (a1(a1(a1(a1，b1) (a2b1) (a2b1) (a2b1) (a2，b2)b2)b2)b2)(an(an(an(an，bnbnbnbn) ) ) )其中其中其中其中( ( ( (aiaiaiai，bi)(ibi)(ibi)(ibi)(i=1=1=1=1，2 2 2 2n) n) n) n) 分别表示某人的名字和对应的电话号分别表示某人的名字和对应的电话号分别表示某人的名字和对应的电话号分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能码。要求设计一个算法
12、，当给定任何一个人的名字时，该算法能码。要求设计一个算法，当给定任何一个人的名字时，该算法能码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，够打印出此人的电话号码，如果该电话簿中根本就没有这个人，够打印出此人的电话号码，如果该电话簿中根本就没有这个人，够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。则该算法也能够报告没有这个人的信息。则该算法也能够报告没有这个人的信息。则该算法也能够报告没有这个人的信息。线性表线性表(N个人的信息个人的信息)非数值计算的程序设计问题非数值计算的程序设计问
13、题例二：人机对弈问题例二：人机对弈问题算法：算法：? ?模型：模型：? ?树树(棋盘和棋子棋盘和棋子)例三：铺设城市的煤气管道例三：铺设城市的煤气管道算法：算法：? ?模型：模型：? ?如何规划使得总投资如何规划使得总投资花费最少花费最少？图图(城市铺设点和铺设成本城市铺设点和铺设成本)概括地说，概括地说， 数据结构是一门研究非数值计数据结构是一门研究非数值计算的程序设计问题中计算机的操算的程序设计问题中计算机的操作对象以及它们之间的关系和操作对象以及它们之间的关系和操作等的学科。作等的学科。1.2 基本概念和术语基本概念和术语一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽
14、象数据类型三、抽象数据类型一、数据与数据结构一、数据与数据结构 所有能所有能被输入被输入到计算机中，且能被计到计算机中，且能被计算机算机处理的处理的符号符号( (数值、字符等数值、字符等) )的集合。的集合。数据数据: :是是计算机操作的对象计算机操作的对象的总称。的总称。 是计算机处理的是计算机处理的信息的信息的某种特定的某种特定的符号符号表示形式表示形式。 是数据（集合）中的一个是数据（集合）中的一个“个体个体”, ,在计算机中通常作为一个整体进在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论行考虑和处理。是数据结构中讨论的的基本基本单位。单位。数据元素数据元素: :如如: :整
15、数整数5 5, ,字符字符N N等。等。 -是不可分割的是不可分割的“原子原子” 其中每个款项称为一个其中每个款项称为一个“数据项数据项”它是数据结构中讨论的它是数据结构中讨论的最小最小单位单位数据元素也可以由若干款项构成。数据元素也可以由若干款项构成。例如：例如：描述一个学生的数据元素描述一个学生的数据元素称之为组合项称之为组合项年年 月月 日日姓姓 名学名学 号班号班 号性别出生日期入学成绩号性别出生日期入学成绩数据结构：数据结构：带带结构结构的数据元素的集合的数据元素的集合有一个特性相同的数据元素的集合，有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种如果在数据元素之间存
16、在一种或多种特定的关系，则称为一个数据结构。特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系指的是数据元素之间存在的关系例如，当用例如，当用三个三个 4 位的十进制数位的十进制数表示一表示一个含个含 12 位数的十进制数时，位数的十进制数时，3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素则在数据元素 a1、a2 和和 a3 之间存在着之间存在着“次序次序”关系关系 a1, a2 、 a2, a3 3214，6587，9345 6587，3214，9345例如例如: :a1 a2 a3a2 a1 a3又例，在又例，在 2 行行 3 列的
17、二维数组列的二维数组中六个元素中六个元素a1, a2, a3, a4, a5, a6之间存在两个关系之间存在两个关系:行的次序关系行的次序关系: :row = ,col = , a1 a2 a3 a4 a5 a6列的次序关系列的次序关系: : 若在若在 6 个数据元素个数据元素a1, a2, a3, a4, a5, a6 之间存在如下的之间存在如下的次序关系次序关系:| i=1, 2, 3, 4, 5 数据结构是数据结构是相互之间存在着某种逻辑相互之间存在着某种逻辑关系关系的数据元素的集合的数据元素的集合。可见，不同的可见，不同的“关系关系”构成不同的构成不同的“结构结构”则构成一维数组的定义
18、。则构成一维数组的定义。从从关系关系或或结构结构分分，数据结构，数据结构可归结为可归结为以下以下四类四类: :线性线性结构结构: :树形树形结构结构图状图状结构结构集合集合结构结构结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存在一对一的关系。在一对一的关系。在一对一的关系。在一对一的关系。结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存在一对多的关系。在一对多的关系。在一对多的关系。在一对多的关系。结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存结构中的数据元素之间存在多对多的关系。在多对多的关
19、系。在多对多的关系。在多对多的关系。结构中的数据元素除了同结构中的数据元素除了同结构中的数据元素除了同结构中的数据元素除了同属于一种类型外，别无其属于一种类型外，别无其属于一种类型外，别无其属于一种类型外，别无其它关系。它关系。它关系。它关系。数据结构包括数据结构包括“逻辑结构逻辑结构” 和和“物理结物理结构构”两个方面两个方面( (层次层次):):逻辑结构逻辑结构 是对数据元素之间的逻辑关系是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示定义在此集合上的若干关系来表示;(;(形式形式定义）定义）物理结构物理结构
20、是逻辑结构在计算机中的表示是逻辑结构在计算机中的表示和实现，故又称和实现，故又称“存储结构存储结构” 。数据结构的形式定义描述为数据结构的形式定义描述为: :数据结构数据结构是一个二元组是一个二元组（逻辑结构）（逻辑结构） Data_Structures = (D, S)其中其中: :D 是是数据元素的有限集数据元素的有限集， S 是是 D上上关系的有限集关系的有限集。数据的数据的存储结构存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象“数据元素数据元素”的映象的映象 ？“关系关系”的映象的映象 ？数据元素的映象方法：数据元素的映象方法：用二进制位用二进制位(bit)(bit)的位串
21、表示数据元素的位串表示数据元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2A A的的ASCIIASCII码是码是6565关系的映象方法：关系的映象方法：（表示（表示 x, y 的方法的方法）顺序映象顺序映象以相邻的存储位置表示后继关系以相邻的存储位置表示后继关系例如例如: :令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置之间差一个常量之间差一个常量 C C而而 C C 是一个隐含固定值，是一个隐含固定值，整个存储结构整个存储结构中只含数据元素本身的信息中只含数据元素本身的信息 x yx yC C链式映象
22、链式映象以附加信息以附加信息( (指针指针) )表示后继关系表示后继关系需要用一个和需要用一个和 x x 在一起的在一起的附加信息附加信息指示指示 y y 的存储位置的存储位置y xy x在不同的编程环境中在不同的编程环境中 存储结构可有不同的描述方法。存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型常可用高级编程语言中提供的数据类型描述之。描述之。例如：以三个带有次序关系的整数表示例如：以三个带有次序关系的整数表示一个长整数时，可利用一个长整数时，可利用C+语言中提供语言中提供的整数数组类型，定义长整数为：的整
23、数数组类型，定义长整数为： int long_int3;二、数据类型二、数据类型 在用高级程序语言编写的程序中，必在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表须对程序中出现的每个变量、常量或表达式，明确说明它们所达式，明确说明它们所属的数据类型。属的数据类型。 数据在真正用程序进行操作时，还必须对其进行类型分类。所以从抽数据在真正用程序进行操作时，还必须对其进行类型分类。所以从抽象数据类型的观点来讨论数据结构，已称为一种新的趋势，越来越被象数据类型的观点来讨论数据结构，已称为一种新的趋势，越来越被人们所重视。人们所重视。每个类型隐含或明显规定了在程序执行期间其变量或表达式
24、允许取值每个类型隐含或明显规定了在程序执行期间其变量或表达式允许取值的范围以及允许进行操作。的范围以及允许进行操作。整型数据类型：值的集合整型数据类型：值的集合整型数据类型：值的集合整型数据类型：值的集合N N2, 2,1,0,1,21,0,1,2一组操作：、一组操作：、一组操作：、一组操作：、x x、/ /、%等等等等数据类型：基本类型和构造类型数据类型：基本类型和构造类型数据类型：基本类型和构造类型数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定
25、义构造类型：数组、结构、联合、指针、枚举型、自定义构造类型：数组、结构、联合、指针、枚举型、自定义构造类型：数组、结构、联合、指针、枚举型、自定义数据对象数据对象数据对象数据对象：某种数据类型元素的集合。：某种数据类型元素的集合。：某种数据类型元素的集合。：某种数据类型元素的集合。例例例例3 3 3 3、整数的数据对象是、整数的数据对象是、整数的数据对象是、整数的数据对象是-3-3-3-3，-2-2-2-2，-1-1-1-1，0 0 0 0，1 1 1 1，2 2 2 2，3 3 3 3，英文字符类型的数据对象是英文字符类型的数据对象是英文字符类型的数据对象是英文字符类型的数据对象是 A A
26、A A，B B B B，C C C C，D D D D，E E E E，F F F F， 数据类型数据类型 是一个值的集合和定义在此集合上的是一个值的集合和定义在此集合上的一组操作的总称。一组操作的总称。 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现每个类型隐含或明显规定了在程序每个类型隐含或明显规定了在程序执行期间其变量或表达式允许取值的范执行期间其变量或表达式允许取值的范围以及允许进行操作。围以及允许进行操作。例如：整型例如：整型值的范围是：值的范围是：-32768 32767操作是：操作是：+，-，*，/，%数数据据类类型型的的抽抽象象性性：各各种种高高级级程程序序设设计计语
27、语言言中中都都拥拥有有“整整数数”类类型型，尽尽管管它它们们在在不不同同处处理理器器上上实实现现的的方方法法不不同同，但但对对程程序序员员而而言言是是“相相同同的的”，因因为为它它们们的的数学特性相同。数学特性相同。从从“数学抽象数学抽象”的角度看，可称它为一的角度看，可称它为一个个“抽象数据类型抽象数据类型” 。三、抽象数据类型三、抽象数据类型 ( (Abstract Data Type 简称简称ADT) ) 是指一个数学模型（数据结构）以及是指一个数学模型（数据结构）以及定义在此数学模型上的一组操作定义在此数学模型上的一组操作抽象数据类型是数据类型的扩展和抽象：抽象数据类型是数据类型的扩展
28、和抽象：数据结构（数据对象数据结构（数据对象D D及其关系及其关系S S）定义在数据结构上的基本操作和算法（定义在数据结构上的基本操作和算法（P P）ADT（抽象数据类型的两个重要特征）（抽象数据类型的两个重要特征）数据抽象数据抽象：用：用ADT描述程序处理的实体时，描述程序处理的实体时，强调的是其本质的特征，其所能完成的功强调的是其本质的特征，其所能完成的功能以及它和外部用户的接口（即外界使用能以及它和外部用户的接口（即外界使用它的方法）。它的方法）。数据封装数据封装：将实体的外部特性和其内部实：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部现细节分离，并且对外部用户隐藏其内
29、部实现细节。如复数定义实现细节。如复数定义例如，定义抽象数据类型例如，定义抽象数据类型“复数复数” 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分是复数的实数部分, , | e2 是复数的虚数部分是复数的虚数部分 ADT Complex 基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作结果：构造复数操作结果：构造复数 Z,Z,其实部和虚部其实部和虚部 分别被赋以参数分别被赋以参数 v1 v1 和和 v2 v2 的值。的值。 DestroyComplex( &Z)操作结果：复数操作结果：复数Z Z被
30、销毁。被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用realPart返回复数返回复数Z Z的实部值。的实部值。 GetImag( Z, &ImagPart )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用ImagPart返回复数返回复数Z Z的虚部值。的虚部值。 Add( z1,z2, &sum )初始条件：初始条件：z1, z2是复数。是复数。操作结果：用操作结果：用sum返回两个复数返回两个复数z1, z2 的的 和值。和值。 ADT Complex抽象数据类型的描述方法抽象数据类型的描述方
31、法抽象数据类型可用抽象数据类型可用（D，S，P）三元组表示三元组表示其中，其中，D 是数据对象，是数据对象， S 是是 D 上的关系集，上的关系集， P 是对是对 D 的基本操作集。的基本操作集。 ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名其中基本操作的定义格式为其中基本操作的定义格式为: :基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件：初始条件描述初始条件描述 操作结果：操作结果：操作结果描述操作
32、结果描述 赋值参数赋值参数 指为操作提供输入值；指为操作提供输入值；引用参数引用参数 以以&打头，除可提供输入值外，打头，除可提供输入值外，还将返回操作结果。还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。作失败，并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后，数说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若据结构的变化状况和应返回的结果。若初始条件为空，则省略之。初始条件为空，则省略之。抽象数据类型的表示和实现抽象数据类型的表示和
33、实现抽象数据类型需要通过固有数据类型抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）（高级编程语言中已实现的数据类型）来实现。来实现。算法与程序的主要区别在于一个程序通常是用某种程序语言书写的一个计算过程算法与程序的主要区别在于一个程序通常是用某种程序语言书写的一个计算过程，而一个算法则并不一定表现为一个计算机程序，它可以用不同方式和不同语言，而一个算法则并不一定表现为一个计算机程序，它可以用不同方式和不同语言来描述。来描述。一个算法可采用自然语言如英语、汉语描述，也可以采用图形方式如流程图、拓一个算法可采用自然语言如英语、汉语描述，也可以采用图形方式如流程图、拓扑图描述；如
34、果算法用各种计算机语言描述，那么就表现为一个程序。扑图描述；如果算法用各种计算机语言描述，那么就表现为一个程序。1.4 算法和算法分析算法和算法分析算法算法：是对特定问题求解步骤的一种描述，是指令的有限序列，：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。其中每一条指令表示一个或多个操作。 算法具有以下五个特性：算法具有以下五个特性：（1）有穷性有穷性 一个算法必须总是在执行有穷步之后结束，且每一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。一步都在有穷时间内完成。（2）确定性确定性 算法中每一条指令必须有确切的含义。不存在二义算法中每一
35、条指令必须有确切的含义。不存在二义性。性。（3）可行性可行性 一个算法是可行的。即算法描述的操作都是可以通一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。过已经实现的基本运算执行有限次来实现的。（4）输入输入 一个算法有零个或多个输入，这些输入取自于某个特一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。定的对象集合。（5）输出输出 一个算法有一个或多个输出，这些输出是同输入有着一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。某些特定关系的量。1.4.2 1.4.2 算法设计的要求算法设计的要求评价一个好的算法有以下几个标准评价一个
36、好的算法有以下几个标准: :(1)(1)正确性正确性: :算法应满足具体问题的需求。算法应满足具体问题的需求。(2)(2)可读性可读性: :算法应该好读。以有利于阅读者对程序的理解。算法应该好读。以有利于阅读者对程序的理解。(3)(3)健状性健状性: :算法应具有容错处理。当输入非法数据时，算法应算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。对其作出反应，而不是产生莫名其妙的输出结果。(4)(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者需求指
37、算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。执行时间少，存储空间小。与问题的规模有关。执行时间少，存储空间小。1.4.3 算法效率的度量算法效率的度量 对一个算法要作出全面的分析可分成两种方法：对一个算法要作出全面的分析可分成两种方法：事先分析事先分析 求出该算法的一个时间界限函数求出该算法的一个时间界限函数事后统计事后统计 收集此算法的执行时间和实际占用空间的收集此算法的执行时间和实际占用空间的统计资料。缺陷：一是必须先运行依据算法编制的程统计资料。缺陷：一是必须先运行依据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软序；二是所得时间的统计量依赖于计算机的硬
38、件、软件等环境因素，有时容易掩盖算法本身的优劣。件等环境因素，有时容易掩盖算法本身的优劣。和算法执行时间相关的因素：和算法执行时间相关的因素：1 1算法选用的策略算法选用的策略2 2问题的规模问题的规模3 3编写程序的语言编写程序的语言4 4编译程序产生的机器代码的质量编译程序产生的机器代码的质量5 5计算机执行指令的速度计算机执行指令的速度事先分析事先分析但同一个算法用不同的语言实现，或者用不同的编译程序进行编译，但同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。因此，使用绝对的时间或者在不同的计算机上运行时，效率均不相同。因此，使用绝对的
39、时间单位衡量算法的效率是不合适的。应撇开这些与计算机硬件、软件有关的因素，单位衡量算法的效率是不合适的。应撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法可以认为一个特定算法“运行工作量运行工作量”的大小，只依赖于问题的规模（通常用整数的大小，只依赖于问题的规模（通常用整数n n表示），或者说，它是问题规模的函数。表示），或者说，它是问题规模的函数。 一个特定一个特定算法的算法的“运行工作量运行工作量”的大小，只依赖于的大小，只依赖于问题的规模问题的规模（通常用整数量（通常用整数量n表示），或者说，表示），或者说，它是问题规模的函数。它是问题规模的函数。例、例、for(i=1;i=n
40、;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 一般情况下，算法中基本操作一般情况下，算法中基本操作重复执行的次数重复执行的次数是问是问题规模题规模n的某个函数的某个函数f(n)，算法的时间量度记作，算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模它表示随问题规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称时的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。间复杂度。 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，
41、则总次数为则总次数为: nnn=n3，时间复杂度为时间复杂度为T(n)=O(n3) 为了便于比较同一问题的不同算法，通常的做法是，为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来从算法中选取一种对于所研究的问题（或算法类型）来说是说是基本操作基本操作的原操作，以该操作重复执行的次数作为的原操作，以该操作重复执行的次数作为算法的时间量度。算法的时间量度。语句重复执行的次数也称为语句的语句重复执行的次数也称为语句的频度频度：例例 +x;s=0; 将将x自增看成是基本操作，则语句频度为，即时间复杂度为自增看成是基本操作，则语句频度为，即时间复杂度为(1)
42、 如果将如果将s=0也看成是基本操作，则语句频度为也看成是基本操作，则语句频度为1，其时间复杂度，其时间复杂度仍为仍为(1)，即常量阶。，即常量阶。例例 for(i=1;i=n;+i) +x;s+=x; 语句频度为：语句频度为：n其时间复杂度为：其时间复杂度为：O(n) 即时间复杂度为线性阶。即时间复杂度为线性阶。显然，呗称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，显然，呗称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。多数情况下它是最深层循环内的语句中
43、的原操作，它的执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。语句的频度指的是该语句重复执行的次数。i=0: 赋值次赋值次i=1: 赋值赋值 2 次次i=2: 赋值赋值3次次i=n-1:赋值赋值n次次.+1+2+3+n=(1+n)n/2=n2/2+n/2例例 for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 语句频度为：语句频度为：n2其时间复杂度为：其时间复杂度为：O(n2) 即时间复杂度为平方阶。即时间复杂度为平方阶。例例 for(i=0;i=n-1;+i) for(j=0;j=i;+j)aij=0; 其时间复杂度为：其时间复杂度为：O
44、(n2) 即时间复杂度为平方阶。即时间复杂度为平方阶。 取语句频度增长最快的项。取语句频度增长最快的项。一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为零次多项式）来限界。而一个时间为O(n2)O(n2)的算法的算法则由一个二次多项式来限界。则由一个二次多项式来限界。 以下几种计算算法时间的多项式是最常用的。其关以下几种计算算法时间的多项式是最常用的。其关系为：系为： 指数时间的关系为：指数时间的关系为： O(2n)O(n!)0 ;
45、i-) for(j=0;jaj+1) aj aj+1; 最好情况：最好情况：0次次 最坏情况：每次都换，最坏情况：每次都换， (n2) 由小到大排列由小到大排列i=n-1: j从从0到到n-2 交换交换n-1次次.+(n-1)+(n-2)+(n-3)+1=(n-1)n/2=n2/2-n/2i=n-2: j从从0到到n-3 交换交换n-2次次i=n-3: j从从0到到n-4 交换交换n-3次次i=1: j从从0到到0 交换交换1次次平均时间复杂性假设每种情况出现的概率相等，但很多情况下难以确定。平均时间复杂性假设每种情况出现的概率相等，但很多情况下难以确定。注意：时间与空间往往是对矛盾，要综合考
46、虑。注意：时间与空间往往是对矛盾，要综合考虑。1.4.4算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作: S(n)=O(f(n) 其中其中n为问题的规模为问题的规模(或大小或大小)1输入数据所占空间输入数据所占空间2程序本身所占空间程序本身所占空间；3辅助变量所占空间辅助变量所占空间。本章学习要点本章学习要点1.熟悉各名词、术语的含义，掌握基本概念；熟悉各名词、术语的含义，掌握基本概念；2.理解算法五个要素的确切含义；理解算法五个要素的确切含义；3.掌握计算语句频度和估算算法时间复杂度掌握计算语句频度和估算算法时间复杂度的方法
47、。的方法。练习练习1. 下面程序的时间复杂度为下面程序的时间复杂度为_。O(mO(m*n)*n)第一个第一个forfor循环执行循环执行m m次，第二个次，第二个forfor循环执行循环执行n n次，两个次，两个forfor循环嵌套起来共执行循环嵌套起来共执行m * nm * n次。次。练习练习2. 2. 下面程序的时间复下面程序的时间复下面程序的时间复下面程序的时间复杂度为杂度为杂度为杂度为_。O(logO(log2 2n)n)3. 比较两个复杂度之间的关系（当比较两个复杂度之间的关系（当n趋向于趋向于无穷大时）无穷大时） 此处语句为此处语句为I = I * 2I = I * 2，循环次数，循环次数k k满足满足2 2的的K K次幂次幂= n= n，即，即k = long2nk = long2n。作业：作业：. 计算时间复杂度计算时间复杂度 sum=1; for(i=0;sumn;i+) sum+=i;2. 计算时间复杂度计算时间复杂度 i = 1; while( i = n) i = i +2;。
