算法分析与设计

1、第 1 页 共 148 页目录目录第一章第一章绪论绪论.31.1 算法的概念.31.2 算法问题求解基础.61.3 重要的问题类型.91.4 基本数据结构.11第二章第二章算法效率分析基础算法效率分析基础.162.1 分析框架.162.2 渐进符号和基本效率类型.192.3 非递归算法的数学分析.222.4 递归算法的数学分析.252.5 例：fibonacci数列.27第三章第三章蛮力法（蛮力法（brute force）和算术问题）和算术问题.333.1 选择排序和冒泡排序.333.2 蛮力字符串匹配.353.3 穷举搜索（exhaustive search）.363.4 基本算术.403.

2、5 模算术.423.6 素性检测.423.7 密码学.42第四章第四章分治法（分治法（devide-and-conqure）.434.1 主定理（master theorem）.434.2 归并排序.444.3 快速排序.464.4 大整数乘法.494.5 strassen矩阵乘法.504.6 快速傅里叶变换 fft.52第五章第五章减治法（减治法（decrese-and-conqure）.585.1 插入排序.585.2 深度优先搜索和广度优先搜索.595.3 生成组合对象的算法.635.4 二叉搜索（折半查找）.675.5 乘法和乘方问题.695.6 euclid算法分析.71第六章第六章

3、时空权衡（时空权衡（time and space tradeoffs）与动态规划（）与动态规划（dynamic programming）.726.1 计数排序.726.2 高效串匹配算法.736.3 再谈 fibonacci数列.78第 2 页 共 148 页6.4 有向无环图中最短路径.796.5 计算传递闭包的 warshall算法和多源最短路径问题的 floyd算法 .816.6 矩阵链相乘问题.846.7 最优二叉搜索树.866.8 最长递增子序列.896.9 编辑距离.896.10 背包问题.926.11 旅行商 tsp 问题.95第七章第七章贪心法（贪心法（greedy techn

4、iques）.997.1 连续背包问题.997.2 最小生成树问题（mst，minimum spanning tree）.1027.3 单源最短路径问题的 dijkstra算法.1097.4 huffman编码.1127.5 集合覆盖.118第八章第八章线性规划（线性规划（linear programming）.1198.1 线性规划简介.1198.2 求解线性规划问题的单纯形算法.1228.3 网络流问题.1298.4 二部图的匹配问题.1298.5 对偶.1298.6 零和游戏.130第九章第九章算法能力的极限算法能力的极限.1319.1 求算法下界的方法.1319.2 问题归约.1329

5、.3 p，np 和 np 完全问题.1349.4 回溯法（backtracking）.1399.5 分支限界法（branch-and-bound）.1419.6 近似算法（approximation algorithms）.144第 3 页 共 148 页第一章第一章绪论绪论1.1 算法的概念算法的概念算法：解决一个问题的算法：解决一个问题的无歧义无歧义的指令序列，对的指令序列，对合法的输入合法的输入在在有有限限的时间内可得到需要的的时间内可得到需要的输出输出。算法的一些特点：算法的一些特点： 无歧义性（确定性）：算法的每个步骤必须确定无疑无歧义性（确定性）：算法的每个步骤必须确定无疑 有穷性

6、：算法的执行必须有限步终止有穷性：算法的执行必须有限步终止 输入的范围：算法只对输入的范围：算法只对满足条件的输入有响应满足条件的输入有响应 正确性：算法应能解决要求的问题正确性：算法应能解决要求的问题 同一算法的不同表示形式：自然语言、伪代码、高级语言同一算法的不同表示形式：自然语言、伪代码、高级语言 同一问题存在的多种算法：同一问题存在的多种算法：设计思想不同，时空性能各异设计思想不同，时空性能各异例，求两个正整数 m 和 n 的最大公因子的算法算法一最容易想到的算法挨个检查step 1t = min m, nstep 2如果 m 除以 t 的余数为 0，转 step 3；否则，转 ste

7、p 4；step 3如果 n 除以 t 的余数为 0，返回 t 的值；否则，转 step 4；step 4t = t 1，转 step 2。分析：分析： 上述步骤每一步均确定没有歧义，是一个循环结构程序这才叫算法这指特定问题的算法第 4 页 共 148 页 循环执行次数未知，那么它会有限步终止吗？（每次（每次 t 1） 该算法由自然语言描述自然语言描述 该算法正确吗？如何证明？该算法正确吗？如何证明？算法二小学数学中讲述的算法step 1将 m 分解质因子；step 2将 n 分解质因子；step 3寻找 step 1 和 step 2 得到的两个质因子连乘积的公共部分（注：若 m 的分解中质

8、因子 p 出现了 x 次，n 的分解中 p 出现了 y 次，作为公共部分，p 应出现 minx, y次） ；step 4计算公共部分的连乘积，并将结果返回。分析：分析：此算法中，如何分解质因子没说明，如何寻找公共部分不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法严格讲起来不能称为算法，至少有待进一步具体说明！考虑如何具体说明：考虑如何具体说明： 分解质因子需要知道有哪些质数分解质因子需要知道有哪些质数 寻找公共部分涉及到质因子连乘积的表示形式寻找公共部分涉及到质因子连乘积的表示形式算法三euclid 算法（记录于公元前 3 世纪 euclid 所著的elements）euclid

9、(m, n)/input：两个正整数 m 和 n/output：m 和 n 的最大公因子while n0 do第 5 页 共 148 页r = m mod nm = nn = rreturn m分析：分析： 上述步骤每一步均确定没有歧义，是一个循环结构程序 循环执行次数未知，那么它有限步终止吗？（每次（每次 n 都减小）都减小） 该算法由伪代码描述：伪代码是自然语言和编程语言的混合伪代码描述：伪代码是自然语言和编程语言的混合 该算法正确吗？如何证明？该算法正确吗？如何证明？证明：证明：设函数 gcd(m, n)就是采用 euclid 算法计算最大公因子的函数。则算法的正确性基于两个事实： 若

10、m0，则 gcd(m, 0)= m gcd(m, n) = gcd(n, m mod n)第一个事实显然易见。设 d = gcd(m, n)且 m = kn + t。则存在 a，b 使得 m = ad，n = bd，且 a 与 b 互质。m mod n = t = m kn = ad kbd =(a kb)*d。说明 d 是 n 和 m mod n 的公因子，还需说明，b 与 a kb 互质。假设 b 与 a kb 有公因子 c。即，b = uc，a kb = vc。则 a = kuc + vc =(ku + v)*c，m =(ku + v)*cd，n = bd = ucd，由 d是 m 与

11、n 的最大公因子得 c=1，即 b 与 a kb 互质。第 6 页 共 148 页比较上述三个算法，很明显，euclid 算法形式简单，循环次数算法形式简单，循环次数少少（后面会进行详细分析）（后面会进行详细分析） ，所以我们说 euclid 算法更高效。算法更高效。1.2 算法问题求解基础算法问题求解基础算法是求解的具体指令，不是解答。算法是求解的具体指令，不是解答。设计和分析算法的典型步骤：设计和分析算法的典型步骤：1.理解问题理解问题1) 仔细阅读问题描述2) 手工测试几个例子3) 思考特殊情形4) 分析是否已有该类问题的算法2.确定计算设备的能力确定计算设备的能力现行的绝多数算法都是基

12、于冯诺依曼机器模型的，即，随机存储模型，它假定指令依次执行，每次执行一个操作，在这样机器上执行的算法称为 sequential 算法算法。适合于现在新兴的可同时执行多条操作的计算机的算法，称为并行算法并行算法。除非对某些本质上复杂、需处理大量数据或者对时间要求很高除非对某些本质上复杂、需处理大量数据或者对时间要求很高的问题，的问题，无需担心现在计算机的能力！无需担心现在计算机的能力！3.选择精确算法还是近似算法选择精确算法还是近似算法1) 存在某些问题不能精确解决，例如求平方根2) 可精确解决的算法难以接受的慢，例如，tsp 问题3) 近似算法可以是某些更为复杂的精确算法的组成部分第 7 页

13、共 148 页4.确定合适的数据结构确定合适的数据结构存在某些算法设计方法固有依赖于描述问题的数据结构。5.算法设计方法算法设计方法本课程所要解决的主要问题主要问题。算法设计方法（或策略）是指：从算法上解决问题的通用方法，可适用于不同领域的各种各样的问从算法上解决问题的通用方法，可适用于不同领域的各种各样的问题题。学习这些方法的原因：1) 有助于为新问题设计算法，授人以鱼不如授人以渔授人以鱼不如授人以渔2) 每门学科都对其研究主题进行分类，算法是计算机科学的基础，有助于根据设计思想对算法进行分类6.描述算法的方法描述算法的方法1) 自然语言描述，如前例中算法一、二2) 伪代码描述，如前例中算法

14、三 euclid 算法，无统一格式3) 流程图，只适合于描述很简单的算法4) 某种计算机语言写成的程序7.证明算法的正确性证明算法的正确性一旦算法描述清楚，就需要证明其正确性，即，它对每一个合法的输入都可以在有限的时间内得出需要的结果。证明算法正确的一个常用方法是：数学归纳法。数学归纳法。注意：测试几组输入数据的方法虽然简单，但却不足以说明算注意：测试几组输入数据的方法虽然简单，但却不足以说明算法正确！法正确！不过却可以说明一个算法不正确！不过却可以说明一个算法不正确！8.算法分析算法分析第 8 页 共 148 页算法应具有的几个品质：算法应具有的几个品质：本课程所要解决的主要问题主要问题1)

15、 正确性正确性2) 效率效率：时间效率和空间效率。第二章详述3) 简洁性简洁性：无法用数学定义精确描述，最好给人以美感例，前述的求 gcd 的算法哪个更简单？简单的算法易于理解，易于编程，通常包含较少的 bug，一般也更有效率4) 通用性通用性：同样的效率，解决的问题可适用范围当然越广越好，但是有时通用算法难设计且效率差，或者根本无通用算法例，判定两个正整数是否互质的算法就没有求 gcd 的通用；二次方程求根公式存在的，但没有任意次方程的求根方法9.算法编码实现算法编码实现1) 注意程序严格准确的实现算法2) 算法到程序的过渡：算法中假设输入都是合法的，程序中需验证3) 程序的正确性验证的实际

16、方式：测试（testing） 。4) 学习编程技巧，以提高程序效率最优算法（最优算法（optimality）：不是算法效率的问题，而是算法解决问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价最少。某些问题的最优算法是存在的，比如，通过比较进行排序的最优算法需要进行 n log n 次比较；但某些看上去简单的问题，还未找到最优算法，例如，矩阵乘法。不可判定性不可判定性(undecidability)：不是说，每个问题均有算法解决第 9 页 共 148 页（注意，这不同于一个问题没有解这不同于一个问题没有解，例如，判别式为负的二次方程无实数解） 。所幸的是，实际计算中的绝大多数问题还是有

17、解决算法的。1.3 重要的问题类型重要的问题类型后面的章节将以以下问题展开，讨论不同算法的设计技术与分析方法。1. 排序排序我们经常遇到排序问题，比如学校学生按学号排序，学号通常被称为 key。那么为什么要进行排序为什么要进行排序？排序使得很多关于列表的问排序使得很多关于列表的问题简单题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法排序还常作为某些领域重要算法的辅助步骤的辅助步骤，比如，在几何算法中。当前，已有很多排序算法，在这些算法当中，有些较好的可将任意 n 个元素通过大约 n log2 n 比较完成排序，但是没有哪一个通过没有哪一个通过关键字比较的排序算法能比关键字比较的排序算

18、法能比 n log2 n 作的更好作的更好！排序算法的两个性质：排序是否稳定稳定（保持输入相等元素的相对次序不变）和是否需要大量辅助空间（in place 排序） 。2. 搜索（查找）搜索（查找）同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜索（要求元素已排序） ，等等。由于搜索经常与添加和删除操作联系在一起，所以，需仔细设需仔细设计数据结构计数据结构。第 10 页 共 148 页3. 字符串处理字符串处理由于所有程序在计算机看来都是字符串，所以此类算法同计算机语言和编译紧密相关。此类算法中最特殊的一个字符串匹配字符串匹配在给定文本中搜索给定单词，在实际中非常有用。4. 图论问题图论问

19、题算法中最古老而又吸引人的领域就是图算法。图可以看作是由若干结点和若干个连接其中某些结点的边所构成，其准确定义下一小节给出。图可以为日常很多应用建模，比如，交通和通信网，项目调度，博弈。最基本的图算法包括：图遍历算法图遍历算法（如何遍历网络中所有结点） ，最小生成树算法最小生成树算法（如何铺设最经济的通信网络） ，最短路径算法最短路径算法（如何确定两城市间的最佳路线） ，有向图的拓扑排序有向图的拓扑排序（如何确定专业课程的学习顺序） ，等等。有些图论问题非常复杂，以至于最快的计算机也只能解决较小规模的这类问题，比如，旅行商问题旅行商问题（遍历 n 个城市每个一次的最短线路）和图着色问题图着色问

20、题（给图的结点着色以使相邻结点颜色不同的最少颜色数） ，例如，多叉路口交通灯的设计就是一个图着色问题。5. 组合问题组合问题更抽象的讲，旅行商问题和图着色问题都是组合问题的例子。组合问题寻求满足某些约束条件或者某些期望性质的组合对象（排列，组合，多重集） 。第 11 页 共 148 页组合问题被认为是计算机科学中最困难的问题，因为： 随着问题规模扩大，组合对象的数目急剧扩大随着问题规模扩大，组合对象的数目急剧扩大 没有已知的算法可在可接受的时间内解决大多数此类问题没有已知的算法可在可接受的时间内解决大多数此类问题 大多数计算机科学家相信不存在可接受时间内解决此类问题大多数计算机科学家相信不存在

21、可接受时间内解决此类问题的算法，但不能证实和证伪的算法，但不能证实和证伪6. 几何问题几何问题几何问题处理点、线、多边形。 应用领域包括计算机图形学，机器人学，x 线断层摄影学。典型算法，比如寻找平面内 n 个点中的最近点对算法。7. 数值问题数值问题涉及到数学问题的求解，比如，解方程或方程组，计算定积分，等等。大多数这类问题只能近似解决，主要一个原因是他们的操作对象是实数，计算机只能够近似表述。1.4 基本数据结构基本数据结构1. 线性数据结构线性数据结构两种基本的线性数据结构是数组和链表数组和链表。数组的特点： 每个元素类型相同，占有同样大小的存储空间 整个数组连续存储，任意元素可通过下标

22、随机访问随机访问单（双、循环）链表的特点： 非连续存储，访问某个元素的时间与其在链表中的位置有关第 12 页 共 148 页 无需预留存储空间，插入和删除操作方便数组和链表均可用于实现抽象数据结构线性表，其基本操作是：搜索、插入、删除。两种特殊的线性表：栈（lifo）和队列（fifo） 。2. 图图图 g =(v, e)，其中 v 是顶点（结点）的有限集，e 是顶点对（边）所构成的集合。如果边没有方向性，称 g 是无向图；否则，称 g 为有向图。aedcbdfacfeb 例：如上左图为无向图，其中 v=a, b, c, d, e, f，e=(a, c), (a, d), (b, c), (b,

23、 f), (c, e), (d, e), (e, f)；右图为有向图，其中 v=a, b, c, d, e, f，e=(a, c), (b, c), (b, f), (c, e), (d, a), (d, e), (e, c), (e, f)。图的定义不禁止圈（loop，自回路） ，但除非明确说明，我们所讲的图不包含圈。 无向图的性质：0 |e| |v|(|v| 1)/ 2 完全图：每对顶点均有边相连，|v|个顶点的完全图记作 k|v| 稠密图（dense）和稀疏图（sparse）图的表示：算法中最主要的两种表示是邻接矩阵和邻接表。上左图的邻接矩阵和邻接表表示如下：fedcba第 13 页 共

24、 148 页fedcba010010101100010001010011100100001100acbfedcfebcaacdedebf对无向图而言，其邻接矩阵总是对称对称的。why？显然，稀疏图用邻接表更节省存储空间。why？但具体某问题采用何种表示，更加依赖于解决该问题的算法的性质。 加权图（weighted graph）：图中边赋有值，称为权或 cost。比如实际应用中，交通图中两城市间的公路距离。邻接矩阵和邻接表均可用于存储加权图。矩阵中的值可表示距离（无边的是为） ，邻接表的每一结点可添加一项表示距离adcb523187ab,2bdca,2a,5a,7c,5c,8b,3b,8d,7d

25、,3d,1c,1 路径（path）：从顶点 u 到顶点 v 的路径，是指始于 u 终于v 有边连接的顶点序列（有向图中，要求边的方向均为从 u至 v 方向） 。若除起止点外路径中无顶点重复，称简单路径简单路径。路径长度指路径中的边数（即，顶点数减 1） 。 连通图（connected）：图中的每对顶点均有路径连接 子图（subgraph）：图 g=(v, e)称为图 g 的子图，当且仅当，vv 并且 e e第 14 页 共 148 页 连通子图（connected component）：如果一个图不是连通的，它将包含若干个连通子图。连通子图指，添加任何结点则不连通的极大子图。下图就不是一个连通

26、图，它有两个连通子图，其顶点集分别是a, b, c, d, e和f, g, h, i。cbdaefghi思考：思考：中国的省际公路网是否是一个连通图？(注意台湾和海南!) 环路（cycle）：起止点为同一结点且路径长度为正的简单路径。没有环路的图称为无环图（acyclic） 。 hamilton 回路：起止点为同一结点，且只经过图中其它结点一次的环路 euler 回路：起止点为同一结点，且只经过图中所有边一次的环路3. 树树树是一个连通的无环图。森林森林：不连通的无环图，其每个连通子图是一棵树。第 15 页 共 148 页a ab bc cf fd de e( (1 1) )树树a ab bc

27、 cf fd dg g( (2 2) )森森林林e eh hi ij j 树的性质 1：|e| = |v| 1。注意，这是图成为树的必要条件必要条件，而不是充分条件不是充分条件。why? 因为图不一定连通，不连通的图却因为图不一定连通，不连通的图却可以有环，仍能满足此条件！可以有环，仍能满足此条件！ 树的性质 2：任意两结点间均有唯一的简单路径。why? 根树（rooted trees）：性质 2 使得选择任一结点为根成为可能。所得树称为根树。一般从上至下依次画出根和各层结点。根树有广泛的应用，常简称简称为树，下面的树均指根树。所谓双亲、孩子、祖先、子孙、子树、叶子等概念，不再详述。i id

28、dc ch hb bg ga ae ef fa ab bd de ec cg gf fh hi i 结点的深度（depth）：从根到该结点的简单路径的长度 树的高度（height）：从根到叶子的最长的简单路径的长度。 有序树（ordered trees）：每个结点的所有孩子是有序的。假定树中以从左至右表示顺序。二叉树（binary trees）是最常用的有序树，从而有左孩子、右孩子、左子树、右子树的概念。一般的有序树可以用“左孩子、右兄弟”的方式表示成二叉树。第 16 页 共 148 页4. 集合与字典集合与字典集合（set）：不同元素组成的一个无序的整体。常用的集合操作：membership

29、、union 和 intersection。字典：一种数据结构，用于实现对给定集合进行搜索、添加和删除元素这三种操作。集合的表示形式：给定全集 u 的 bit vector 表示和列表表示。第 17 页 共 148 页第二章第二章算法效率分析基础算法效率分析基础算法分析的重点是算法效率的分析，因为它可以量化（不像简洁性和通用性） ，关注的是时间效率（时间效率（time efficiency）和空间效率空间效率（space efficiency） 。2.1 分析框架分析框架对于给定问题，一个算法的 时间效率：指它运行的有多快（running time） 空间效率：指它需要多大的额外空间（memo

30、ry space）随着计算机技术的革新，越来越大容量的存储器的出现，算法对空间的需要已不再是什么问题，但是时间效率却没有相应的提高，因此，我们关注的重点是时间效率关注的重点是时间效率，但分析框架完全适用于空间效率。1. 度量输入规模度量输入规模算法的效率和输入规模 n 有关，因为几乎所有算法对大的输入运行时间要长一些。例如，对较大的数组排序，两个较高维数的矩阵相乘，等等。关键是 n 如何确定?例，对一个列表的排序、搜索或者寻找其中最小元素，显然，n 即列表中元素的个数；矩阵相乘，n 可以是矩阵的维数，也可以是矩阵中元素的个数；而大整数相乘，则 n 取大整数的位数比取大整数本身更合适。第 18

31、页 共 148 页2. 度量运行时间的单位度量运行时间的单位 秒、毫秒等时间单位：依赖于特定机器的性能，我们需要的是一种不依赖于外部因素、只决定于算法本身的衡量标准 算法中各种操作执行的次数：精确，但过于困难且没有必要 算法中基本操作执行的次数：对算法总运行时间贡献最大的、最重要的操作例，对一个列表的排序，位于最内循环中的操作肯定执行次数最大，选择元素的比较操作为基本操作；矩阵相乘，需要对应元素一一相乘并求和，又因为大多数计算机中乘法比加法慢，所以选择乘法为基本操作；而大整数相乘，则宜取每一位的乘法为其基本操作。因为实际运行时间 t 和基本操作的执行次数 c 关于输入规模 n近似的成一定的比例

32、，即，t(n) k c(n)，要分析时间效率，就要建立输入规模 n 和基本操作执行次数 c 之间的函数关系 c(n)。例，假设 c(n)=，当输入规模翻番时，运行时nnnn2121) 1(212间如何变化？（当 n 足够大时）4242121)2(21)2(21)()2()()2(2222nnnnnnnnnkcnkcntnt注意：注意： 实际运行时间和基本操作执行次数所成的比例 k 对最后的结果没有影响 函数 c(n)中的常数因子对最后的结果没有影响21第 19 页 共 148 页 考虑较大输入规模时，低阶量对最后的结果没有影响为什么分析效率只考虑较大输入规模的情形？为什么分析效率只考虑较大输入

33、规模的情形？输入规模较小时，不同算法之间的效率差异不明显！输入规模较小时，不同算法之间的效率差异不明显！3. 函数的阶（分析效率时的关注重点）函数的阶（分析效率时的关注重点）nn2lognnn2logn2n32nn!103.3103.3 101021031033.6 1061026.61026.6 1021041061.3 10309.3 10157103101031.0 104106109104131041.3 1051081012105171051.7 10610101015106201062.0 10710121018书上 p7 有类似表。，可见底数不同的对数函数之间只相差一个nbnba

34、alogloglog常数因子，由前讨论，可以忽略，今后忽略底数忽略底数，写作 log n。指数函数和阶乘函数增长过快，只适合求解很小的输入规模只适合求解很小的输入规模，今后统称作指数函数指数函数。4. 最坏、最好和平均情况最坏、最好和平均情况有很多算法的性能不仅和输入规模有关，还和特定的输入有关。例，在以数组 a1 . n表示的线性表中顺序搜索某个值 k，找到则返回下标值，返回1 表示未找到。 sequentialsearch (a1.n, k)第 20 页 共 148 页/input：数组 a1.n和搜索值 k/output：若有 a 中元素等于 k，返回该元素下标，否则返回1i = 1wh

35、ile i n doif k = ai return i/基本操作为此处的比较else i = i + 1return 1 最坏情况最坏情况：所有同规模的输入中，算法运行时间最长的输入 最好情况最好情况：所有同规模的输入中，算法运行时间最快的输入 平均情况平均情况：随机输入的运行情况，需对输入做某些假定对上述线性搜索，cworst(n)= n，cbest(n)=1。假定，对任意输入，能搜索到的概率为 p，且在任一位置找到的可能性相同，则如果 p=1，则表)1 (2) 1()1 (21)(pnnppnnpnnpnpncavg示一定能找到，平均比较次数为；如果 p=0，则表示一定找不21n到，也需

36、比较 n 次。 最坏情况最坏情况：决定算法运行时间的上限，常用 最好情况最好情况：除极少情况，很难保证算法总处于最好，不常用 平均情况平均情况：需进行概率分析，运算复杂，但有时很有必要，尤其当平均情况远不像最差情况那么糟的时候。注意：平均情况不是最坏情况和最好情况的平均 分摊效率分摊效率：有些算法的第一次运行代价很高，但多次运行第 21 页 共 148 页的代价却比第一次的代价乘以运行次数的值要小的多2.2 渐进符号和基本效率类型渐进符号和基本效率类型本课程所讨论函数均为非负函数。本课程所讨论函数均为非负函数。1. o 记号记号：函数 t(n)o(g(n)如果存在某个正常数 c 和某个非负整数

37、 n0 使得对所有 nn0，t(n)c g(n)。例，100n+5100n+n=101n101n2 （对所有 n5） ，所以100n+5o(n2)，此处，取 c=101，n0=5；又，100n+5100n+5n=105n （对所有 n1） ，100n+5o(n)，此处，取 c=105，n0=1。试证明，no(n2)，o(n2)，0.00001no(n2)，) 1(21nn3n +n+1 o(n2)。42. 记号记号：函数 t(n)(g(n)如果存在某个正常数 c 和某个非负整数 n0 使得对所有 nn0，t(n)c g(n)。例， n (n2)，因为对所有 n0，n n2，此处 c=1，n0=

38、0。33试证明，n2(n)，(n2)，100n+5 (n2)。) 1(21nn3. 记号记号：函数 t(n)(g(n)如果存在正常数 c1 和 c2 和某个非负整数 n0 使得对所有 nn0，c1 g(n)t(n)c2 g(n)。例，（对所有 n0）22212121) 1(21nnnnn（对所有 n2）222412121212121) 1(21nnnnnnnn所以，取 c1=，c2=，n0=2，有(n2)。4121) 1(21nn4. 渐进符号的性质渐进符号的性质第 22 页 共 148 页 性质性质 1 1如果如果 t1(n)o(g1(n)，t2(n)o(g2(n)，则 t1(n) + t2

39、(n) o(maxg1(n),g2(n) 性质性质 2 2如果如果 t1(n)(g1(n)，t2(n)(g2(n)，则 t1(n) + t2(n) (maxg1(n),g2(n) 性质性质 3 3如果如果 t1(n)(g1(n)，t2(n)(g2(n)，则 t1(n) + t2(n) (maxg1(n),g2(n)性质性质 1 1 的证明：的证明：t1(n)o(g1(n)， c1 和 n1 对所有 nn1，t1(n)c1 g1(n)t2(n)o(g2(n)， c2 和 n2 对所有 nn2，t2(n)c2 g2(n)对所有 nmaxn1,n2，t1(n) + t2(n) c1 g1(n) +

40、c2 g2(n) c1 maxg1(n),g2(n) + c2 maxg1(n),g2(n) (c1+c2) maxg1(n),g2(n)取 c= c1+c2，n0=maxn1,n2，即，t1(n) + t2(n) o(maxg1(n),g2(n)。试证明另外两个性质。例，某算法判断数组中是否包含相同元素，其思想如下，首先将数组排序，然后比较相邻元素是否相同。假设所用排序算法属于 o(n2)，比较相邻元素显然属于 o(n)，则该算法属于 o(maxn2,n)= o(n2)。第 23 页 共 148 页5. 使用极限比较函数的阶使用极限比较函数的阶0 t(n)的阶小于的阶小于 g(n)c t(n

41、)与与 g(n)有相同的阶有相同的阶 t(n)的阶高于的阶高于 g(n)例，(n2)21)11 (lim21lim21) 1(21lim222nnnnnnnnnn) 1(21nn，比0limlog2211)(loglim)()(loglimloglim2222nnennennnnnnnnn2log的阶小。n6. 基本效率类型基本效率类型即使不考虑常数因子，仍然有无穷多种函数的阶类型。即使不考虑常数因子，仍然有无穷多种函数的阶类型。类型名称描述1常数某些算法的最好情况，实际中很少log n对数每次迭代输入规模以常数因子递减的算法n线性需扫描整个输入的算法n log n n-log-n 许多分治算

42、法属于此类，如归并排序和快速排序n2平方有两重循环的算法，如冒泡排序和选择排序n3立方有三重循环的算法，如矩阵乘法2n指数产生输入集所有子集的算法n！阶乘产生输入集元素全排列的算法)()(limngntn第 24 页 共 148 页2.3 非递归算法的数学分析非递归算法的数学分析例 1在 n 个元素的线性表（以数组 a1.n表示）中寻找最大元素。maxelement(a1.n)/input：数值型数组 a1.n/output：a 中最大元素的值maxval = a1for i = 2 to n doif aimaxval maxval = aireturn maxval 输入规模输入规模：数组

43、中元素的个数 n 基本操作基本操作：最频繁执行的操作在循环内，循环内有比较和赋值，但赋值不是每次都做，故比较为基本操作 是否依赖于输入是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况 比较次数比较次数：c(n) = = n 1 (n)ni 21非递归算法效率分析的一般模式非递归算法效率分析的一般模式： 确定描述输入规模的参数 识别算法的基本操作 检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解第 25 页 共 148 页 建立表示基本操作执行次数的公式 得出执行次数的通项公式，或者至少确定其阶例 2检查给定数组中的元素是否彼

44、此不同。uniqueelement (a1.n)/input：数组 a1.n)/output：如果所有元素均不相同，返回 true；否则，返回 falsefor i = 1 to n 1 dofor j = i + 1 to n doif ai = aj return falsereturn true 输入规模输入规模：数组中元素的个数 n 基本操作基本操作：循环内只有比较操作 是否依赖于输入是否依赖于输入：比较的次数不仅与输入规模有关，还和数组中是否有相同元素，以及相同元素在数组中的位置有关，此例我们考虑最差情况最差情况 比较次数比较次数：每次内循环的比较都执行，cworst(n)= = 1

45、111ninij = = =11)1(niin11) 1(nin11nii111) 1(nin2) 1)(2(nn2) 1( n=(n2)2) 1)(2(nn2) 1(nn 例 3给定两个 nn 的矩阵 a 和 b，求 c=ab。matrixmultiplication(a1.n, 1.n, b1.n, 1.n)/input：两个 nn 的矩阵 a 和 b第 26 页 共 148 页/output：矩阵 c=abfor i = 1 to n dofor j = 1 to n doci, j = 0for k = 1 to n doci, j = ci, j + ai, k * bk, jret

46、urn c 输入规模输入规模：矩阵的阶 n 基本操作基本操作：最内循环有加法和乘法两种操作，两种操作执行次数相同，所以取哪个为基本操作都可以 是否依赖于输入是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况 乘法次数乘法次数：m(n) = =n3ninjnk1111ninjn11nin122.4 递归算法的数学分析递归算法的数学分析例 1非负整数 n 的阶乘 f(n) = n! = 1(n1)n，其递归定义如下：1n=0f(n) = n f(n1) n0由此定义，可得其递归算法如下f(n)/input：非负整数 n第 27 页 共 148 页/output：n 的阶乘if n=0

47、 return 1else return f(n1)*n 输入规模输入规模：非负整数 n 基本操作基本操作：有比较和乘法，但 n=0 时算法结束，所以基本操作是 else 分支中的乘法 是否依赖于输入是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况 乘法次数乘法次数：m(n) =+ 对 n0) 1(1 -nfnm）中的乘法（计算1n*1 -nf中的乘法）（这是一个递推公式，要求 m(n)的通项公式，可逆向回推，得m(n) = m(n1)+1= m(n2)+1+1=m(n2)+2=m(n3)+3 = m(ni)+i = m(nn)+n =m(0)+n，又 n=0 时，算法直接返回，不

48、进行乘法，即，m(0)=0,m(n) = n递归算法效率分析的一般模式递归算法效率分析的一般模式： 确定描述输入规模的参数 识别算法的基本操作 检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解 建立表示基本操作执行次数的递推公式 解递推式，得出执行次数的通项公式，或者至少确定其阶例 2tower of hanoi 问题的递归算法如下第 28 页 共 148 页hanoi(n, a, b, c)/input：要搬运的盘子总数 n/output：塔上盘子的搬运过程if n=1 move(n, a, c)elsehanoi(n1, a, c, b

49、)move(n, a, c)hanoi(n1, b, a, c) 输入规模输入规模：盘子总数 n 基本操作基本操作：有比较和搬运操作 move，此处去 move，why？ 是否依赖于输入是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况 搬运次数搬运次数：m(n) = m(n1)+1+ m(n1) 对 n1又，只有一个盘子（即 n=1）时，需 move 一次，即，m(1)=1。逆向回推，得m(n) = 2m(n1)+1 = 22m(n2)+1+1 = 4m(n2)+2+1 = 42m(n3)+1+2+1 = 8m(n3)+4+2+1 = =12422)(221iiiinm12)(2i

50、iinm=12)1(211nnnnm12) 1 (211nnm12211nn12 n这是一个指数算法指数算法，并且，由于此问题本身的复杂性，这已经是解决这个问题的最有效方法。另外注意，经常根据递归定义得到第 29 页 共 148 页的算法看上去非常简洁，但是要小心看上去的简洁掩盖了实际上的看上去的简洁掩盖了实际上的低效低效!2.5 例：例：fibonacci 数列数列1fibonacci 数列的递推公式为0n=0f(n)=1n=1f(n1)+f(n2) n1解法一解法一求数列通项公式求数列通项公式前面求解递归算法效率时，求得通项公式即可获知算法效率，受此启发，对于递推式给出的数列，如能求得数列

51、的通项公式，则对任意的输入 n，求解 f(n)的时间仅依赖于通项公式的复杂程度。但此处逆向回推逆向回推法会让人迅速放弃！二阶常系数线性递推关系二阶常系数线性递推关系 a x(n)+b x(n1)+c x(n2) = f(n)的求解的求解 二阶：待求递推关系最高项二阶：待求递推关系最高项 x(n)与最低项与最低项 x(n2)相差两阶相差两阶 线性：左侧是递推关系未知项的线性组合线性：左侧是递推关系未知项的线性组合 常系数：常系数：a，b，c 均为常数均为常数 齐次：如果齐次：如果 f(n)=0；否则，称为非齐次；否则，称为非齐次考虑最简单情形最简单情形 a x(n) + b x(n1) = 0，

52、即，x(n) = x(n1)，ab这是一个等比数列，其通解为 x(n) = rn，公比 r = ， 的值由初ab始条件确定。1此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。第 30 页 共 148 页对于 a x(n)+b x(n1)+c x(n2) = 0 的情形，类比可猜想其通解也应为等比数列，设 x(n) = rn，则 x(n1) = rn1，x(n2) = rn2，得 a rn + b rn1 + c rn2 = 0，考虑一般情况，0，r0，得 特征方程特征方程a r2 + b r + c = 0

53、。对此方程解的不同情况，递推关系的通解如下： 方程有二不等实根方程有二不等实根 r1，r2：递推关系的通解为 x(n)=+ ，nr1nr2其中 和 的值由初始条件确定 方程有二相等实根方程有二相等实根 r：递推关系的通解为 x(n)=+ n，其中nrnr 和 的值由初始条件确定 方程有二共轭虚根方程有二共轭虚根 r1, 2=uiv：由于算法分析所考虑的数列均为非负数，数列递推关系的通解 x(n)=( cos n+ sin n)，其中n=，=arc tan ， 和 的值由初始条件确定22vu uv对于 a x(n)+b x(n1)+c x(n2) = f(n)的情形，它的通解是相应齐次递推关系的

54、通解与该非齐次递推关系的一个特解之和。不像求通解，求特解的无一般方法，常用的方法是尝试与 f(n)同阶的函数。上述求解二阶常系数线性递推关系的方法可推广到上述求解二阶常系数线性递推关系的方法可推广到 n 阶常系数阶常系数线性递推关系。线性递推关系。例，解递推关系 x(n)6x(n1)+9x(n2) = 4。 特征方程为 r2 6 r + 9 = 0，有二相等实根 r=3，相应齐次递推关系的通解为 x(n)=+ nn3n3 f(n)=4，同阶的函数同样为常数，设为 c，代入得 c6c+9c=4，解得 c=1 递推关系 x(n)6x(n1)+9x(n2) = 4 的通解为 x(n)第 31 页 共

55、 148 页=+n+1n3n3求解求解 fibonacci 数列的通项公式数列的通项公式 特征方程为 r2 r1 = 0，有二不等实根，2511r，通解为 f(n)=+ 2512rn)251(n)251( 将 f(0)=0，f(1)=1 代入得 += 0+ = 1)251()251( 解此二元一次方程组得 =，=5151f(n) = 51n)251(51n)251(解法二解法二用递归算法求数列第用递归算法求数列第 n 项项f(n)/input：非负整数 n/output：fibonacci 数列第 n 项if n1 return nelse return f(n1)+ f(n2) 输入规模输入

56、规模：非负整数 n 基本操作基本操作：有比较和加法，但 n1 时算法结束，所以基本操作是 else 分支中的加法 是否依赖于输入是否依赖于输入：无须区分最好、最差和平均情况 加法次数加法次数：a(n) = a(n1)+a(n2)+1 对 n0，a(0) = a(1) 第 32 页 共 148 页=0 这是一个二阶常系数线性非齐次递推关系，其对应齐次递推关系的特征方程为 r2r1=0，与 fibonacci 数列通解相同 f(n)=1，同阶的函数同样为常数，设为 c，代入得 ccc=1，解得 c= 1，通解为 a(n)=+ 1n)251(n)251( 将 a(0)=0，a(1)=0 代入得 +1

57、 = 0+ 1 = 0)251()251( 解此二元一次方程组得 =，=，10551055a(n) = +11055n)251(1055n)251( 关于 a(n) = a(n1)+a(n2)+1 的另一解法：a(n)+1= a(n1)+1 + a(n2)+1，显然这就是 fibanacci 数列的递推关系，而 a(0)+1=1=f(1)，a(1)+1=1=f(2)，a(n)=f(n+1) 1，即 a(n) = 1()，why？511)251(n511)251(nn)251(显然，这是一个指数算法指数算法，递归算法的简洁掩盖了它实际的低实际的低效效!解法三解法三用非递归算法求数列第用非递归算法

58、求数列第 n 项项fib(n)/input：非负整数 n/output：fibonacci 数列第 n 项第 33 页 共 148 页f0 = 0; f1 = 1for i = 2 to n dofi = fi1 + fi2return fn 输入规模输入规模：非负整数 n 基本操作基本操作：循环内只有加法，故加法为基本操作 是否依赖于输入是否依赖于输入：无须区分最好、最差和平均情况 加法次数加法次数：a(n) = n 1 (n)ni 21三种算法的比较：三种算法的比较： 第二种递归算法不可取第二种递归算法不可取 如果第一种算法指数运算采用依次相乘的方法，其效率也属于 (n) 存在算法存在算法

59、使得 n 次指数运算可以在 (log n)时间内完成第 34 页 共 148 页第三章第三章蛮力法（蛮力法（brute force）和算术问题）和算术问题例，计算，由就是蛮力法的体现。na次nnaaa*为什么应用蛮力法进行算法设计？为什么应用蛮力法进行算法设计？ 不像其他算法设计方法只适合于某类问题，很难指出蛮力法不适合于什么问题 对于小规模问题，采用蛮力法设计的算法速度可接受，花费大量时间设计高效算法不值 蛮力法可作为评价更高效算法的标准3.1 选择排序和冒泡排序选择排序和冒泡排序1. 选择排序扫描整个列表选择最小的元素放在第一个位置，扫描余下的元素选择最小的放在第二个位置，依次继续，直至最

60、后一个元素，这恐怕是我们进行排序所想到的第一个算法。例，对 89，45，68，90，29，34，17 的选择法排序。考虑一般情形，第 i 趟扫描是寻找第 i 小的元素，所以前面 i1个元素已经排好序，要依次扫描从第 i 个元素开始的每个元素，这是内循环。经过 n1 趟扫描后，只余最后一个元素，无需比较，所以，共需 n1 趟扫描（外循环）完成排序。伪代码如下selectionsort(a1.n)/input：一个可排序元素的数组 a1.n/output：以升序排列的数组 a1.n第 35 页 共 148 页for i = 1 to n1 domin = ifor j = i+1 to n doi