国家级精品课程—《数据结构与算法》

1、文库专用1国家级精品课程国家级精品课程数据结构与算法数据结构与算法张铭、赵海燕、王腾蛟、宋国杰、高军张铭、赵海燕、王腾蛟、宋国杰、高军/北京大学信息科学与技术学院北京大学信息科学与技术学院“数据结构与算法数据结构与算法”教学小组教学小组本章主笔：赵海燕赵海燕 版权所有，转载或翻印必究版权所有，转载或翻印必究第第 1 1 章章 概论概论主要内容主要内容n问题求解问题求解n数据结构及抽象数据类型数据结构及抽象数据类型n算法的特性及分类算法的特性及分类n算法的效率度量算法的效率度量n数据结构的选择和评价数据结构的选择和评价问题求解问题求解n阶段和步骤阶段和步骤q获取需求（问题），以保证解决的问题正是

2、需获取需求（问题），以保证解决的问题正是需要的（要的（solve the right problem）；）；q分析问题，将其分解为粒度更小的部分；分析问题，将其分解为粒度更小的部分；q针对问题（子问题）给出相应的解决方案，易针对问题（子问题）给出相应的解决方案，易于理解和修改；于理解和修改；q估算解决方案的开销，以事先判断其可行性；估算解决方案的开销，以事先判断其可行性；n利用数学等工具的辅助得到正确且简洁的解决方案利用数学等工具的辅助得到正确且简洁的解决方案q维护和演化维护和演化问题求解问题求解问题求解问题求解数据结构数据结构设计方法设计方法描述语言描述语言算法理论算法理论数据模型数据模型问

3、题求解问题求解n通过通过n问题抽象问题抽象n数据抽象数据抽象n算法抽象算法抽象分析问题，应用数据结构和算法来设计分析问题，应用数据结构和算法来设计和实现高效的程序和实现高效的程序问题求解问题求解n实质实质q描述问题域中实际对象的描述问题域中实际对象的数据数据及其及其相互相互关系关系q映射到计算机的存储器上映射到计算机的存储器上q编写算法模拟对象领域中的求解过程编写算法模拟对象领域中的求解过程文库专用7问题求解问题求解n计算机科学就是计算机科学就是“一种关于信息结构转换一种关于信息结构转换的科学的科学” (Wegnor)n计算机科学是计算机科学是“算法的学问算法的学问” (D.Knuth)n其实

4、数据结构与算法两者互为存在其实数据结构与算法两者互为存在 （数据（数据结构离不开施于其上的操作，同时算法也结构离不开施于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据）必然离不开作为其处理对象和结果的数据）问题求解问题求解n 例子：例子：q从一组人中找出最高、最矮，及身高最适从一组人中找出最高、最矮，及身高最适中的人。中的人。q有有12个外表完全相同的球，只有一个不标个外表完全相同的球，只有一个不标准，或轻或重，要求用天平以最少的次数准，或轻或重，要求用天平以最少的次数找出该球，并判定其轻重找出该球，并判定其轻重。q计算机专业课程安排。计算机专业课程安排。n问题抽象问题抽象 、数据

5、抽象、算法抽象、数据抽象、算法抽象数据结构数据结构n数据的数据的q图图 树树 二叉树二叉树 线性表线性表n数据的数据的q顺序方法、链接方法顺序方法、链接方法q索引方法、散列方法索引方法、散列方法 n数据的数据的q增、删、查、改增、删、查、改q排序、检索排序、检索存存储储数据数据结构结构逻逻辑辑运运算算数据结构数据结构n一类按照一定逻辑关系组织起来的数据的一类按照一定逻辑关系组织起来的数据的表示及其相关操作表示及其相关操作q逻辑结构：表示数据元素之间的逻辑关系；q存储结构：数据结构在计算机存储器中的表示，也称存储表示；q运算（结构的行为特征）：作用于数据结构上的运算。常见的基本数据结构常见的基本

6、数据结构：线性表，字符串，堆栈与队列，树与二叉树，字典，图数据的逻辑结构数据的逻辑结构 n二元组 B = (K, R) K ： 结点（ 初等或组合类型）的有限集合 R : K上的有穷关系的集合（一组二元关系）qK中每个结点都代表一个数据或一组有明确结构中每个结点都代表一个数据或一组有明确结构的数据的数据q关系集关系集 R中的每个关系中的每个关系(relation) r（r R）都）都是是 KK上的二元关系，用以描述结点之间的逻上的二元关系，用以描述结点之间的逻辑关系辑关系 例如, r = | ki K, 1 i n 数据的逻辑结构：示例数据的逻辑结构：示例 n家族人员家族人员q把每个成员个体的

7、属性描述作为数据结点，而全部人员把每个成员个体的属性描述作为数据结点，而全部人员组成结点集组成结点集Kq家族的各类亲属关系就是一组关系家族的各类亲属关系就是一组关系R，其中如母系血缘关，其中如母系血缘关系系r、远亲关系、远亲关系r*、和非血缘的亲情关系、和非血缘的亲情关系r等等，每一个关等等，每一个关系要给出具体人员的关系元组系要给出具体人员的关系元组q例如：例如： 母子关系（戴爱莲，张远）母子关系（戴爱莲，张远） 兄弟关系（张远，张立）兄弟关系（张远，张立） 妯娌关系妯娌关系 （戴爱莲，李美英）（戴爱莲，李美英）结点类型：基本数据类型结点类型：基本数据类型n整数类型整数类型(integer)

8、：规定了所能表示的整数范围，：规定了所能表示的整数范围，计算机一般用计算机一般用1个字节个字节到到4个字节个字节来存储整数来存储整数n实数类型实数类型(real)：计算机的浮点数据类型所能表示：计算机的浮点数据类型所能表示的数值范围和精度是的数值范围和精度是有限有限的。的。 机器一般使用机器一般使用4到到8个字节个字节来存储浮点数来存储浮点数n布尔类型布尔类型(boolean)：取值为：取值为真真(true)和和假假(false)，在在C+语言中一般使用整数语言中一般使用整数0表示表示false，用非，用非0表表示示true 结点类型：基本数据类型结点类型：基本数据类型n字符类型字符类型(ch

9、ar)： 用单个字节（用单个字节（8bit，最高位，最高位bit为为0）表示）表示ASCII字符集中的字符字符集中的字符q汉字符号需要使用汉字符号需要使用2个字节（每个字节的最高位个字节（每个字节的最高位bit为为1）的编码，单个字节对于汉字是没有独立含义的的编码，单个字节对于汉字是没有独立含义的q在在C+中把双字节表示中文符号的字节类型称为中把双字节表示中文符号的字节类型称为w_char类型（类型（wide character）。）。q目前国际上已经采用了统一的扩展字符集合标准目前国际上已经采用了统一的扩展字符集合标准UNICODE，这一标准允许英、日、韩、阿拉伯语等，这一标准允许英、日、韩

10、、阿拉伯语等文字的混合文字处理文字的混合文字处理结点类型结点类型 ：基本数据类型：基本数据类型n指针类型指针类型(pointer)：用于表示机器内存地址，指：用于表示机器内存地址，指针表示指向某一内存单元的地址针表示指向某一内存单元的地址q由于机器的指令系统一般采用由于机器的指令系统一般采用32 bit或或64bit的地址长的地址长度，故指针类型也相应地用度，故指针类型也相应地用4或或8个字节个字节来表示一个指来表示一个指针针q指针值的存储和指针值的运算方式，在形式上与正整指针值的存储和指针值的运算方式，在形式上与正整数相似数相似q指针的运算一般仅限于两个指针地址的比较，加减，指针的运算一般仅

11、限于两个指针地址的比较，加减，或对一个指针增减一个整数量等或对一个指针增减一个整数量等结点类型结点类型 ：复合数据类型：复合数据类型n复合类型是由基本数据类型组合而成的数据结构复合类型是由基本数据类型组合而成的数据结构类型类型q例如：在程序语言中常用的数组类型，结构例如：在程序语言中常用的数组类型，结构（记录）类型等皆属复合数据类型（记录）类型等皆属复合数据类型n复合数据类型本身，又可以复合数据类型本身，又可以参与定义参与定义结构更为复结构更为复杂的结点类型杂的结点类型n结点的类型不限于基本数据类型，可以根据应用结点的类型不限于基本数据类型，可以根据应用的需要来灵活定义的需要来灵活定义 结构的

12、分类结构的分类 n数据的逻辑结构（数据的逻辑结构（K, R）的讨论，一般把重点放）的讨论，一般把重点放在在关系集关系集R上；上；n根据根据 R的性质的性质 刻划数据结构的特点，并对数据结刻划数据结构的特点，并对数据结构进行分类：构进行分类： q线性结构（线性结构（linear structure）q树型结构（树型结构（tree structure） q图结构（图结构（graph structure）线性结构线性结构n关系关系r 是一种线性关系，或称为是一种线性关系，或称为“前后关系前后关系”，有，有时也称为时也称为“大小关系大小关系”。关系。关系 r 是有向的，且满足是有向的，且满足全序性和单

13、索性等约束条件全序性和单索性等约束条件q全序性是指，线性结构的全部结点两两皆可以比全序性是指，线性结构的全部结点两两皆可以比较前后（关系较前后（关系 r）q单索性是指，每一个结点单索性是指，每一个结点 x 都存在唯一的一个都存在唯一的一个直接后继结点直接后继结点 y。如果其他结点。如果其他结点 z 在在 y 之前，则之前，则这个这个 z 也一定在也一定在 x 之前，不会在之前，不会在x，y之间之间 树型结构树型结构n简称树结构，或层次结构。其关系简称树结构，或层次结构。其关系 r 称为层次关称为层次关系，或称系，或称“父子关系父子关系”、“上下级关系上下级关系”等等n每一个结点可以有每一个结点

14、可以有多于一个的多于一个的“直接下级直接下级”，但，但是它只能有是它只能有唯一的唯一的“直接上级直接上级”。q树型结构的最高层次的结点称为树型结构的最高层次的结点称为根（根（root）结点）结点。只有。只有它它没有父结点没有父结点n树型结构存在着很多变种，如二叉树结构，堆结树型结构存在着很多变种，如二叉树结构，堆结构等，都有各自独特的有效应用构等，都有各自独特的有效应用图结构图结构n有时称为结点互联的有时称为结点互联的网络结构网络结构，因特网的网页链接关系就，因特网的网页链接关系就是一个非常复杂的图结构是一个非常复杂的图结构n对于图结构的关系对于图结构的关系 r 没有加任何约束。这样也就无法象

15、线没有加任何约束。这样也就无法象线性结构及树结构那样，利用关系性结构及树结构那样，利用关系 r 的约束来设计图结构的的约束来设计图结构的存储结构存储结构n在日常应用中图结构往往只是层次结构的一种扩展在日常应用中图结构往往只是层次结构的一种扩展允允许结点具有多个许结点具有多个“直接上级结点直接上级结点” ，关系，关系 r 表现为树型结表现为树型结构约束的放松构约束的放松 n从数学上看，树型结构和图结构的基本区别就是从数学上看，树型结构和图结构的基本区别就是“每个结每个结点是否点是否仅仅从属一个直接上级仅仅从属一个直接上级”。而线性结构和树型结构。而线性结构和树型结构的基本区别是的基本区别是“每个

16、结点是否每个结点是否仅仅有一个直接后继仅仅有一个直接后继”结点和结构结点和结构 n对于数据结构（对于数据结构（K, R），结点数据类型不限），结点数据类型不限于基本数据类型，可以根据应用需要来灵活于基本数据类型，可以根据应用需要来灵活设计结点的数据类型设计结点的数据类型文库专用22结点和结构结点和结构 n数据结构的设计也可采用数据结构的设计也可采用自顶向下自顶向下的方法的方法逐层进行逐层进行q先明确先明确数据结点数据结点，及其，及其主要关系主要关系 r q分析关系分析关系 r 的同时，也要分析其数据结点的的同时，也要分析其数据结点的数数据类型据类型q如果数据结点的逻辑结构比较复杂，那么把它如果

17、数据结点的逻辑结构比较复杂，那么把它作为下一个层次，再分析下一层次的逻辑结构作为下一个层次，再分析下一层次的逻辑结构数据的存储结构数据的存储结构n数据的存储（主存、外存）数据的存储（主存、外存）n计算机主存的特性计算机主存的特性q其存储空间提供了一种具有其存储空间提供了一种具有非负整数非负整数地址编码的、地址编码的、相邻单元相邻单元的集合，其基本的存储单元是的集合，其基本的存储单元是字节字节q计算机的指令具有计算机的指令具有按地址随机访问按地址随机访问存储空间内任存储空间内任意单元的能力，访问不同地址所需的访问时间基意单元的能力，访问不同地址所需的访问时间基本相同本相同 数据的存储结构数据的存

18、储结构n数据的存储结构是建立一种映射，对于数据逻辑结数据的存储结构是建立一种映射，对于数据逻辑结构（构（K ，r），其中），其中rRq对结点集合对结点集合 K 建立一个从建立一个从K到存储器到存储器M的单元的映射：的单元的映射：KM，对于每一个结点，对于每一个结点 jK 都对应一个都对应一个唯一唯一的的连续存连续存储储区域区域c Mq每一个关系元组（每一个关系元组（j1 ，j2）r（其中（其中j1， j2K是结点），是结点），亦即亦即j1， j2的逻辑后继关系应映射为存储单元的地址之间的逻辑后继关系应映射为存储单元的地址之间的顺序关系（或指针的地址指向关系）的顺序关系（或指针的地址指向关系）n

19、四种基本存储映射方法：四种基本存储映射方法：顺序、链接、索引、散列顺序、链接、索引、散列顺序方法顺序方法 n用一块连续的存储区域存储数据称为用一块连续的存储区域存储数据称为顺序存储顺序存储n顺序存储把一组结点存储在按地址相邻的顺序存顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用储单元里，结点间的逻辑后继关系用存储单元的存储单元的自然顺序关系自然顺序关系来表达来表达 n顺序存储法为使用整数编码来访问数据结点提供顺序存储法为使用整数编码来访问数据结点提供了便利了便利 02136547S顺序方法顺序方法 n顺序存储结构称为顺序存储结构称为紧凑存储结构紧凑存储结构，其紧凑性

20、是指，其紧凑性是指它的存储空间除了存储有用数据外，没有用于存它的存储空间除了存储有用数据外，没有用于存储其他附加的信息储其他附加的信息n紧凑性可以用紧凑性可以用“存储密度存储密度”来度量：它是一个存来度量：它是一个存储结构所存储的储结构所存储的“有用数据有用数据”和该结构（包括附和该结构（包括附加信息）整个存储空间大小之比加信息）整个存储空间大小之比n有时为了有时为了“用空间换取时间用空间换取时间”，在存储结构中存，在存储结构中存储一些附加信息还是很必要的储一些附加信息还是很必要的q譬如，用于提高算法的执行速度，或者让算法实现更为譬如，用于提高算法的执行速度，或者让算法实现更为简便等简便等 链

21、接方法链接方法 n利用指针，在结点的存储结构中附加指针字段称利用指针，在结点的存储结构中附加指针字段称为为链接法链接法。两个结点的逻辑后继关系。两个结点的逻辑后继关系用指针用指针来表来表达达n任意的逻辑关系任意的逻辑关系 r，均可使用这种指针地址来表达。，均可使用这种指针地址来表达。一般的做法是将数据结点分为两部分一般的做法是将数据结点分为两部分:q一部分存放结点本身的数据，称为一部分存放结点本身的数据，称为数据字段数据字段q一部分存放指针，称一部分存放指针，称指针字段指针字段，链接到某个后继结点，链接到某个后继结点，指向它的存储单元的开始地址。多个相关结点的依次链指向它的存储单元的开始地址。

22、多个相关结点的依次链接就会形成接就会形成链索链索链接方法链接方法 n对于经常增删结点的复杂数据结构，顺序存储往往对于经常增删结点的复杂数据结构，顺序存储往往会难以应付，而链接方法结合动态存储为这些复杂会难以应付，而链接方法结合动态存储为这些复杂问题提供了解决方法问题提供了解决方法n缺点：缺点：q为了访问结点集为了访问结点集 K 中某个结点，必须用该结点的存储指针中某个结点，必须用该结点的存储指针q当不知道结点指针时，为了在结点集当不知道结点指针时，为了在结点集 K中寻找某个符合条中寻找某个符合条件的结点，就要沿着链接结点的链索，按结点逐个比较搜件的结点，就要沿着链接结点的链索，按结点逐个比较搜

23、索，得花费相当可观的时间索，得花费相当可观的时间索引方法索引方法 n顺序存储法的一种推广，也使用顺序存储法的一种推广，也使用整数编码来整数编码来访问数据结点位置访问数据结点位置n建造一个由整数域建造一个由整数域 Z 映射到存储地址域映射到存储地址域D 的的函数函数Y：ZD，把，把结点的整数索引值结点的整数索引值 zZ 映射到映射到结点的存储地址结点的存储地址 dD 。Y称为称为索引函数索引函数索引方法示意索引方法示意 一般而言，索引函数并不象数组那样，是简单的线性一般而言，索引函数并不象数组那样，是简单的线性函数。当数据结点长度不等的情况下，索引函数就无函数。当数据结点长度不等的情况下，索引函

24、数就无法用线性表达式给出法用线性表达式给出索引方法索引方法n为了构造任意的索引函数，可为索引函数提供附为了构造任意的索引函数，可为索引函数提供附加的存储空间，称为加的存储空间，称为索引表索引表Sn索引表中每一元素是指向数据结点的指针。因为索引表中每一元素是指向数据结点的指针。因为索引表索引表 S 由等长元素（指针）组成，故可进行线由等长元素（指针）组成，故可进行线性的索引计算：性的索引计算： 始址始址(元素元素Si) 始址始址(元素元素S0) i （指针尺寸）（指针尺寸）通过上述公式，由索引号通过上述公式，由索引号 i 可以计算出索引表中的单元可以计算出索引表中的单元Si的始址，再通过读出的始

25、址，再通过读出Si元素的内容（指针），访问真元素的内容（指针），访问真正需要访问的数据结点正需要访问的数据结点索引方法索引方法n索引方法付出了存储的开销，其数据结点要附加索引方法付出了存储的开销，其数据结点要附加用于指针的存储空间用于指针的存储空间n索引方法在程序设计中是一种经常使用的方法，索引方法在程序设计中是一种经常使用的方法，主要原因是对于非顺序的存储结构来说，使用索主要原因是对于非顺序的存储结构来说，使用索引表是快速地由整数索引值找到其对应数据结点引表是快速地由整数索引值找到其对应数据结点的的唯一唯一方法方法散列方法散列方法 n索引方法的一种延伸和扩展索引方法的一种延伸和扩展n利用一种

26、称为利用一种称为散列函数散列函数(hash functions)的机制来的机制来进行索引值的计算，然后通过索引表求出结点的进行索引值的计算，然后通过索引表求出结点的指针地址指针地址n散列函数是将字符串散列函数是将字符串 s（ 或关键码）映射到非负或关键码）映射到非负整数整数 z 的一类函数的一类函数 h: S Z ， 对任意的对任意的 s S，散列函数，散列函数 h(s)=z，z Z散列方法散列方法 n散列函数散列函数h(s)除了取非负整数值外，关键的除了取非负整数值外，关键的问题包括：问题包括：q如何恰当地选择散列函数如何恰当地选择散列函数q如何建造散列表如何建造散列表q如何在构建散列表时解

27、决如何在构建散列表时解决“碰撞碰撞”问题问题文库专用35数据的运算数据的运算n作用于数据上的运算作用于数据上的运算q查、改、增、删，等等查、改、增、删，等等n不同的数据不同的数据文库专用36数据结构数据结构n抽象数据类型抽象数据类型存存储储数据数据结构结构逻逻辑辑运运算算文库专用37抽象抽象n计算机科学本身就是抽象的计算机科学本身就是抽象的科学科学 为问题建立适当的模为问题建立适当的模型并设计相应的技术解决它型并设计相应的技术解决它q相对于物理学相对于物理学n计算机本身的一些抽象计算机本身的一些抽象silicongatesregisters & processorsmachine la

28、nguagedevice drivers, : : :operating systemHigh level languageusern抽象的本质？抽象的本质？n简化简化n忽略非本质的部分忽略非本质的部分抽象数据类型抽象数据类型n模块化的思想的发展，为模块的划分提供了模块化的思想的发展，为模块的划分提供了理论依据理论依据 ，简称，简称ADT (Abstract Data Type)n目的目的q隐藏运隐藏运算实现的细节和内部数据结构算实现的细节和内部数据结构q提高复用的力度和粒度提高复用的力度和粒度ADTuser1user2usern.实现实现1 1实现实现2 2实现实现3 3抽象数据类型抽象数据

29、类型抽象数据类型抽象数据类型n用数学方法定义用数学方法定义对象对象集合和集合和运算运算集合，仅通过运算集合，仅通过运算的性质刻画数据对象，而独立于计算机中可能的表的性质刻画数据对象，而独立于计算机中可能的表示方法示方法q可看作是定义了一组操作的一个抽象模型可看作是定义了一组操作的一个抽象模型n例如，集合与集合的并、交、差运算就可定义为一个的抽例如，集合与集合的并、交、差运算就可定义为一个的抽象数据类型象数据类型q一个抽象数据类型要包括哪些操作，这一点由设计一个抽象数据类型要包括哪些操作，这一点由设计者根据需要确定者根据需要确定n例如，对于集合，如果需要，也可以把判别一个集合是否例如，对于集合，

30、如果需要，也可以把判别一个集合是否为空集或两个集合是否相等作为集合上的操作为空集或两个集合是否相等作为集合上的操作抽象数据类型抽象数据类型n由三元组由三元组 表示表示q数据对象数据对象Dq数据关系数据关系Sq数据操作数据操作P文库专用42抽象数据类型抽象数据类型template / 模板参数为类型模板参数为类型Typeclass className private: / 数据结构的的取值类型和取值空间数据结构的的取值类型和取值空间Type dataList; / 定义数据及其存储方式定义数据及其存储方式. public: / 运算集运算集methodName(); / 定义对数据的操作定义对数

31、据的操作; 文库专用43数据结构数据结构文库专用44算法算法算法算法n对特定问题求解过程的描述，是指令的有限对特定问题求解过程的描述，是指令的有限序列，也即，为解决某一特定问题而采取的序列，也即，为解决某一特定问题而采取的具体有限的操作步骤。具体有限的操作步骤。n程序是算法的一种实现，计算机按照程序逐程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。步执行算法，实现对问题的求解。文库专用46算法算法n用计算装置能够理解的语言描述的解题过用计算装置能够理解的语言描述的解题过程，具有如下性质：程，具有如下性质：q将它作用于所求解的问题的给定输入集上，或将它作用于所求解的问题的给定

32、输入集上，或作用于问题自身的描述上，将产生唯一确定的作用于问题自身的描述上，将产生唯一确定的动作序列，此序列是有限的；动作序列，此序列是有限的；q此序列或终止于给出问题的解，或终止于指出此序列或终止于给出问题的解，或终止于指出问题对此输入无解问题对此输入无解 有穷性；确定性；有穷性；确定性； 可行性；可行性； 输入；输入； 输出输出算法的特性算法的特性n 通用性通用性o对于符合输入类型的任意输入数据，都能根据算法进行对于符合输入类型的任意输入数据，都能根据算法进行问题求解，并保证计算结果的正确性问题求解，并保证计算结果的正确性n有效性有效性q组成算法的每一条指令都必须是能够被（人或机器）确组成

33、算法的每一条指令都必须是能够被（人或机器）确切执行的，且指令的类型应该明确规定，其结果应具有切执行的，且指令的类型应该明确规定，其结果应具有确定的数据类型，是能够预期的确定的数据类型，是能够预期的n确定性确定性q保证每一步之后都有关于下一步动作的指令，不能缺乏保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令（被锁住）或仅仅含有模糊不清的指令下一步指令（被锁住）或仅仅含有模糊不清的指令n有穷性有穷性q算法的执行必须在有限步内结束。换句话说，算法不能算法的执行必须在有限步内结束。换句话说，算法不能含有死循环含有死循环 算法分类算法分类n算法设计与算法分析是计算机科学的核心问题算法设计与算

34、法分析是计算机科学的核心问题n常用的设计方法常用的设计方法q穷举法穷举法(百钱买百鸡百钱买百鸡)q贪心法贪心法(Huffman树、树、Prim等等)q递归法递归法, 分治法分治法(二分检索、快速排序等二分检索、快速排序等)q回溯法回溯法(树、图等的深度优先搜索）树、图等的深度优先搜索）q动态规划法动态规划法(最佳二叉排序树最佳二叉排序树)q-裁剪和分枝界限法裁剪和分枝界限法q并行算法并行算法49计算复杂性和算法的效率计算复杂性和算法的效率n根据计算理论，存在着一类问题虽然能够被准确定根据计算理论，存在着一类问题虽然能够被准确定义，但却不存在能够解决该问题的算法。称为义，但却不存在能够解决该问题

35、的算法。称为不可不可解问题解问题n计算复杂性理论指出，理论上存在一大类难解问题计算复杂性理论指出，理论上存在一大类难解问题，它们虽然存在着求解算法，但在算法的计算时间，它们虽然存在着求解算法，但在算法的计算时间上，都是组合爆炸型的求解算法上，都是组合爆炸型的求解算法q随着问题的规模随着问题的规模 n 的增大，算法的时间开销不能约束在的增大，算法的时间开销不能约束在 n 的的 k 阶多项式数量范围内。（其中阶多项式数量范围内。（其中 k是任意不依赖于是任意不依赖于 n 的的常数）常数） q比较常见的难解问题有：图论中的求最优巡游路径问题，比较常见的难解问题有：图论中的求最优巡游路径问题，判定命题

36、逻辑公式是否为恒真等判定命题逻辑公式是否为恒真等算法的执行效率及其度量算法的执行效率及其度量n解决同一个问题存在多种算法，如何评估各算法的解决同一个问题存在多种算法，如何评估各算法的好坏？或据此设计出更好的算法？好坏？或据此设计出更好的算法？q运行该算法所需要的计算机资源的多寡，所需越大复杂性运行该算法所需要的计算机资源的多寡，所需越大复杂性越高越高q最重要的资源：时间（处理器）和空间（存储器）最重要的资源：时间（处理器）和空间（存储器）n评价一个算法优劣的重要依据是看执行该算法的程评价一个算法优劣的重要依据是看执行该算法的程序需要占用多少机器资源：序需要占用多少机器资源：q程序所用算法运行时

37、所要花费的时间代价程序所用算法运行时所要花费的时间代价q程序中使用的数据结构占有的空间代价程序中使用的数据结构占有的空间代价文库专用51算法的执行效率及其度量算法的执行效率及其度量n需要明确：需要明确：n如何表达一个算法的复杂性如何表达一个算法的复杂性n怎样计算一个算法的复杂性怎样计算一个算法的复杂性算法时间复杂性算法时间复杂性n不能用诸如微秒、纳秒这样的真实时间单位不能用诸如微秒、纳秒这样的真实时间单位q一个运行在一个运行在Cray机上的算法若放在机上的算法若放在PC机会慢很多机会慢很多q一个运行在一个运行在Cray机上的效率极差的算法也许比一个机上的效率极差的算法也许比一个运行在运行在PC

38、上的效率很高的算法花费更少的时间上的效率很高的算法花费更少的时间q同样的算法运行在同样的机器上也会因使用不同的程同样的算法运行在同样的机器上也会因使用不同的程序语言而存在差异序语言而存在差异nC vs LISPq两个不同的算法也许在输入规模为两个不同的算法也许在输入规模为100时表现不相上时表现不相上下，而在输入规模扩大下，而在输入规模扩大10倍后却表现迥异倍后却表现迥异算法复杂性分析算法复杂性分析n算法分析感兴趣的不是具体的资源占用量，算法分析感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无而是与具体的平台无关、具体的输入实例无关，且随输入规模增长的值是可预测的关，且随输

39、入规模增长的值是可预测的q与问题的规模之间的关系，用一定与问题的规模之间的关系，用一定“规模规模(size)”的数据作为输入时程序运行所需的的数据作为输入时程序运行所需的“基本操作基本操作(basic operation) ” 数来描述时间效率。数来描述时间效率。q完成一个完成一个“基本操作基本操作”所需的时间应该与具体所需的时间应该与具体的被操作的数无关的被操作的数无关算法的渐进分析算法的渐进分析nasymptotic analysis，简称算法分析q由于算法的复杂性与其所求解的问题规模直接由于算法的复杂性与其所求解的问题规模直接有关，因此通常将有关，因此通常将问题规模问题规模 n 作为一个

40、参照量作为一个参照量，求算法的时空开销和，求算法的时空开销和 n 的关系的关系q一般这种函数关系都相当复杂，计算时只考虑一般这种函数关系都相当复杂，计算时只考虑可以显著影响函数量级的部分，即结果为原函可以显著影响函数量级的部分，即结果为原函数的一个近似值数的一个近似值q对资源开销的一种不精确估计，提供对于算法对资源开销的一种不精确估计，提供对于算法资源开销进行评估的简单化模型资源开销进行评估的简单化模型算法的渐进分析算法的渐进分析n算法的渐进分析就是要估计，当数据规模算法的渐进分析就是要估计，当数据规模 n逐逐步增大时，资源开销步增大时，资源开销f(n)的增长趋势的增长趋势n得到如此精确的一个

41、界相对比较费时费力，且得到如此精确的一个界相对比较费时费力，且没有必要没有必要n从数量级大小的比较来考虑，当从数量级大小的比较来考虑，当n增大到一定值增大到一定值以后，资源开销的计算公式中影响最大的就是以后，资源开销的计算公式中影响最大的就是n的的幂次最高的项，其他的常数项和低幂次项都是可幂次最高的项，其他的常数项和低幂次项都是可以忽略的以忽略的 1000nlog100nn)n(f102算法渐进分析：算法渐进分析：大表式法大表式法n假设假设f 和和g为从自然数到非负实数集的两个函数为从自然数到非负实数集的两个函数定义定义1：如果存在正数：如果存在正数c和和N，使得对任意的，使得对任意的n N，

42、都有，都有f(n) cg(n)，则称则称f(n)在集合在集合O(g(n)中，或简称中，或简称f(n)是是O(g(n)的的 q说明了函数说明了函数 f 和和 g 关系：函数关系：函数g(n) 是函数是函数 f(n) 取值的上取值的上限（限（upper bound），或说函数），或说函数f的增长最终至多趋同于的增长最终至多趋同于g的增长的增长q大大O表示法提供了一种表达函数增长率上限的方法表示法提供了一种表达函数增长率上限的方法 q一个函数增长率的上限可能不止一个。大一个函数增长率的上限可能不止一个。大O表示法给出了表示法给出了所有上限中最所有上限中最“紧紧”（也即最小）的那个上限（也即最小）的那

43、个上限57大表式法的性质大表式法的性质n若符号若符号a是不依赖于是不依赖于n的任意常数的任意常数 q如果函数如果函数 f(n) 是是O(g(n)的，的，g(n)是是O(h(n)，那么，那么f(n)是是O(h(n)的的q如果函数如果函数f(n)是是O(h(n)的，的，g(n)是是O(h(n)，那么，那么f(n) + g(n) 是是O(h(n)的的q函数函数ank是是O(nk)的的q对任何正数对任何正数 j 而言，函数而言，函数nk 是是O(nk+j)的的q若若f(n) = cg(n)，则，则f(n) 是是O(g(n)的的q对于任何正数对于任何正数a和和b，且，且b 1，函数，函数logan 是是

44、O(logbn)的。的。即，任何对数函数无论底数为何，都具有相同的增长率即，任何对数函数无论底数为何，都具有相同的增长率1.对任何正数对任何正数 a 1，都有，都有logan 是是O(lg n)的，其中的，其中lg n = log2n大大O表示法的运算规则表示法的运算规则n单位时间单位时间q简单布尔或算术运算简单布尔或算术运算q简单简单I/Oq函数返回函数返回n加法规则加法规则: f1(n)+f2(n)=(max(f1(n), f2(n)q顺序结构，顺序结构，if 结构，结构，switch结构结构n乘法规则乘法规则: f1 (n)f2 (n) =(f1(n)f2 (n)qfor, while,

45、 do-while结构结构算法渐进分析：算法渐进分析： 表式法表式法n定义定义2 ：如果存在正数：如果存在正数c和和N，使得对所有的，使得对所有的n N，都有都有f(n) cg(n)，则称则称f(n)在集合在集合 (g(n) 中，或简称中，或简称f(n) 是是 (g(n)的的 q说明了说明了cg(n)是函数是函数f(n)取值的下限（取值的下限（lower bound），或说函数），或说函数f的增长最终至少是趋同于函的增长最终至少是趋同于函数数g的增长的增长q正如大正如大O表示法，表示法， 表示法也是在函数增值率的表示法也是在函数增值率的所有下限中那个最所有下限中那个最“紧紧”（即最大）的下限（

46、即最大）的下限算法渐进分析：算法渐进分析： 表式法表式法n当上、下限相同时则可用当上、下限相同时则可用 表示法。定义如表示法。定义如下：下：如果一个函数既在集合如果一个函数既在集合O (g(n)中又在集合中又在集合 (g(n)中，则称其为中，则称其为 (g(n)。 也即，也即，存在正常数存在正常数c1, c2，以及正整数，以及正整数n0，使得对于任意，使得对于任意的正整数的正整数n n0 ，有下列两不等式同时成立，有下列两不等式同时成立c1 g(n) f(n) c2 g(n)渐进分析示例渐进分析示例n对数组中的各个元素求和的代码：对数组中的各个元素求和的代码：for (i = sum = 0;

47、 in; i+） sum += ai;其中主要的操作为赋值运算，故该算法的时其中主要的操作为赋值运算，故该算法的时间代价主要体现在赋值操作的数目上间代价主要体现在赋值操作的数目上p在循环开始之前有两次赋值，分别对在循环开始之前有两次赋值，分别对 i 和对和对sum进行；进行；p循环进行了循环进行了n 次，每次循环中执行两次赋值，分别对次，每次循环中执行两次赋值，分别对 sum和对和对 i 进行更新操作；进行更新操作；p总共有总共有2 + 2n 次赋值操作次赋值操作其渐进复杂度为其渐进复杂度为O(n) 渐进分析示例渐进分析示例n依次求出给定数组的所有子数组中各元素之和：依次求出给定数组的所有子数

48、组中各元素之和：for (i = 0; i n; i+) for (j = 1, sum = a0; j = i; j+) sum += aj;)n(O)n(O) n(O) 1n( n3n1) 1n.21 ( 23n12i3n1221n1io循环开始前，有一次对i的赋值操作。o外层循环共进行n次，每个循环中包含一个内层循环，以及对i, j, sum分别进行赋值操作；n每个内层循环执行每个内层循环执行2个赋值操作，分别更新个赋值操作，分别更新sum 和和 j；共执行；共执行i次次（i=1,2, ,n-1）。）。o整个程序总共执行的赋值操作为：渐进分析示例渐进分析示例n若只对每个子数组的前若只对每

49、个子数组的前5个元素求和，则相应的代个元素求和，则相应的代码可采用下面的方式：码可采用下面的方式：for ( i=4; in; i+) for (j = i-3, sum = ai-4; j = i; j+) sum += aj; o外层循环进行外层循环进行n-4次次o对每个对每个 i 而言，内层循环只执行而言，内层循环只执行4次，每次的操次，每次的操作次数和作次数和 i 的大小无关：的大小无关：8次赋值操作次赋值操作o整个代码总共进行整个代码总共进行O(1)+O(n) +8(n-4)=O(n)次次 o看似双重循环，其实线性时间看似双重循环，其实线性时间增长率函数曲线增长率函数曲线各时间量级在

50、现实中对应的物体速度各时间量级在现实中对应的物体速度米米/ /秒秒英制度量衡英制度量衡现实世界的例子现实世界的例子1010-11-111010-10-101010-9-91010-8-81010-7-71010-6-61010-5-51010-4-41010-3-31010-2-21010-1-11 110101 110102 210103 310104 410105 510106 610107 710108 81.2 1.2 英寸英寸/ /世纪世纪1.21.2英寸英寸/ /十年十年1.2 1.2 英寸英寸/ /年年1 1 英尺英尺/ /年年1 1英尺英尺/ /月月 3.43.4英寸英寸/ /

51、天天1.41.4英寸英寸/ /时时1.21.2英尺英尺/ /时时2 2英寸英寸/ /分分2 2英尺英尺/ /分分2020英尺英尺/ /分分2.22.2英里英里/ /时时 2222英里英里/ /时时 220220英里英里/ /时时3737英里英里/ /分分370370英里英里/ /分分37003700英里英里/ /分分620620英里英里/ /秒秒62006200英里英里/ /秒秒62,00062,000英里英里/ /秒秒钟乳石的生长速度钟乳石的生长速度大陆板块的漂移速度大陆板块的漂移速度指甲的生长速度指甲的生长速度头发的生长速度头发的生长速度杂草的生长速度杂草的生长速度冰河的流动速度冰河的流动

52、速度表的分针转动速度表的分针转动速度胃肠的蠕动速度胃肠的蠕动速度蜗牛的速度蜗牛的速度蚂蚁的速度蚂蚁的速度巨龟的速度巨龟的速度人类的散步速度人类的散步速度人类疾跑速度人类疾跑速度螺旋桨飞机的速度螺旋桨飞机的速度喷气式飞机的速度喷气式飞机的速度宇宙飞船的速度宇宙飞船的速度流星撞击地球的速度流星撞击地球的速度地球自转速度地球自转速度卫星从洛杉矶到纽约的速度卫星从洛杉矶到纽约的速度光速的三分之一光速的三分之一运行时间估算运行时间估算n例：假设例：假设CPU每秒处理每秒处理10 6 个指令，对于输入规个指令，对于输入规模为模为108的问题，时间代价的问题，时间代价T(n) = 2n2的算法要运的算法要运

53、行多长时间？行多长时间？q操作次数为操作次数为T(n) = T(108) = 2(108)2 = 21016q运行时间为运行时间为21016/106 = 21010秒秒q一天有一天有86,400秒，故需要秒，故需要231,480 天，即天，即634年年运行时间估算运行时间估算n例：假设例：假设CPU每秒处理每秒处理106个指令，对于输入个指令，对于输入规模为规模为108的问题，时间代价为的问题，时间代价为nlog n 的算的算法要运行多长时间？法要运行多长时间？q操作次数为操作次数为 T(n) = T(108) = 108 log 108 = 2.66109q运行时间为运行时间为2.66109

54、/106 = 2.66103秒，即秒，即44.33分钟分钟规定时间内处理问题的规模规定时间内处理问题的规模n设设CPU每秒处理每秒处理106个指令，则每小时能够个指令，则每小时能够解决的最大问题规模解决的最大问题规模 T(n) / 106 3600n对对T(n) = 2n2，q即即2n2 3600 106qn 42 , 426nT(n) = nlog nq即即nlogn 3600 106q n 133 , 000 , 000加快硬件速度？加快硬件速度？T(n)处理输入规模为处理输入规模为n=108 1小时内解决的问题规模小时内解决的问题规模106指令指令/秒秒108指令指令/秒秒106指令指令

55、/秒秒108指令指令/秒秒n log n 44.33 秒秒0.4433秒秒1.33亿亿100亿亿2n2634年年6.34年年42,426424,264 CPU每秒处理每秒处理个指令（快个指令（快100倍）倍）处理时间降为原来的处理时间降为原来的1/100- 解决问题的规模解决问题的规模对对规模增加规模增加10倍倍规模增加规模增加75倍倍最差、最佳、平均情况最差、最佳、平均情况n在进行算法增长率估计时，有些算法，即使问题规在进行算法增长率估计时，有些算法，即使问题规模相同，若输入数据不同，其时间复杂度也不同模相同，若输入数据不同，其时间复杂度也不同q由于算法实际执行的操作往往依赖于分支条件的走向

56、由于算法实际执行的操作往往依赖于分支条件的走向，而输入数据的取值又影响这些分支走向，因此很多，而输入数据的取值又影响这些分支走向，因此很多算法都无法得出独立于输入数据的渐进估计算法都无法得出独立于输入数据的渐进估计n针对这一情况，提出了最差情况估计、平均情况估针对这一情况，提出了最差情况估计、平均情况估计、最佳情况估计等三种方法计、最佳情况估计等三种方法 示例示例n求一个数组的所有有序子数组中最长的一个：求一个数组的所有有序子数组中最长的一个：for (i = 0, length=1; in-1; i+) for (j1 = j2 = k = i; k n-1 & ak ak+1; k

57、+, j2+);if (length j2 - j1 - 1)length = j2 - j1 + 1;譬如，在数组譬如，在数组1, 8, 1, 2, 5, 0, 11, 9中，这个最长的中，这个最长的有序子数组为有序子数组为1，2，5，长度为，长度为3。时间代价和数组时间代价和数组 a 中元素的实际取值状态很相关中元素的实际取值状态很相关示例：最佳示例：最佳n数组数组a的所有元素是以降序方式输入的所有元素是以降序方式输入q外层循环执行外层循环执行n-1次，次，q每次内层循环只执行每次内层循环只执行1次次q整个的时间开销为整个的时间开销为O(n)min complexity(size(y) | y Input示例：最差示例：最差n数组数组 a 的所有元素是以升序方式输入的所有元素是以升序方式输入q外层循环执行