数据结构与算法数据结构和算法简介.ppt

《数据结构与算法数据结构和算法简介.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法数据结构和算法简介.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、p在信息技术日益盛行的今天，计算机已成为解决各类实际问题的主要工具。p数据结构与算法是利用计算机进行求解问题的两大基石：数据结构刻画了实际问题中信息及其关系算法描述了问题解决方案的逻辑抽象。n数据就是计算机化的信息，是信息的有形表示，是现实世界的事物采用计算机能够识别、存储和处理的形式所进行的描述。n数据之间的关系就是“结构”。n加工、处理数据的规则就是“算法”。p关键词：数据、结构、算法数据结构和算法是相互依赖的：数据结构和算法是相互依赖的：只有恰当地确立问题的结构，才能只有恰当地确立问题的结构，才能选择和设计合适的解决方法。选择和设计合适的解决方法。合适的算法亦需要合适的结构进行合适的算法

2、亦需要合适的结构进行支撑。支撑。学习数据结构和算法是有效使用计算学习数据结构和算法是有效使用计算机的基本前提。机的基本前提。数据结构数据结构 vs vs 计算机科学计算机科学数据结构和算法是计算机学科的核心基础课程n任何问题都离不开数据 n任何数据的处理都离不开算法n数据结构和算法是后续专业课程学习的必要知识与技能准备 编译技术要使用栈、散列表及语法树 操作系统中用队列、存储管理表及目录树 数据库系统运用线性表、多链表、及索引树 etc.课程目标课程目标学会如何有效地组织信息，以便支持高效的数据处理掌握常用的基本数据结构及其应用n学会合理地组织数据，有效地表示数据，高效地处理数据n基本掌握算法

3、的设计与分析技术提高程序设计能力与程序的质量提高使用计算机解决问题的能力教材教材数据结构与算法数据结构与算法 张铭,王腾蛟,赵海燕 高等教育出版社 普通高等教育“十一五”国家级规划教材参考资料参考资料数据结构数据结构(C语言版语言版)严蔚敏严蔚敏 (作者作者),),吴伟民吴伟民 (作者作者)清华大学出版社算法算法导论导论(原书第原书第3版版)Thomas H.Cormen,Charles E.Leiserson Thomas H.Cormen,Charles E.Leiserson etc.etc.机械工业出版社课程学时：56考核方式：考试成绩评定：平时成绩（20%）+考试成绩（80%）学习方

4、法：n n课前预习，提出相关问题课前预习，提出相关问题n n课课上听讲，寻求问题的答案上听讲，寻求问题的答案n n课后复习，巩固知识课后复习，巩固知识认真完成作业第第1 1章章 概论概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量数据结构的选择和评价数据结构数据结构 +算法算法 =？数据结构 n有哪些基本的工具n如何用基本工具制造复杂工具算法n如何使用这些工具解决具体的问题 建立问题的模型n描述问题域中实际对象的数据及其相互关系，得到问题的逻辑模型。n将逻辑模型映射到计算机的存储器上，得到存储模型。n编制程序模拟对象领域中的求解过程。“算法算法数据结构数据结构 程序程序”表达了

5、算法与数据结构的联系及其在程序中的地位n程序就是在数据的某些特定的结构和表示的基础上对于算法的描述n算法与数据结构是程序设计中相辅相成、不可分割的两个方面1.1 问题求解问题求解使用计算机解决实际问题通常遵循以下步骤：第一步第一步：提出问题：提出问题第二步第二步：明确问题的描述，定义恰当的：明确问题的描述，定义恰当的数据结构描述处理对象。数据结构描述处理对象。第三步第三步：设计数据的加工处理规则，得：设计数据的加工处理规则，得到算法到算法第四步第四步：利用有效地程序设计语言编制：利用有效地程序设计语言编制程序程序第五步第五步：运行程序，解决问题：运行程序，解决问题求解问题n计算机科学是“一种关

6、于信息结构转换的科学”(Wegnor)；（数据结构也称“信息结构”）n计算机科学是“算法的学问”，算法是精确定义的一系列规则，指出怎样从给定的输入信息经过有限步骤产生所求的输出信息(D.Knuth)n数据结构与算法两者相互依存，（数据结构离不开施于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据。实例1 已知一组人的身高，如何从中找出最高、最矮的，再找出身材最适中的（诸如101个人中，找出高度第51位的那个）人？1）明确问题的要求：找不同身高的人2）定义处理对象的数据描述：人姓名+身高数据3）给出一种数据结构描述处理对象：名表（线性表）数组4）操作处理对象 设计一组操作规则，在上述数

7、据结构里找出不同身高的人 （这里给出详细的规则描述）5）选用恰当的程序设计语言编写程序 C/C+，Java，等实例2 股市的传言n n实际问题：利用股市传言现象进行谋利实际问题：利用股市传言现象进行谋利n n计算机计算机求解：将这样一个问题转换成用图描述的求解：将这样一个问题转换成用图描述的数学模型，将传言传播问题转换成图上的最短路数学模型，将传言传播问题转换成图上的最短路径问题，进而利用径问题，进而利用FloydFloyd算法求图上每个节点到其算法求图上每个节点到其它各节点的最短路径，比较各节点最长的最短路它各节点的最短路径，比较各节点最长的最短路径，最后求出最有效地传言传播途径。径，最后求

8、出最有效地传言传播途径。关键词：抽象将实际将实际问题抽象成某种数学模型，然后进行求解。问题抽象成某种数学模型，然后进行求解。程序和算法程序和算法程序是计算机程序是计算机“指令指令”的某种组合，用来控制计算机的工的某种组合，用来控制计算机的工作流程，完成一定的逻辑功能，从而实现某种任务。作流程，完成一定的逻辑功能，从而实现某种任务。算法是程序的逻辑抽象，是解决某类客观问题的过程。算法是程序的逻辑抽象，是解决某类客观问题的过程。程序是算法的具体程序是算法的具体实现，是用某种程序设计语言具体书写实现，是用某种程序设计语言具体书写的算法。的算法。算法是程序的灵魂，算法一般不依赖任何程序设计语言而算法是

9、程序的灵魂，算法一般不依赖任何程序设计语言而存在。存在。同一个算法可用不同的程序设计语言实现，从而得到多个同一个算法可用不同的程序设计语言实现，从而得到多个不同的程序，但解题思路都是一样的（为什么？）。不同的程序，但解题思路都是一样的（为什么？）。1.2 数据结构数据结构数据结构描述的是按照一定逻辑关系组织起来的数据的表示及其相关操作，涉及如下三个方面：n数据的逻辑结构：表示数据元素之间的逻辑关系；n数据的存储结构：数据结构在计算机存储器中的表示，也称存储表示；n数据的运算（结构的行为特征）：（结构的行为特征）：作用于数据结构上的运算。例如：检索，插入，删除等常见的基本数据结构 线性表，字符串

10、，堆栈与队列，树与二叉树，字典，图等 后面将逐一详解。关键词：表、树、图 学生花名册 自然界里的树 地图 特点：顺序结构特点：顺序结构 特点：分层结构特点：分层结构 特点：网状结构特点：网状结构 一颗倒生的树 数据的逻辑结构数据的逻辑结构 数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系。用集合论的观点，数据的逻辑结构可以表示为一个二元组：B=(K,R)nK 是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据。n R是定义在集合K上的一组关系，其中每个关系(relation)r（r R）都是 KK上的二元关系，用它描述结点数据之间的逻

11、辑关系。例如,r=|ki K,1 i n K K上的二元关系用二元组上的二元关系用二元组（k,kk,kK K）的集合）的集合表示。每个二元组表示。每个二元组是是K K上的有序对。上的有序对。若若r r R R，k,kk,kK K，r r，则称，则称k k为为k k在关系在关系r r上的直接前驱，上的直接前驱，k k为为k k在关系在关系r r上的直接后继。上的直接后继。没有前驱的结点称为开始没有前驱的结点称为开始结点，没有后继的结点结点，没有后继的结点称为终止结点。称为终止结点。数据的逻辑结构示例数据的逻辑结构示例 家族人员n把每个成员个体的属性描述作为数据结点n全部人员组成结点集Kn家族的各

12、类亲属关系就是一组关系R，其中如母系血缘关系r、远亲关系r*、和非血缘的亲情关系r等等，每一个关系要给出具体人员的关系元组例如：母子关系：兄弟关系：妯娌关系：结点是数据结构中数据的基本单位，也称为“元素”。结点的类型是指结点的数据类型n n如如：学生花名册中每个元素是学生记录类型。：学生花名册中每个元素是学生记录类型。n n数据结构数据结构课程考试成绩的每个元素是一个整型数。课程考试成绩的每个元素是一个整型数。关键词：类型，代表一种种类。结点的类型结点的类型结点的类型可以是基本数据类型，也可以是复合数据类型n基本数据类型：最简单的数据类型，如整型、实型、字符型n复合数据类型：由基本数据类型或复

13、合数据类型的数据组合而成的复杂型数据类型。如数组，用户自定义类型等。基本数据类型基本数据类型整数类型(integer)：该类型规定了整数所能表示的范围。通常，在计算机中一般使用1到4个字节来存储整数。实数类型(real)：计算机的浮点数据类型所能表示的数值范围和精度是有限的。机器一般使用4到8个字节来存储浮点数。布尔类型(boolean)：取值为真(true)和假(false)，在C+语言中一般使用整数0表示false，用非0表示true 字符类型(char)：用单个字节（8bit）表示ASCII字符集中的字符。n汉字符号需要使用2个字节（每个字节的最高位bit为1）的编码，单个字节对于汉字是

14、没有独立含义的n在C+中把双字节表示中文符号的字节类型称为w_char类型（wide character）。n目前国际上已经采用了统一的扩展字符集合标准UNICODE，这一标准允许英、日、韩、阿拉伯语等文字的混合文字处理特殊的数据类型：指针类型(pointer)用于表示计算机中内存单元的地址。某指针类型变量的值是某一内存单元的地址，简称为该指针指向该内存单元。n由于机器的指令系统一般采用32 bit或64bit的地址长度，所以指针类型也相应地用4个字节或8个字节来表示一个指针。n指针值的存储和指针值的运算方式，在形式上与正整数相似。n指针的运算一般仅限于两个指针地址的比较，加减，或对一个指针增

15、减一个整数量等，乘、除等运算对指针无效。复合数据类型复合数据类型复合类型是由基本数据类型组合而成的数据结构类型例如：在程序语言中常用的数组类型，结构（记录）类型等皆属复合数据类型复合数据类型本身，又可以参与定义结构更为复杂的结点类型结构的分类结构的分类 讨论逻辑结构（K,R）的分类，一般把讨论重点放在关系集R上。用R的性质来刻划数据结构的特点，并对数据结构进行分类：n线性结构（linear structure）n树型结构（tree structure）n图结构 （graph structure）线性结构线性结构线性结构中的关系r 称为线性关系，也称为“前驱关系”。线性关系r中，每个结点至多只有

16、一个前驱结点和一个后继结点。n开始结点没有前驱结点，终止结点没有后继结点。n其它结点为“内部结点”，在关系r上有且只有一个前驱结点和一个后继结点。关系 r 是有向的，且满足全序性和单索性等约束条件n全序性是指，线性结构的全部结点两两皆可以比较前后（关系 r）n单索性是指，每一个结点 x 都存在唯一的一个直接后继结点 y。如果其他结点 z 在 y 之前，则这个 z 也一定在 x 之前，不会在x，y之间。线性结构是程序设计中应用最多的数据结构形式n数组、链表、栈、队列等都属于线性结构。树型结构树型结构树型结构简称树结构或层次结构。其关系 r 称为层次关系，或称“父子关系”、“上下级关系”等层次关系

17、中，结点被分布于多个层中。每一个结点k可以有多于一个的“直接下级”（后继结点，称为k的儿子结点），但是它最多只能有唯一的一个“直接上级”（前驱结点，称为k的父亲节点）。n没有父结点的结点称为树根（root），位于树型结构的最高层。n没有儿子结点成为叶子结点，位于树型结构的最下层。树型结构存在着很多变种，如二叉树结构，堆结构等，它们都有着各自独特的性质和应用。图结构图结构图结构有时称为网络结构。对于图结构的关系 r 没有加任何约束。图结构中允许结点具有多个“直接上级结点”或“直接下级结点”。图由结点和边组成，注意与日常生活中“图”的区别。从数学上看，树型结构和图结构的基本区别就是“每个结点是否仅

18、仅从属一个直接上级”。线性结构和树型结构的基本区别是“每个结点是否仅仅有一个直接后继”。需要注意的是，一个复杂的数据结构里可能包含一些小的数据结构（类似于C/C+语言中结构类型的嵌套定义），反映了现实世界中客观实体之间属性的包含关系。因此，在构造比较复杂的数据结构时，可以逐层分析逻辑结构，层层展开这是一种自顶向下的分析设计方法。数据的存储结构数据的存储结构数据及其关系在计算机内存里是怎么存储的呢？数据的存储结构就是各种逻辑结构在计算机中的物理存储表示计算机的主存储器的特性n计算机主存是由若干基本存储单元组成的一个连续的一维区域。每个基本存储单元都有一个非负整数型的地址编码的，从0开始连续编码。

19、一般情况下，基本存储单元是字节，8bit。0 12188bits内存是一个连续的一维空间区域计算机的指令具有按地址随机访问存储空间内任意单元的能力，并且访问不同地址所需的访问时间基本相同数一个结点自身的内部数据一般存放在内存一块连续的区域内，并称其第一个字节的地址为该结点在内存中的地址。首地址：该区域第一个字节的地址某结点的连续存储区域 “关系”在计算机内存里是怎么存储的呢？用数学映射的观点，数据的存储结构是建立一种映射：对于数据的逻辑结构（K，r），其中rRn对它的结点集合 K，建立一个从K到存储器M的映射：KM，对于每一个结点 jK 都对应一个唯一的连续存储区域c M与之对应n每一个关系元

20、组（j1，j2）r（其中j1，j2K是结点），亦即j1，j2的逻辑后继关系应映射为存储单元的地址间关系（顺序的，或指针的地址指向关系）。常用的基本存储映射方法有四种：顺序、链接、索引、散列顺序方法顺序方法 用一块无空隙的存储区域存储数据称为顺序存储。顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑关系用存储单元的自然顺序关系来表达 顺序存储法为使用整数编码来访问数据结点提供了便利，如数组。02136547S顺序存储结构称为紧凑存储结构，其紧凑性是指它的存储空间除了存储“有用数据”外，没有用于存储其他附加的信息。紧凑性可以用“存储密度”来度量：它是一个存储结构所存储的“有用数据”

21、和该结构（包括附加信息）占用的整个存储空间大小之比。存储密度低则空间利用率就低、空间效率差。链接方法链接方法 在结点的存储结构中附加指针域来表示存储结点间的逻辑关系，这种方法称为链接法。指针：“指示器”，一种变量单元，其值是内存单元的地址。n指针“指向”某个结点，就是令该指针的值等于这一结点的存储单元的开始地址，称为“链接”。n多个相关结点的依次链接就会形成“链索”0Xff0d结点的内存区域结点的首地址0Xff0d指向指针链接法中，数据结点由两部分组成:n数据域：存放结点本身的“有用数据”，也称为数据字段n指针域：存放后继结点的指针，也称为指针字段。两个结点的逻 辑后继关系用指针的指向来表达。

22、n如上，多个相关结点的依次链接就会形成“链索”数据域 指针域P链接法的优点：对于经常增删结点的复杂数据结构，顺序存储往往会遇到困难元素的移动很低效；链接方法结合动态存储为这些复杂问题提供了解决方法不用移动元素，只要修改结点指针的指向关系即可。链接法的缺陷：n需要额外存储指针的空间空间利用率低了。n为了访问结点集 K 中某个结点，必须使用该结点的存储指针。当不知道结点指针时，为了在结点集 K中寻找某个符合条件的结点，就要沿着链接结点的“链索”，一个结点一个结点搜索查询花费的时间多，效率低下，索引（索引（indexingindexing）方法）方法 索引法是顺序存储法的一种推广，也使用整数编码来访

23、问数据结点位置。索引方法是要建造一个由整数域 Z 映射到存储地址域D 的函数Y：ZD，把结点的整数索引值 zZ映射到结点的存储地址 dD（Y称为索引函数）从而形成一张存储了一组指针的索引表。表中的每个指针指向存储区域的一个数据结点（类似于目录）。索引方法示意索引方法示意 索引表中每一元素是指向数据结点的指针，大小一致，所以可以进行线性的索引计算：索引表S的元素Si的起始地址 元素S0的起始地址 i（指针尺寸）通过上述公式，由索引号 i 可以计算出索引表中的单元Si的始址，再通过读出Si元素的内容（即指针），访问真正需要访问的数据结点。0123数据结点1数据结点2数据结点3数据结点4索引表索引方

24、法的缺点：索引表需要额外的存储空间，空间开销大。索引方法的优点：索引提高了结点检索的效率。索引方法在程序设计中是一种经常使用的方法，其主要原因是对于非顺序的存储结构来说，使用索引表是快速地由整数索引值找到其对应数据结点的唯一方法散列方法散列方法 散列方法是索引方法的一种延伸和扩展。散列法利用一种称为散列函数(hash functions)的机制来进行索引值的计算，然后通过索引表求出结点的指针地址。散列函数是一种将给定的关键码s 映射为非负整数 z 的函数 h:S Z：对任意的 s S，散列函数 h(s)=z，z Z z即为结点的索引值。散列函数h(s)除了它取非负整数值外，关键的问题包括：n如

25、何恰当地选择散列函数，是散列函数计算出来的地址尽可能地均匀分布在构造散列表的地址空间中，并且计算效率高。n如何建造散列表n“碰撞”问题：如果两个关键码的散列函数值相同，则发生“碰撞”。当发生碰撞时，如何处理冲突，以便能找到正确的结点是散列法需要重点考虑的一个问题。抽象数据类型抽象数据类型什么是抽象数据类型？通俗地讲，抽象数据类型ADT(Abstract Data Type)就是数据和操作的封装来自于面向对象中类的概念。n数据是该抽象数据类型的数据对象，操作是施加在数据上的特定运算。nADT对外部的反映就是该类型数据能取什么值，对外提供哪些运算和操作。n如整型：整型数取整数作为其值，可以参加+、

26、-、x、/等运算。n如字符串类型：字符串类型的变量取字符串作为其值，提供的运算有：赋值、求字符串长度、取子串、字符串连接等操作。模块化的思想的发展，为模块的划分和ADT的产生提供了理论依据（见教材P9，自学）。一个抽象数据类型可以看作是定义了一组操作的一个抽象模型。n例如，集合与集合的并、交、差运算就可定义为一个的抽象数据类型一个抽象数据类型要包括哪些操作，这一点由设计者根据需要确定n例如，对于集合，如果需要，也可以把判别一个集合是否空集或两个集合是否相等作为集合上的操作抽象数据类型的本质n抽象数据类型用数学方法定义对象集合和运算集合，仅通过运算的性质刻画数据对象，而独立于计算机中可能的表示方

27、法逻辑表示。n抽象数据类型隐藏了内部数据结构和运算实现的细节，对外仅提供接口，使得用户程序仅通过抽象数据类型所定义的操作来访问其中的数据，从而实现了信息隐藏，使人们独立于程序的实现细节来理解数据结构的主要性质和约束条件，从更高的抽象级别去讨论和使用数据结构和算法。抽象数据类型抽象数据类型抽象数据结构由 三个不可分割的部分组成的三元组：n数据对象Dn数据关系Sn数据操作P 1.3 算法算法对特定问题求解过程的描述，是指令的有限序列，也即，为解决某一特定问题而采取的具体有限的操作步骤。程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。用计算装置能够理解的语言描述的解题过程，具有如

28、下性质：1.将它作用于所求解的问题的给定输入集上，或作用于问题自身的描述上，将产生唯一确定的动作序列，此序列是有限的；2.此序列或终止于给出问题的解，或终止于指出问题对此输入无解 有穷性；确定性；可行性；输入；输出算法的特性算法的特性 通用性对于那些符合输入类型的任意输入数据，都能根据算法进行问题求解，并保证计算结果的正确性有效性n算法是有限条指令组成的指令序列，其中每一条指令都必须是能够被确切执行的，被人或机器所执行。指令的类型应该明确规定，仅限于若干明确无误的指令动作，是一个有限的指令集。其结果应具有确定的数据类型，是能够预期的确定性n算法对每执行一步之后的下一步，应该有明确的指示。下一步

29、动作可以是条件判断、分支指令、或顺序执行一条指令、或者指示整个算法的结束等。算法的确定性要保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令（被锁住）或仅仅含有模糊不清的指令有穷性n算法的执行必须在有限步内结束。换句话说，算法不能含有死循环 算法分类算法分类算法设计与算法分析是计算机科学的核心问题常用的设计方法n穷举法(百钱买百鸡)n贪心法(Huffman树)n递归法,分治法(二分法检索)n回溯法(八皇后)n动态规划法(最佳二叉排序树)n宽度优先和深度优先搜索n-裁剪和分枝界限法n并行算法算法的执行效率及其度量算法的执行效率及其度量解决同一个问题总是存在着多种算法，如何评估各算法的好坏

30、？或据此设计出更好的算法？n运行该算法所需要的计算机资源的多寡，所需越大复杂性越高n其中，最重要的资源：时间（处理器）和空间（存储器）评价一个算法优劣的重要依据是看执行该算法的程序需要占用多少机器资源：n程序所用算法运行时所要花费的时间代价n程序中使用的数据结构占有的空间代价需要明确：n怎样表达一个算法的复杂性n怎样计算一个算法的复杂性计算复杂性和算法的效率计算复杂性和算法的效率根据计算理论(theory of computation)，存在着一类问题虽然能够被准确定义，但却不存在能够解决该问题的算法。称为不可解问题计算复杂性理论(computational complexity theory

31、)指出，理论上存在一大类难解问题，它们虽然存在着求解算法，但是在算法的计算时间上，都是组合爆炸型的求解算法n所谓组合爆炸型，是指随着问题的规模 n 的增大，算法的时间开销不能约束在 n 的 k 阶多项式数量范围内。（其中 k是任意不依赖于 n 的常数）根据计算复杂性理论，难解问题的定义就是它的求解算法均无法在多项式时间 nk 数量级内解决（其中 k 是任意正整数）。比较常见的难解问题有：图论中的求最优巡游路径问题，判定命题逻辑公式是否为恒真等算法复杂性算法复杂性不能用诸如微秒、纳秒这样的真实时间单位n一个运行在Cray机上的算法若放在PC机会慢很多n一个运行在Cray机上的效率极差的算法也许比

32、一个运行在PC上的效率很高的算法花费更少的时间n同样的算法运行在同样的机器上也会因使用不同的程序语言而存在差异C vs LISPn两个不同的算法也许在输入规模为100时表现不相上下，而在输入规模扩大10倍后却表现迥异重要的假设和约定重要的假设和约定1）计算机模型的假设 Turing机模型：计算机形式理论模型 通用计算机模型：顺序计算机 有足够的“内存”能在固定的时间内存取数据单元重要的假设和约定重要的假设和约定(2)(2)计算的约定计算的约定 算法的执行时间算法的执行时间=FFi i*t*ti i 其中，其中，F Fi i是算法中用到的某种运算是算法中用到的某种运算i i的次数，的次数，t t

33、i i是是该该运算运算执执行一行一次所用的次所用的时间时间。确定使用什么样的运算及其执行时间。确定使用什么样的运算及其执行时间。从计算时间上，运算的分类：从计算时间上，运算的分类：时间囿界于常数的运算时间囿界于常数的运算：基本算术运算，如整数、浮点数的加、减、乘、除基本算术运算，如整数、浮点数的加、减、乘、除 字符运算字符运算 赋值赋值运算运算 过程调用等过程调用等 特点：尽管每种运算的执行时间不同，但一般只花特点：尽管每种运算的执行时间不同，但一般只花 一个一个固定量固定量的时间（单位时间）就可完成。的时间（单位时间）就可完成。重要的假设和约定重要的假设和约定(3)(3)其他运算其他运算：字

34、符串操作：与字符串中字符的数量成正比字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关记录操作：与记录的属性数、属性类型等有关 特点：运算时间特点：运算时间无定量无定量 如何分析非时间囿界于常数的运算：分解成若干时间囿界于常如何分析非时间囿界于常数的运算：分解成若干时间囿界于常数的运算。数的运算。如：如：T Tstringstring=Length=Length（StringString）*t tcharchar算法分析算法分析对算法进行全面分析，可分两个阶段进行：对算法进行全面分析，可分两个阶段进行：事前分析事前分析：就算法本身，通过对其执行性能的理论分析，：就

35、算法本身，通过对其执行性能的理论分析，得出关于算法特性得出关于算法特性时间和空间时间和空间的一个特征的一个特征 函数（函数（、）与计算机物理软硬件没有与计算机物理软硬件没有 直接关系。直接关系。事后测试事后测试：将算法编制成程序后实际放到计算机上运行，：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行收集其执行时间和空间占用等统计资料，进行 分析判断分析判断直接与物理实现有关直接与物理实现有关事前分析目的：试图得出关于算法执行特性的一种形式描目的：试图得出关于算法执行特性的一种形式描 述，以述，以“理论上理论上”衡量算法的衡量算法的“好坏好坏”。如何给出反映算法

36、执行特性的描述如何给出反映算法执行特性的描述？最直接方法：最直接方法：统计算法中各种运算的执行情况，包括：统计算法中各种运算的执行情况，包括：运用了哪些运算运用了哪些运算 每种运算被执行的次数每种运算被执行的次数 该种运算执行一次所花费的时间等。该种运算执行一次所花费的时间等。算法的执行时间算法的执行时间=FFi i*t ti i频率计数频率计数 例：例：x=x=x+y for x+y for（i=0i=0；inin；i+i+）for for（i=0i=0；inin；i+i+）x=x+y x=x+y；for for（j=0j=0；jnjn；i+i+）x=x+y;x=x+y;(a)(b)(c)(

37、a)(b)(c)分析：分析：(a)(a)：x x=x+y=x+y执执行了行了1 1次次 (b)(b)：x x=x+y=x+y执执行了行了n n次次 (c)(c)：x x=x+y=x+y执执行了行了n n2 2次次 定定义义：频频率率计计数数：一条：一条语语句句或一种或一种运算运算在算法（或程序）体中的在算法（或程序）体中的执执行次行次数。数。一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间 如何刻画算法执行特性的形式描述如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素，如机器类型、编程与实际执行时间受约于诸多实际因素，如机器类型、编程与语言、操作系统等，没

38、有统一的描述模型。语言、操作系统等，没有统一的描述模型。在事前分析中，只限于确定与所使用的机器及其他环境因在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立理论分析模型。素无关的频率计数，依此建立理论分析模型。数量级 语句的数量级：语句的执行频率 例：例：1 1，n n，n n2 2 算法的数量级：算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例：假如求解同一个问题的三个算法分别具有例：假如求解同一个问题的三个算法分别具有n n，n n2 2 ，n n3 3数数 量级。量级。若若n=1

39、0n=10，则可能的执行时间将分别是，则可能的执行时间将分别是1010，100100，10001000个单个单 位时间位时间与环境因素无关。与环境因素无关。算法的输入规模算法的输入规模算法的执行时间随问题规模的增长而增长，增长算法的执行时间随问题规模的增长而增长，增长的速度随不同的算法而不同的速度随不同的算法而不同没有一个方法可以准确的计算算法的具体执行时没有一个方法可以准确的计算算法的具体执行时间间 语言、编译系统、计算机语言、编译系统、计算机实际上，在评估算法的性能时，并不需要对算法实际上，在评估算法的性能时，并不需要对算法的执行时间作出准确的统计，人们希望算法与实的执行时间作出准确的统计

40、，人们希望算法与实现的语言无关、与执行的计算机无关现的语言无关、与执行的计算机无关所关心的是：算法的执行时间，随着输入规模的所关心的是：算法的执行时间，随着输入规模的增长而增长的情况增长而增长的情况1.4 算法复杂性分析算法复杂性分析算法分析感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随输入规模增长的值是可预测的n与问题的规模之间的关系，用一定“规模(size)”的数据作为输入时程序运行所需的“基本操作(basic operation)”数来描述时间效率。譬如，如果数据规模n和运行时间t 间存在一个线性的关系，t1=cn，那么数据规模增加5倍后，运行时间也相应地增

41、加同样的倍数，即n2=5n,则t2=5t1。同理，如果t1=log2n，则 n 的规模加倍意味着时间增加一个单位，即，n2=2n，t2=log 2(2n)=log2n+1=t1+1 n完成一个“基本操作”所需的时间应该与具体的被操作的数无关算法的渐进分析算法的渐进分析 (asymptotic analysisasymptotic analysis)简称算法分析n由于算法的复杂性与其所求解的问题规模直接有关，因此通常将问题规模 n 作为一个参照量，求算法的时空开销和 n 的关系n一般这种函数关系都相当复杂，计算时只考虑可以显著影响函数量级的部分，即结果为原函数的一个近似值n对资源开销的一种不精确

42、估计，提供对于算法资源开销进行评估的简单化模型算法的渐进分析算法的渐进分析算法的渐进分析就是要估计，当数据规模 n逐步增大时，资源开销f(n)的增长趋势得到如此精确的一个界相对比较费时费力，且没有必要从数量级大小的比较来考虑，当n增大到一定值以后，资源开销的计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都是可以忽略的 算法渐进分析：大表式法算法渐进分析：大表式法假设f 和g为从自然数到非负实数集的两个函数定义定义1：如果存在正数c和N，使得对任意的nN，都有f(n)cg(n)，则称f(n)在集合O(g(n)中，或简称f(n)是O(g(n)的。该定义说明了函数 f 和 g 之间

43、的关系：函数g(n)是函数 f(n)取值的上限（upper bound），或说函数f的增长最终至多趋同于g的增长因此，大O表示法提供了一种表达函数增长率上限的方法。一个函数增长率的上限可能不止一个。譬如，一个在集合O(n)中的函数也一定在集合O(n2)中，同时也在集合O(n3)中，等等。大O表示法给出了所有上限中最“紧”（也即最小）的那个上限 一般而言：一般而言：算法的计算时间为算法的计算时间为f(n)f(n)数量级限界函数为数量级限界函数为g(n)g(n)其中，其中，n n是输入或输出规模的某种测度。是输入或输出规模的某种测度。f(n)f(n)表示算法的表示算法的“实际实际”执行时间执行时间

44、与机器及语言有与机器及语言有关关。g(n)g(n)是是形式简单形式简单的函数，如的函数，如n nmm，lognlogn，2 2n n，n!n!等。是等。是事前分析中通过对计算时间或频率计数统计分析所得事前分析中通过对计算时间或频率计数统计分析所得的、的、与机器及语言无关与机器及语言无关的函数。的函数。大表式法的性质大表式法的性质若符号a是不依赖于n的任意常数 1.如果函数 f(n)是O(g(n)的，g(n)是O(h(n)，那么f(n)是O(h(n)的2.如果函数f(n)是O(h(n)的，g(n)是O(h(n)，那么f(n)+g(n)是O(h(n)的3.函数ank是O(nk)的4.若f(n)=c

45、g(n)，则f(n)是O(g(n)的5.对于任何正数a和b，且b1，函数logan 是O(logbn)的。即，任何对数函数无论底数为何，都具有相同的增长率6.对任何正数 a1，都有logan 是O(log n)的，其中log n=log2n大大O O表示法的运算规则表示法的运算规则单位时间n简单布尔或算术运算n简单I/On函数返回加法规则:f1(n)+f2(n)=(max(f1(n),f2(n)n顺序结构，顺序结构，if 结构，switch结构乘法规则:f1(n)f2(n)=(f1(n)f2(n)nfor,while,do-while结构76多项式定理多项式定理:定理定理定理定理 若若若若A(

46、n)=aA(n)=ammn nmm+a+a+a+a1 1 1 1n+an+an+an+a0 0 0 0是一个是一个是一个是一个m m m m次多项次多项次多项次多项 式，则有式，则有式，则有式，则有A(n)=A(n)=A(n)=A(n)=(n nmm)即：变量即：变量即：变量即：变量n n n n的固定阶数为的固定阶数为的固定阶数为的固定阶数为m m m m的任一多项式，与此多的任一多项式，与此多的任一多项式，与此多的任一多项式，与此多 项式的最高阶项式的最高阶项式的最高阶项式的最高阶n nmm同阶。同阶。同阶。同阶。证明：取证明：取证明：取证明：取n n n n0 0 0 0=1,=1,=1

47、,=1,当当当当nnnnnnnn0 0 0 0时，有时，有时，有时，有 A(n)A(n)|a|amm|n|nmm+|a+|a1 1|n+|a|n+|a0 0|(|a (|amm|+|a|+|am-1m-1|/n+|a|/n+|a0 0|/n|/nmm)n)nmm (|a (|amm|+|a|+|am-1m-1|+|a|+|a0 0|)n|)nmm 令令令令c=|ac=|amm|+|a|+|am-1m-1|+|a|+|a0 0|定理得证。定理得证。定理得证。定理得证。算法分类（计算时间）算法分类（计算时间）多项式时间算法：可用多项式（函数）对其计算时间多项式时间算法：可用多项式（函数）对其计算时

48、间限界的算法。限界的算法。常见的多项式限界函数有：常见的多项式限界函数有：(1)(1)(logn)(logn)(n)(n)(nlogn)(nlogn)(n(n2 2)(n(n3 3)指数时间算法：计算时间用指数函数限界的算法指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数：常见的指数时间限界函数：(2(2n n)(n(n！)n0，有下列两不等式同时成立：c1 g(n)f(n)c2 g(n)渐进分析示例渐进分析示例下面是一段对数组中的各个元素求和的代码：for (i=sum=0;in;i+）sum+=ai;其中主要的操作为赋值运算，故该算法的时间代价主要体现在赋值操作的数目上n

49、在循环开始之前有两次赋值，分别对 i 和对sum进行；n循环进行了n 次，每次循环中执行两次赋值，分别对 sum和对 i 进行更新操作；n总共有2+2n 次赋值操作其渐进复杂度为O(n)渐进分析示例渐进分析示例依次求出给定数组的所有子数组中各元素之和：for (i=0;i n;i+)for (j=1,sum=a0;j=i;j+)sum+=aj;循环开始前，有一次对i的赋值操作。外层循环共进行n次，每个循环中包含一个内层循环，以及对i,j,sum分别进行赋值操作；n每个内层循环执行2个赋值操作，分别更新sum 和 j；共执行i次（i=1,2,n-1）。整个程序总共执行的赋值操作为：渐进分析示例渐

50、进分析示例若只对每个子数组的前5个元素求和，则相应的代码可采用下面的方式：for(i=4;in;i+)for(j=i-3,sum=ai-4;j=i;j+)sum+=aj;外层循环进行n-4次对每个 i 而言，内层循环只执行4次，每次的操作次数和 i 的大小无关：8次赋值操作整个代码总共进行O(1)+8(n-4)=O(n)次 看似双重循环，其实线性时间增长率函数曲线增长率函数曲线各时间量级在现实中对应的物体速度各时间量级在现实中对应的物体速度米/秒英制度量衡现实世界的例子10-1110-1010-910-810-710-610-510-410-310-210-111011021031041051