算法与数据结构C语言描述(第2版)电子教案-第1章-绪论课件.ppt

《算法与数据结构C语言描述(第2版)电子教案-第1章-绪论课件.ppt》由会员分享，可在线阅读，更多相关《算法与数据结构C语言描述(第2版)电子教案-第1章-绪论课件.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构C语言描述（第二版）张乃孝高等教育出版社2006年1月“算法数据结构程序算法数据结构程序”程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。算法与数据结构是程序设计中相辅相成、不可分割的两个方面。抽象数据类型抽象数据类型有一定行为（操作）的抽象（数学）类型。抽抽象象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏隐藏起来。支持数据类型的实现与使用分离的原则，是一种十分有效的对问题进行抽象与分解的思维工具。是面向对象面向对象技术与方法的主要理论基础。数据结构“数据结构是抽象数据类型的物理抽象数据类型的物理实现实现”。解决：1）如何具体表示抽象数据类型中的数

2、学模型；2）如何具体实现抽象数据类型中操作。学习目的理解数据结构和算法的概念；掌握设计数据结构与算法的主要原理和方法；比较不同数据结构和算法的特点。提高学生使用计算机解决问题的能力。第一章第一章 绪绪 论论本章重点：理解从问题到程序的主要过程；体会抽象数据类型、数据结构和算法在问题求解过程中的作用；了解数据结构的主要概念和分类；了解算法的概念和主要设计、分析方法。1.1从问题到程序用计算机解决（一种）实际问题，就是在计算机中建立一个解决问题的模型。程序是使用程序设计语言精确描述的实现模型，它是问题求解的一个可以在计算机上运行的模型。程序中描述的数据用来表示问题中涉及的对象，程序中描述的过程表示

3、了对于数据的处理算法；通过接受（具体）实际问题的输入，经过程序的运行，便可以得到实际问题的一个解。问题求解（1）分析阶段。弄清用户的需求是什么，设计者根据它进行深入分析，使用规范说明语言（或数学语言等工具）给出系统的需求模型（或数学模型）。问题求解（2）设计阶段设计阶段（本课讨论的重点本课讨论的重点）。建立求解系统的实现模型，重点是算法的设计和数据结构的设计。对于大型的复杂的系统，还包括抽象数据类型或者模块的设计。一般而言，设计过程需要从粗到细，经过多次精化才能完成。问题求解（3）编码阶段。根据设计的要求，采用适当的程序设计语言（C语言、C+语言或Java语言），编写出可执行的程序。问题求解（

4、4）测试和维护。发现和排除在前几个阶段中产生的错误，经测试通过的程序便可投入运行，在运行过程中还可能发现隐含的错误和问题，因此还必须在使用中不断维护和完善。1.1.1问题分析与抽象为了能正确地解决问题，必须首先深刻地理解需要解决的问题。只有在深刻地认识了这个问题以后，才能着手确定这个问题的解决方法。信号灯问题：为这个路口设计一个安全有信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统。效的交通信号灯的管理系统。信号灯问题分析分析所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求：使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。信号

5、灯问题分析可以确定13个可能通行方向：AB，AC，AD，BA，BC，BD，DA，DB，DC，EA，EB，EC，ED。交叉路口行驶冲突的抽象（不能同时行驶的用线连接）信号灯问题抽象要求将图1.2中的结点分组，使有线相连(互相冲突)的结点不在同一个组里。这个问题的解有许多“可行解可行解”。我们希望能够设计一个最佳（分组数最少）的方案。称作“最优解最优解”。着色问题经典问题把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出（最少）要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。1.1.2程序的设计与实现一个问题的解决可以有

6、许多办法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的办法，比较快而且准确地计算出需要的结果。选择算法穷举法具体做法：从分为1、2、3组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。穷举法的分析这类穷举法对结点少的问题(称为“规模小的”问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。贪心法贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。贪心法的一个解(1)

7、红色：ABACADBADCED(2)蓝色：BCBDEA(3)绿色：DADB(4)白色：EBEC抽象数据类型的选择为了便于给出上述算法的实现，可以按照抽象数据类型的观点，先把被处理的对象加以抽象。在着色问题中具体解决：使用什么抽象数据类型来表示地图，以及使用什么样的抽象数据类型表示一组国家等。抽象数据类型的选择使用一个图图（图是图论图论研究的对象，也是一种重要的抽象数据类型。）表示地图。使用国名（图中结点名）的集合集合表示国家的分组。假设需要着色的图是G，G中所有结点的集合记为G.V，集合V1存放图中所有未被着色的结点，集合NEW存放可以用某颜色着色的所有结点。贪心法的描述贪心法的描述从V1中找

8、出可用新颜色着色的结点集的工作可以用下面的伪码描述：置NEW为空集合;for每个vV1doifv与NEW中所有结点间都没有边从V1中去掉v;将v加入NEW;这个伪码如果能执行，集合NEW中就得到一组可以用新颜色着色的结点。着色程序可以反复调用这段伪码，直到V1为空，每次调用选择一种新颜色，这段伪码执行的次数就是需要的不同颜色个数。假设（ADT）集合和图支持下面行为：判断元素v是否属于集合V1表示为vV1；从集合V1中去掉一个元素v表示为remove(V1,v)；向集合NEW里增加一个元素v用add(NEW,v)表示，判断集合V1是否空集合表示为isEmpty(V1)检查结点v与结点集合NEW中

9、各结点之间在图G中是否有边连接，用函数notAdjacentWith(NEW,v,G)表示。抽象的抽象的着色算法着色算法intcolorUp(GraphG)intcolor=0;/记录使用的颜色数setV1=G.V;/V1初始化为图G的结点集VsetNEW;while(!isEmpty(V1)NEW=;while(vV1.notAdjacentWith(NEW,v,G)add(NEW,v);remove(V1,v);+color;returncolor;/返回使用的颜色数数据结构的设计如果集合和图是程序设计语言中预定义的类型，则colorUp中用到的remove(V1,v)和add(NEW,v

10、)等就应该是语言中预定义的内部函数，该程序就几乎可以直接上机运行。否则程序员需要自己用语言所提供的（类型）机制实现这些抽象数据类型（集合、图等），这些正是数据结构设计要讨论的内容。算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的数据结构进行精化。如果这个问题仍然是个比较复杂的问题，就还需要选择算法，也可能存在需要新抽象数据类型和数据结构。经过这种反复的精化过程，最后将算法中所有部分都细化为能用程序设计语言描述的成分，得到的就是我们希望的程序。1.2抽象数据类型抽抽象象数数据据类类型型的的概概念念最最早早出出现现在在20世世纪纪70年年代代，它它是是面面向向对对象象方方法法的的重重要

11、要理理论论基础。基础。本本书书在在内内容容的的组组织织中中仅仅仅仅使使用用了了抽抽象象数数据据类类型型的的概概念念，而而没没有有严严格格采采用用面面向向对对象象的的程程序序设设计计语语言言的的描描述述机机制制（例例如如class）。）。基本概念类型类型（type）是一组值（或者对象）的集合。例如：布尔作为一种类型是由真（true）和假（false）两个值组成的集合；布尔向量也可以作为一种类型，它的每个值是一个由true或false构成的向量。基本概念数据类型数据类型（datatype）通常是指在计算机（语言）中可以使用的一个类型，它不但包括这个类型的值的集合，还包括定义在这个类型上的一组操作。

12、例如：整数作为一个数据类型是指在计算机上所能表示的（不是数学意义上任意大小的）所有整数和语言中定义的对于这些整数的全部操作（整数的加、减、乘、除、取余等）。基本概念抽象数据类型抽象数据类型抽象数据类型（AbstractDataType简称为ADT）可以定义作具有一定行为(操作)的抽象（数学）类型。它不关心不关心类型中值的具体表示方式和数据类型中定义的各种操作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象抽象。意义和作用（1）抽象数据类型的实质是抽象抽象出了数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏隐藏起来。抽象数据类型仅仅规定了数据类型应该具有的行为（操

13、作）。一旦抽象数据类型被正确实现，就好像程序设计语言中所提供的数据类型那样，可以被自由使用。意义和作用（2）抽象数据类型支持数据类型的实现与使实现与使用分离的原则用分离的原则，允许独立地考虑数据类型的外部接口和内部的实现。这使应用程序只要按抽象数据类型的接口统一其使用界面；可以不管其是否已经实现，也不管它是如何实现的。对于系统的分解、设计、维护和修改均十分有利。例1抽象数据类型圆 ADTCircleisoperationsarea计算圆的面积circumference计算圆的周长getRadius获取圆的半径setRadius设置圆的半径end ADTCircle例2集合抽象数据类型ADTSe

14、tisOperationsisEmpty判断集合是否是空集合add给集合增加一个元素remove删除集合中的一个元素isIn判断一个元素是否在当前集合中endADTSet1.3数据结构关于数据结构的研究，可以追溯到1972年C.A.R.Hoare奠基性的论文数据结构笔记；而现代计算机所大量采用的基本数据结构，最早的系统论述应归功于1973年D.E.Knuth的名著计算机程序设计技巧的问世。为了学习和研究的方便，计算机科学家把常用的数据进行分类，总结出许多典型的数据结构。1.3.1什么是数据结构（通常）可以把数据结构数据结构理解为：计算机中表示（存储）的、具有一定（逻辑）关系和行为的一组数据。其

15、中的每个数据(元素)称为这个结构的一个结点。结点。（根据面向对象的观点）可以把数据结构理解成（根据面向对象的观点）可以把数据结构理解成为抽象数据类型的物理实现为抽象数据类型的物理实现。主要解决两个问题：如何具体表示抽象数据类型中的数学模型；如何给出抽象数据类型中需要操作的实现。数据结构三要素：逻辑结构逻辑结构:指数学模型中的基本元素（结点）和元素之间的相互关系。存储结构存储结构:指数学模型的具体表示方式，包括结点的表示和关系的表示。操操 作作:指抽象数据类型关心的各种行为在存储结构上的具体实现（算法）。例子集合从集合抽象数据类型抽象数据类型的定义出发，将讨论它的实现集合数据结构：数据结构：根据

16、数学数学的概念，集合中的元素是各不相同而且无序的（逻辑结构逻辑结构）；将介绍使用顺序表、单链表、散列表等等许多不同的集合表示方法（存储结构存储结构）；并且在这些不同的表示基础上，给出各自的行为实现算法（操作操作）。1.3.2数据结构的分类主要根据逻辑结构主要根据逻辑结构 和存储结构和存储结构进行分类进行分类逻辑结构逻辑结构 B=K是结点的有穷集合，是结点的有穷集合，R是是K上的一个关系。上的一个关系。K上的一个关系就是K上的一些二元组组成的集合K上的二元组是K中元素的有序对.若k,kK,R，则称k为k的前驱，k为k的后继。没有前驱的结点称为开始结点，没有后继的结点称为终端结点。K上不同的二元组

17、集合构成不同的关系。逻辑结构的概念逻辑结构的概念按逻辑结构分类根据R的特点可以将数据结构分为以下三类：线性结构线性结构：K中每个结点最多只有一个前驱和一个后继的结构。树形结构树形结构：K中每个结点最多只有一个前驱，但可有多个后继的结构。复杂结构复杂结构：K中结点的前驱、后继结点个数都不作限制的结构。*集合：它可以看成R为空的情况，即结点之间没有任何关系。按逻辑结构分类举例 线性结构举例线性结构举例 树形结构举例树形结构举例 复杂结构举例复杂结构举例 存储结构的概念存储结构存储结构:数据的逻辑结构在计算机中的存储数据的逻辑结构在计算机中的存储(表示表示)。通常包括结点的表示和关系的表示。同一种逻

18、辑结构，可以采用不同的表示方式。例如，线性表既可以用顺序（一维数组）的方式来表示（顺序表），也可以用链接的方式（使用指针）来表示（单链表或双链表）。存储结构的设计目标，是使用比较少的空间记录逻辑结构的必要信息，还能够有效实现(抽象数据类型中)要求的操作。根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结构中的各个结点。（结点的关系需要另外存储或者隐含其中）链接表示：结点的存放位置是任意的，结点之间的关系通过与结点关联的指针（或者引用）方式显式表达出来。散列表示：又称为关键码地址转换法。即选择适当的散列（杂凑）函数，根据关键码的值将结点映射到给定的存储空间（散列表）中。索引表示：索引与

19、散列一样，都给出一种从关键码到存储地址的映射方法。不同的是，散列法的映射是通过函数定义；而索引法是通过建立辅助的索引结构解决。1.3.3结点与结构在数据结构的讨论中重点研究的是“结构”，而把组成结构的那些元素抽象成一个“结点”。结点是数据结构中的基本单位，在实际应用中一个结点可以是一个字符、一个整数（初等类型），也可以是一个结构（组合类型）。1.3.4 外存数据的组织简单介绍常用的外存设备及其特点，讨论文件的结构和处理。掌握这些知识，对于理解涉及到外存上的数据结构（例如B/B+树）与算法（例如归并排序）会有帮助.基本概念文件文件是逻辑记录的集合。逻逻辑辑记记录录（简称记记录录）是应用程序需要进

20、行内外存交换的逻辑单位。每个记录可以包含若干数据项数据项，其中能够唯一标识该记录的数据项称为关键码关键码。对外存的数据必须按页块页块存取。页块页块又称物理记录物理记录，是内存与外存进行交换的物理单位。外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。其中以磁带和磁盘最具代表性。磁带磁带上的信息以页块为单位顺序存放，页块与页块之间留有间隙，间隙上不存放数据，但有被硬件识别的带标。一个页块就是一个物理记录。要读写一个页块，首先要定位，即通过磁带的移动使磁头对准被读页块的前沿，然后才能读写。磁带存储器的读写速度与(磁带的存储密度和)走带速度有关，因为属于机械动作，比内存数据的读写时间长得多。

21、在读写前需要定位，定位需要的时间与当前磁头位置与需要定位的位置之间的距离成正比，最坏情况可能需要花费若干分钟。磁盘磁盘类似于多碟的CD，若干盘片（比如片）串在一根主轴上形成一个盘组，当主轴旋转时带动各个盘片旋转。每个盘面上包含大小不同的许多同心圆。每个圆圈称为一个磁磁道道，各个盘面的半径相同的磁道合在一起构成一个柱柱面面。一个磁道又可分为若干段，每段是一个页块页块（物理记录）。一个盘组上从大到小的存储地址为：柱面、磁道和页块。在磁盘上读写信息:选定柱面，这是机械动作，所以比较慢。选定磁道，由电子线路实现，所以比较快。找物理记录，这是机械动作，较慢。实际读写信息的时间比定位时间少得多，目前访问磁

22、盘中的数据比访问内存慢56个数量级。缓冲区与访外缓冲区与访外主机对外存储器上的数据不能直接按字字(或者字字节节)存取。读外存上的数据:1,把外存上一个或者多个物理记录读到内存的指定的区域，这个区域叫作缓冲区缓冲区。2,在缓冲区中找到需要的逻辑记录进行处理。写的过程则相反，先写到缓冲区中，然后通过主机与外存的接口，把缓冲区中的数据写到外存储器的物理记录中。这种读写过程，通常称为访外访外。外存的存取外存储器上的逻辑记录的地址地址由两部分表示：逻辑记录所在物理记录的地址；逻辑记录在物理记录内的相对位置。节省外存的存取时间的关键在于减少访外的次数。由于缓冲区的大小受到内存容量的限制，所以减少访外次数的

23、有效方法是精心设计文件的结构，使外存中存放的记录，相互关联，以便于处理。文件的分类顺序文件.文件中的记录可以按某种顺序（例如按放入文件的先后或者按关键码的大小）定义次序，并且在外存储器上是按同样的次序存放的，则这种文件叫做顺序文件顺序文件。散列文件.通过某种函数关系（称为散列函数）作用到记录的关键码上来确定记录的外存地址。索引文件.对于文件中的记录也可以建立索引。对于大型的文件，其索引往往也是很大的，需要存放在外存上。这样索引也是一种文件。本书把索引和主文件总称为索引文件索引文件。对于索引文件，其主文件如果是一个顺序文件，又可以叫作索引顺序文件索引顺序文件。倒排文件.对于需要对属性建立的索引，

24、称为倒排索引倒排索引带有倒排索引的文件称为倒排索引文件，简称倒排倒排文件文件。文件的处理检检索索。在文件中查找满足一定条件的记录。最常见的是，查找关键码为一指定值的记录，此时，成功的检索只能找出唯一的记录。插入插入。在文件中增加一个新的记录。删删除除。删去文件中的一个记录。插入和删除操作常常需要通过检索，先找到被插入或删除记录的位置。修修改改。把记录中某些属性的值改为新值。若被修改的属性包括关键码，则相当于删除一个老记录并插入一个新记录。排排序序。按照关键码或者某属性的值，从小到大（或从大到小）的次序，把文件的全部记录重新进行排列。这种排序叫做外排序外排序。1.4算法本课是以数据结构为主线，算

25、法为辅线组织内容。因为每种数据结构上的操作，都需要一定算法。对于不同存储结构的选择与评价，算法的好坏起着决定的因素。所有算法的实现也都需要数据结构的支持。算法与数据结构是程序设计的两大支柱。它们相辅相成，互相依赖。什么是算法算法算法是由有穷规则构成（为解决某一类问题）的运算序列。算法可以有若干输入(初始值或条件)；算法通常又有若干个输出(计算结果）。算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。算法应该具有确定性。算法的每一步，必须有确切的定义。算法应该具有可行性。算法中的每个动作，原则上都是能够由机器或人准确完成的。算法的正确性如果一个算法以一组满足初始条件的输入开始，那么该算法的

26、执行一定终止，并且在终止时得到满足要求的（输出）结果。算法设计的方法贪心法分治法回溯法动态规划法分枝界限法贪心法贪心法基本思想是：当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成若干步骤来完成。在其中的每一个阶段都选择从局部看是最优的方案，以期望通过各阶段的局部最优选择达到整体的最优。算法1.1解着色问题时就是采用的贪心法。贪心法实际上不能保证都成功地产生一个全局性最优解，但是通常可以得到一个可行的较优解。（举例）分治法分治法基本思想是:把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题的解合并起来，得出整个问题的解，即对问题分

27、而治之。如果一个子问题的规模仍然比较大，不能很容易地求得解，就可以对这个子问题重复地应用分治策略。二分法检索二分法检索就是用分治策略的典型例子。回溯法回溯法基本思想是:有一些问题，需要通过彻底搜索所有可能情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量通常非常大，所以采取一步一步向前试探，当有多种选择时可以任意选择一种，只要目前可行就继续向前，一旦发现问题或失败就后退，回到上一步重新选择，借助于回溯技巧和中间增加判断，这样常常可以大大地减少搜索时间。常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。动态规划法动态规划法与分治法相似都是把一个大问题分解为若干较小的子问题，通过求解子问

28、题而得到原问题的解。不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。在带权图中，求所有结点之间最短路径的Floyd算法（见第9章）就属于动态规划法。分枝界限法分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略或者采用最大收益（或最小损耗）策略，并且利用最优解属性的的上下界来控制搜索的分枝。最后一章，在讨论背包问题时，介绍了一个用

29、分枝界限法设计的算法。1.4.3算法的精化实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过多次细化才能完成。习惯上，把这个过程称为算法的精化算法的精化。排序问题假设有n1个不同的整数a0，a1，an-1，要求把这些整数从大到小进行排序。排序算法可以明确地用下面的输入和输出关系来描述其功能：输入：是含n个元素的整数数组，记为a，其中的元素依次为：a0,a1,an-1。输出：是输入数组a中元素重新排列，记为a，其中的元素依次为：a0,a1,an-1，满足aiai+1，对所有的0iaj，则jk(3)tai；aiaj；ajt使用

30、C语言的函数形式描述的算法voidsortIntArray(inta，intn)inti,j,k,t;for(i=0;in-1;i=i+1)j=i;/*把ai作为最大整数的初值*/for(k=i+1;kaj)j=k;t=ai;ai=aj;aj=t;1.4.4算法分析分析一个算法主要是看这个算法的执行需要花费多少机器资源。在进行算法分析时人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据占有的空间。在文献中习惯称之为算法的时间代价时间代价和空间代价空间代价。基本概念算法的空空间间代代价价(或称空空间间复复杂杂性性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占

31、用的空间也以某种单位由f(1)增至f(n)，这时我们称该算法的空间代价是f(n)。算法的时时间间代代价价(或称时时间间复复杂杂性性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称该算法的时间代价是g(n)。问题的规模、空间单位和时间单位问题的规模一般可以根据问题本身的提法确定。例如对n个记录进行排序，这里n即可以作为问题的规模。空间单位和时间单位没有统一的规定，通常取算法描述中的初等数据占用的空间和基本操作耗费的时间为单位。在本书中，空间单位选择为一个简单变量(如整型或者实型等)所占存储空间的大小；时间单位则选择为执行一个简单语句(如赋值

32、语句或者判断语句等)所用时间。选择排序的时间代价(n-1)+(n-2)+1=n(n-1)/2大大O表示法表示法在描述算法分析的结果时，人们通常采用大大O表表示示法法：说某个算法的时间代价(或者空间代价)为O(f(n)，如果存在正的常数c和n0，当问题的规模nn0后，该算法的时间(或空间)代价T(n)cf(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。最坏情况下代价的数量级每个算法的实际实际运行时的代价并不是固定不变的。由于不同的输入参数，可能使一个算法的实际代价出现很大差别。要全面分析一个算法，应该考虑它在最坏情况最坏情况下的代价、最好情况最好情况下的代价和平均情况平均情况下的代

33、价等。本书不是专门讨论算法分析的教材，所以在分析算法时主要考虑它们在最坏情况下的代价，而且仅仅要求计算它们的数量级。大大O表示法表示法说某个算法的时间代价(或者空间代价)为O(f(n)，如果存在正的常数c和n0，当问题的规模nn0后，该算法的时间(或空间)代价T(n)cf(n)。也称该算法的时间(或空间)代价的增长率为f(n)。例如，如果有T(n)=3n3，很容易证明T(n)=O(n3)。当然我们也可以证明T(n)=O(n4)。但从分析的精度来看，前一结论给出的是上确界(上界中最小的)，后者给出的仅是一般上界中的一个。计算规则1)加法规则T(n)=T1(n)+T2(n)=O(f1(n)+O(f

34、2(n)=O(max(f1(n),f2(n)2)乘法规则T(n)=T1(n)T2(n)=O(f1(n)O(f2(n)=O(f1(n)f2(n)对于大O表示法，以非零正常数c形成的复杂性度量O(c)都居于同一个量级，人们习惯把它们统一记为O(1)。clog2nnnlog2nn2n310n例子1：考虑如下程序：action1(.);action2(.);其中action1的时间代价是T1(n)=O(n2)，action2的时间代价是T2(n)=O(n3)。按照加法规则，计算整个程序的时间代价为：T(n)=T1(n)+T2(n)=O(max(n2,n3)=O(n3)例子2for(i=1;i=n;i+

35、)action3();/*假设action3()的执行中不改变i的值*/以操作action3的执行时间为单位，显然这里for循环的时间代价可以看作是T1(n)=O(n)；假设action3的时间代价是T2(n)=O(f(n)，根据乘法规则整个程序实际的时间复杂性应当是：T(n)=T1(n)T2(n)=O(n)O(f(n)=O(nf(n)小结1抽象数据类型用计算机对于实际问题求解，就是在计算机中建立一个解决该问题的模型。程序是使用程序设计语言精确描述的实现模型。抽象数据类型是具有一定行为的抽象类型，它抽象掉了类型中值的具体表示方式和数据类型中定义的各种操作的实现方法。在问题求解、数据结构和算法的

36、研究中，抽象数据类型的地位和作用越来越受到重视。小结2数据结构数据结构是抽象数据类型的物理实现。数据结构主要应解决两个问题：一个是选择存储结构；另一个是实现抽象数据类型中的各种操作。抽象类型中元素间内在的相互依赖关系称为逻辑结构。逻辑结构和存储结构是研究数据结构的两个重要方面，也是划分不同数据结构的主要依据。线性结构、树形结构和复杂结构是三种主要的逻辑结构；顺序、链接、索引和散列是四种主要的存储结构。小结3算法算法是由有穷规则构成的，为解决某一特定类型问题确定的运算序列。常见的算法根据其设计方法可以分为贪心法、分治法、回溯法、动态规划法和分枝界限法等。评价一个算法或程序的重要依据是它们运行时所要花费的时间代价和空间代价。实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过多次算法的精化才能完成。小结4文件外存上的数据结构一般都组织成文件的形式，一个文件由若干记录组成。把数据从外存读到内存或从内存写到外存需要执行访外操作，由于每次访问外存可能要花费许多时间来定位，为了减少访外的次数，在内外存交换时，采用缓冲区和分块存取技术。