算法分析与设计.doc

第 1 页 共 148 页 目录目录 第一章第一章绪论绪论3 1.1 算法的概念.3 1.2 算法问题求解基础.6 1.3 重要的问题类型.9 1.4 基本数据结构.11 第二章第二章算法效率分析基础算法效率分析基础16 2.1 分析框架.16 2.2 渐进符号和基本效率类型.19 2.3 非递归算法的数学分析.22 2.4 递归算法的数学分析.25 2.5 例：fibonacci数列27 第三章第三章蛮力法（蛮力法（brute force）和算术问题）和算术问题.33 3.1 选择排序和冒泡排序.33 3.2 蛮力字符串匹配.35 3.3 穷举搜索（exhaustive search）36 3.4 基本算术40 3.5 模算术42 3.6 素性检测42 3.7 密码学42 第四章第四章分治法（分治法（devide-and-conqure）43 4.1 主定理（master theorem）43 4.2 归并排序.44 4.3 快速排序.46 4.4 大整数乘法.49 4.5 strassen矩阵乘法50 4.6 快速傅里叶变换 fft52 第五章第五章减治法（减治法（decrese-and-conqure）.58 5.1 插入排序.58 5.2 深度优先搜索和广度优先搜索.59 5.3 生成组合对象的算法.63 5.4 二叉搜索（折半查找）.67 5.5 乘法和乘方问题.69 5.6 euclid算法分析.71 第六章第六章时空权衡（时空权衡（time and space tradeoffs）与动态规划（）与动态规划（dynamic programming）.72 6.1 计数排序.72 6.2 高效串匹配算法.73 6.3 再谈 fibonacci数列.78 第 2 页 共 148 页 6.4 有向无环图中最短路径.79 6.5 计算传递闭包的 warshall算法和多源最短路径问题的 floyd算法 .81 6.6 矩阵链相乘问题.84 6.7 最优二叉搜索树.86 6.8 最长递增子序列.89 6.9 编辑距离.89 6.10 背包问题.92 6.11 旅行商 tsp 问题95 第七章第七章贪心法（贪心法（greedy techniques）.99 7.1 连续背包问题.99 7.2 最小生成树问题（mst，minimum spanning tree）.102 7.3 单源最短路径问题的 dijkstra算法.109 7.4 huffman编码.112 7.5 集合覆盖118 第八章第八章线性规划（线性规划（linear programming）.119 8.1 线性规划简介.119 8.2 求解线性规划问题的单纯形算法.122 8.3 网络流问题.129 8.4 二部图的匹配问题.129 8.5 对偶.129 8.6 零和游戏.130 第九章第九章算法能力的极限算法能力的极限131 9.1 求算法下界的方法.131 9.2 问题归约.132 9.3 p，np 和 np 完全问题134 9.4 回溯法（backtracking）.139 9.5 分支限界法（branch-and-bound）.141 9.6 近似算法（approximation algorithms）144 第 3 页 共 148 页 第一章第一章绪论绪论 1.1 算法的概念算法的概念 算法：解决一个问题的算法：解决一个问题的无歧义无歧义的指令序列，对的指令序列，对合法的输入合法的输入在在有有 限限的时间内可得到需要的的时间内可得到需要的输出输出。 算法的一些特点：算法的一些特点： 无歧义性（确定性）：算法的每个步骤必须确定无疑无歧义性（确定性）：算法的每个步骤必须确定无疑 有穷性：算法的执行必须有限步终止有穷性：算法的执行必须有限步终止 输入的范围：算法只对输入的范围：算法只对满足条件的输入有响应满足条件的输入有响应 正确性：算法应能解决要求的问题正确性：算法应能解决要求的问题 同一算法的不同表示形式：自然语言、伪代码、高级语言同一算法的不同表示形式：自然语言、伪代码、高级语言 同一问题存在的多种算法：同一问题存在的多种算法：设计思想不同，时空性能各异设计思想不同，时空性能各异 例，求两个正整数 m 和 n 的最大公因子的算法 算法一最容易想到的算法挨个检查 step 1t = min m, n step 2如果 m 除以 t 的余数为 0，转 step 3；否则，转 step 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 的分解中质因子 p 出现了 x 次，n 的分解中 p 出现 了 y 次，作为公共部分，p 应出现 minx, y次） ； step 4计算公共部分的连乘积，并将结果返回。 分析：分析：此算法中，如何分解质因子没说明，如何寻找公共部分 不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法严格讲起来不能称为算法， 至少有待进一步具体说明！ 考虑如何具体说明：考虑如何具体说明： 分解质因子需要知道有哪些质数分解质因子需要知道有哪些质数 寻找公共部分涉及到质因子连乘积的表示形式寻找公共部分涉及到质因子连乘积的表示形式 算法三euclid 算法（记录于公元前 3 世纪 euclid 所著的 elements） euclid (m, n) /input：两个正整数 m 和 n /output：m 和 n 的最大公因子 while n0 do 第 5 页 共 148 页 r = m mod n m = n n = r return m 分析：分析： 上述步骤每一步均确定没有歧义，是一个循环结构程序 循环执行次数未知，那么它有限步终止吗？（每次（每次 n 都减小）都减小） 该算法由伪代码描述：伪代码是自然语言和编程语言的混合伪代码描述：伪代码是自然语言和编程语言的混合 该算法正确吗？如何证明？该算法正确吗？如何证明？ 证明：证明：设函数 gcd(m, n)就是采用 euclid 算法计算最大公因子的 函数。则算法的正确性基于两个事实： 若 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 与 n 的最大公因子得 c=1，即 b 与 a kb 互质。 第 6 页 共 148 页 比较上述三个算法，很明显，euclid 算法形式简单，循环次数算法形式简单，循环次数 少少（后面会进行详细分析）（后面会进行详细分析） ，所以我们说 euclid 算法更高效。算法更高效。 1.2 算法问题求解基础算法问题求解基础 算法是求解的具体指令，不是解答。算法是求解的具体指令，不是解答。 设计和分析算法的典型步骤：设计和分析算法的典型步骤： 1.理解问题理解问题 1) 仔细阅读问题描述 2) 手工测试几个例子 3) 思考特殊情形 4) 分析是否已有该类问题的算法 2.确定计算设备的能力确定计算设备的能力 现行的绝多数算法都是基于冯诺依曼机器模型的，即，随机 存储模型，它假定指令依次执行，每次执行一个操作，在这样机器 上执行的算法称为 sequential 算法算法。适合于现在新兴的可同时执行 多条操作的计算机的算法，称为并行算法并行算法。 除非对某些本质上复杂、需处理大量数据或者对时间要求很高除非对某些本质上复杂、需处理大量数据或者对时间要求很高 的问题，的问题，无需担心现在计算机的能力！无需担心现在计算机的能力！ 3.选择精确算法还是近似算法选择精确算法还是近似算法 1) 存在某些问题不能精确解决，例如求平方根 2) 可精确解决的算法难以接受的慢，例如，tsp 问题 3) 近似算法可以是某些更为复杂的精确算法的组成部分 第 7 页 共 148 页 4.确定合适的数据结构确定合适的数据结构 存在某些算法设计方法固有依赖于描述问题的数据结构。 5.算法设计方法算法设计方法 本课程所要解决的主要问题主要问题。算法设计方法（或策略）是指： 从算法上解决问题的通用方法，可适用于不同领域的各种各样的问从算法上解决问题的通用方法，可适用于不同领域的各种各样的问 题题。 学习这些方法的原因： 1) 有助于为新问题设计算法，授人以鱼不如授人以渔授人以鱼不如授人以渔 2) 每门学科都对其研究主题进行分类，算法是计算机科学的 基础，有助于根据设计思想对算法进行分类 6.描述算法的方法描述算法的方法 1) 自然语言描述，如前例中算法一、二 2) 伪代码描述，如前例中算法三 euclid 算法，无统一格式 3) 流程图，只适合于描述很简单的算法 4) 某种计算机语言写成的程序 7.证明算法的正确性证明算法的正确性 一旦算法描述清楚，就需要证明其正确性，即，它对每一个合 法的输入都可以在有限的时间内得出需要的结果。 证明算法正确的一个常用方法是：数学归纳法。数学归纳法。 注意：测试几组输入数据的方法虽然简单，但却不足以说明算注意：测试几组输入数据的方法虽然简单，但却不足以说明算 法正确！法正确！不过却可以说明一个算法不正确！不过却可以说明一个算法不正确！ 8.算法分析算法分析 第 8 页 共 148 页 算法应具有的几个品质：算法应具有的几个品质：本课程所要解决的主要问题主要问题 1) 正确性正确性 2) 效率效率：时间效率和空间效率。第二章详述 3) 简洁性简洁性：无法用数学定义精确描述，最好给人以美感 例，前述的求 gcd 的算法哪个更简单？简单的算法易于理解， 易于编程，通常包含较少的 bug，一般也更有效率 4) 通用性通用性：同样的效率，解决的问题可适用范围当然越广越 好，但是有时通用算法难设计且效率差，或者根本无通用算法 例，判定两个正整数是否互质的算法就没有求 gcd 的通用； 二次方程求根公式存在的，但没有任意次方程的求根方法 9.算法编码实现算法编码实现 1) 注意程序严格准确的实现算法 2) 算法到程序的过渡：算法中假设输入都是合法的，程序中 需验证 3) 程序的正确性验证的实际方式：测试（testing） 。 4) 学习编程技巧，以提高程序效率 最优算法（最优算法（optimality）：不是算法效率的问题，而是算法解决 问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价 最少。某些问题的最优算法是存在的，比如，通过比较进行排序的 最优算法需要进行 n log n 次比较；但某些看上去简单的问题，还未 找到最优算法，例如，矩阵乘法。 不可判定性不可判定性(undecidability)：不是说，每个问题均有算法解决 第 9 页 共 148 页 （注意，这不同于一个问题没有解这不同于一个问题没有解，例如，判别式为负的二次方程 无实数解） 。所幸的是，实际计算中的绝大多数问题还是有解决算法 的。 1.3 重要的问题类型重要的问题类型 后面的章节将以以下问题展开，讨论不同算法的设计技术与分 析方法。 1. 排序排序 我们经常遇到排序问题，比如学校学生按学号排序，学号通常 被称为 key。那么为什么要进行排序为什么要进行排序？排序使得很多关于列表的问排序使得很多关于列表的问 题简单题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法排序还常作为某些领域重要算法 的辅助步骤的辅助步骤，比如，在几何算法中。 当前，已有很多排序算法，在这些算法当中，有些较好的可将 任意 n 个元素通过大约 n log2 n 比较完成排序，但是没有哪一个通过没有哪一个通过 关键字比较的排序算法能比关键字比较的排序算法能比 n log2 n 作的更好作的更好！ 排序算法的两个性质：排序是否稳定稳定（保持输入相等元素的相 对次序不变）和是否需要大量辅助空间（in place 排序） 。 2. 搜索（查找）搜索（查找） 同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜 索（要求元素已排序） ，等等。 由于搜索经常与添加和删除操作联系在一起，所以，需仔细设需仔细设 计数据结构计数据结构。 第 10 页 共 148 页 3. 字符串处理字符串处理 由于所有程序在计算机看来都是字符串，所以此类算法同计算 机语言和编译紧密相关。 此类算法中最特殊的一个字符串匹配字符串匹配在给定文本中搜 索给定单词，在实际中非常有用。 4. 图论问题图论问题 算法中最古老而又吸引人的领域就是图算法。图可以看作是由 若干结点和若干个连接其中某些结点的边所构成，其准确定义下一 小节给出。图可以为日常很多应用建模，比如，交通和通信网，项 目调度，博弈。 最基本的图算法包括：图遍历算法图遍历算法（如何遍历网络中所有结点） ， 最小生成树算法最小生成树算法（如何铺设最经济的通信网络） ，最短路径算法最短路径算法（如 何确定两城市间的最佳路线） ，有向图的拓扑排序有向图的拓扑排序（如何确定专业课 程的学习顺序） ，等等。 有些图论问题非常复杂，以至于最快的计算机也只能解决较小 规模的这类问题，比如，旅行商问题旅行商问题（遍历 n 个城市每个一次的最 短线路）和图着色问题图着色问题（给图的结点着色以使相邻结点颜色不同的 最少颜色数） ，例如，多叉路口交通灯的设计就是一个图着色问题。 5. 组合问题组合问题 更抽象的讲，旅行商问题和图着色问题都是组合问题的例子。 组合问题寻求满足某些约束条件或者某些期望性质的组合对象（排 列，组合，多重集） 。 第 11 页 共 148 页 组合问题被认为是计算机科学中最困难的问题，因为： 随着问题规模扩大，组合对象的数目急剧扩大随着问题规模扩大，组合对象的数目急剧扩大 没有已知的算法可在可接受的时间内解决大多数此类问题没有已知的算法可在可接受的时间内解决大多数此类问题 大多数计算机科学家相信不存在可接受时间内解决此类问题大多数计算机科学家相信不存在可接受时间内解决此类问题 的算法，但不能证实和证伪的算法，但不能证实和证伪 6. 几何问题几何问题 几何问题处理点、线、多边形。 应用领域包括计算机图形学， 机器人学，x 线断层摄影学。典型算法，比如寻找平面内 n 个点中 的最近点对算法。 7. 数值问题数值问题 涉及到数学问题的求解，比如，解方程或方程组，计算定积分， 等等。大多数这类问题只能近似解决，主要一个原因是他们的操作 对象是实数，计算机只能够近似表述。 1.4 基本数据结构基本数据结构 1. 线性数据结构线性数据结构 两种基本的线性数据结构是数组和链表数组和链表。 数组的特点： 每个元素类型相同，占有同样大小的存储空间 整个数组连续存储，任意元素可通过下标随机访问随机访问 单（双、循环）链表的特点： 非连续存储，访问某个元素的时间与其在链表中的位置有关 第 12 页 共 148 页 无需预留存储空间，插入和删除操作方便 数组和链表均可用于实现抽象数据结构线性表，其基本操 作是：搜索、插入、删除。 两种特殊的线性表：栈（lifo）和队列（fifo） 。 2. 图图 图 g =(v, e)，其中 v 是顶点（结点）的有限集，e 是顶点对 （边）所构成的集合。如果边没有方向性，称 g 是无向图；否则， 称 g 为有向图。 a ed cb df ac fe b 例：如上左图为无向图，其中 v=a, b, c, d, e, f，e=(a, c), (a, d), (b, c), (b, 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 页 共 148 页 f e d c b a 010010 101100 010001 010011 100100 001100 ac b f e d c f e b c a a c d e d e b f 对无向图而言，其邻接矩阵总是对称对称的。why？ 显然，稀疏图用邻接表更节省存储空间。why？但具体某问题 采用何种表示，更加依赖于解决该问题的算法的性质。 加权图（weighted graph）：图中边赋有值，称为权或 cost。 比如实际应用中，交通图中两城市间的公路距离。邻接矩阵 和邻接表均可用于存储加权图。矩阵中的值可表示距离（无 边的是为） ，邻接表的每一结点可添加一项表示距离 a dc b 5 2 3 1 87 ab,2 b d c a,2 a,5 a,7 c,5 c,8 b,3 b,8 d,7 d,3 d,1 c,1 路径（path）：从顶点 u 到顶点 v 的路径，是指始于 u 终于 v 有边连接的顶点序列（有向图中，要求边的方向均为从 u 至 v 方向） 。若除起止点外路径中无顶点重复，称简单路径简单路径。 路径长度指路径中的边数（即，顶点数减 1） 。 连通图（connected）：图中的每对顶点均有路径连接 子图（subgraph）：图 g=(v, e)称为图 g 的子图，当且仅 当，vv 并且 e e 第 14 页 共 148 页 连通子图（connected component）：如果一个图不是连通的， 它将包含若干个连通子图。连通子图指，添加任何结点则不 连通的极大子图。下图就不是一个连通图，它有两个连通子 图，其顶点集分别是a, b, c, d, e和f, g, h, i。 cbd a e f gh i 思考：思考：中国的省际公路网是否是一个连通图？(注意台湾和海南!) 环路（cycle）：起止点为同一结点且路径长度为正的简单路 径。没有环路的图称为无环图（acyclic） 。 hamilton 回路：起止点为同一结点，且只经过图中其它结点 一次的环路 euler 回路：起止点为同一结点，且只经过图中所有边一次 的环路 3. 树树 树是一个连通的无环图。 森林森林：不连通的无环图，其每个连通子图是一棵树。 第 15 页 共 148 页 a ab b c c f f d d e e ( (1 1) )树树 a ab b c c f f d d g g ( (2 2) )森森林林 e e h h i i j j 树的性质 1：|e| = |v| 1。注意，这是图成为树的必要条件必要条件， 而不是充分条件不是充分条件。why? 因为图不一定连通，不连通的图却因为图不一定连通，不连通的图却 可以有环，仍能满足此条件！可以有环，仍能满足此条件！ 树的性质 2：任意两结点间均有唯一的简单路径。why? 根树（rooted trees）：性质 2 使得选择任一结点为根成为可 能。所得树称为根树。一般从上至下依次画出根和各层结点。 根树有广泛的应用，常简称简称为树，下面的树均指根树。所谓 双亲、孩子、祖先、子孙、子树、叶子等概念，不再详述。 i id d c c h h b b g g a ae e f f a a b bd de e c cg gf f h hi i 结点的深度（depth）：从根到该结点的简单路径的长度 树的高度（height）：从根到叶子的最长的简单路径的长度。 有序树（ordered trees）：每个结点的所有孩子是有序的。假 定树中以从左至右表示顺序。二叉树（binary trees）是最常 用的有序树，从而有左孩子、右孩子、左子树、右子树的概 念。一般的有序树可以用“左孩子、右兄弟”的方式表示成 二叉树。 第 16 页 共 148 页 4. 集合与字典集合与字典 集合（set）：不同元素组成的一个无序的整体。常用的集合操 作：membership、union 和 intersection。字典：一种数据结构，用于 实现对给定集合进行搜索、添加和删除元素这三种操作。 集合的表示形式：给定全集 u 的 bit vector 表示和列表表示。 第 17 页 共 148 页 第二章第二章算法效率分析基础算法效率分析基础 算法分析的重点是算法效率的分析，因为它可以量化（不像简 洁性和通用性） ，关注的是时间效率（时间效率（time efficiency）和空间效率空间效率 （space efficiency） 。 2.1 分析框架分析框架 对于给定问题，一个算法的 时间效率：指它运行的有多快（running time） 空间效率：指它需要多大的额外空间（memory space） 随着计算机技术的革新，越来越大容量的存储器的出现，算法 对空间的需要已不再是什么问题，但是时间效率却没有相应的提高， 因此，我们关注的重点是时间效率关注的重点是时间效率，但分析框架完全适用于空间效 率。 1. 度量输入规模度量输入规模 算法的效率和输入规模 n 有关，因为几乎所有算法对大的输入 运行时间要长一些。 例如，对较大的数组排序，两个较高维数的矩阵相乘，等等。 关键是 n 如何确定? 例，对一个列表的排序、搜索或者寻找其中最小元素，显然， n 即列表中元素的个数；矩阵相乘，n 可以是矩阵的维数，也可以是 矩阵中元素的个数；而大整数相乘，则 n 取大整数的位数比取大整 数本身更合适。 第 18 页 共 148 页 2. 度量运行时间的单位度量运行时间的单位 秒、毫秒等时间单位：依赖于特定机器的性能，我们需要的 是一种不依赖于外部因素、只决定于算法本身的衡量标准 算法中各种操作执行的次数：精确，但过于困难且没有必要 算法中基本操作执行的次数：对算法总运行时间贡献最大的、 最重要的操作 例，对一个列表的排序，位于最内循环中的操作肯定执行次数 最大，选择元素的比较操作为基本操作；矩阵相乘，需要对应元素 一一相乘并求和，又因为大多数计算机中乘法比加法慢，所以选择 乘法为基本操作；而大整数相乘，则宜取每一位的乘法为其基本操 作。 因为实际运行时间 t 和基本操作的执行次数 c 关于输入规模 n 近似的成一定的比例，即，t(n) k c(n)，要分析时间效率，就要 建立输入规模 n 和基本操作执行次数 c 之间的函数关系 c(n)。 例，假设 c(n)=，当输入规模翻番时，运行时nnnn 2 1 2 1 ) 1( 2 1 2 间如何变化？ （当 n 足够大时）4 24 2 1 2 1 )2( 2 1 )2( 2 1 )( )2( )( )2( 2 2 2 2 nn nn nn nn nkc nkc nt nt 注意：注意： 实际运行时间和基本操作执行次数所成的比例 k 对最后的结 果没有影响 函数 c(n)中的常数因子对最后的结果没有影响 2 1 第 19 页 共 148 页 考虑较大输入规模时，低阶量对最后的结果没有影响 为什么分析效率只考虑较大输入规模的情形？为什么分析效率只考虑较大输入规模的情形？ 输入规模较小时，不同算法之间的效率差异不明显！输入规模较小时，不同算法之间的效率差异不明显！ 3. 函数的阶（分析效率时的关注重点）函数的阶（分析效率时的关注重点） n n 2 log n nn 2 log n 2 n 3 2 n n! 103.3103.3 1010 2 10 3 10 3 3.6 10 6 10 2 6.610 2 6.6 10 2 10 4 10 6 1.3 10 30 9.3 10 157 10 3 1010 3 1.0 10 4 10 6 10 9 10 4 1310 4 1.3 10 5 10 8 1012 10 5 1710 5 1.7 10 6 10101015 10 6 2010 6 2.0 10 7 10121018 书上 p7 有类似表。 ，可见底数不同的对数函数之间只相差一个nbn baa logloglog 常数因子，由前讨论，可以忽略，今后忽略底数忽略底数，写作 log n。 指数函数和阶乘函数增长过快，只适合求解很小的输入规模只适合求解很小的输入规模， 今后统称作指数函数指数函数。 4. 最坏、最好和平均情况最坏、最好和平均情况 有很多算法的性能不仅和输入规模有关，还和特定的输入有关。 例，在以数组 a1 n表示的线性表中顺序搜索某个值 k，找到 则返回下标值，返回1 表示未找到。 sequentialsearch (a1n, k) 第 20 页 共 148 页 /input：数组 a1n和搜索值 k /output：若有 a 中元素等于 k，返回该元素下标，否则返回1 i = 1 while i n do if k = ai return i/基本操作为此处的比较 else i = i + 1 return 1 最坏情况最坏情况：所有同规模的输入中，算法运行时间最长的输入 最好情况最好情况：所有同规模的输入中，算法运行时间最快的输入 平均情况平均情况：随机输入的运行情况，需对输入做某些假定 对上述线性搜索，cworst(n)= n，cbest(n)=1。 假定，对任意输入，能搜索到的概率为 p，且在任一位置找到 的可能性相同，则 如果 p=1，则表)1 ( 2 ) 1( )1 (21)(pn np pn n p n n p n p ncavg 示一定能找到，平均比较次数为；如果 p=0，则表示一定找不 2 1n 到，也需比较 n 次。 最坏情况最坏情况：决定算法运行时间的上限，常用 最好情况最好情况：除极少情况，很难保证算法总处于最好，不常用 平均情况平均情况：需进行概率分析，运算复杂，但有时很有必要， 尤其当平均情况远不像最差情况那么糟的时候。注意：平均 情况不是最坏情况和最好情况的平均 分摊效率分摊效率：有些算法的第一次运行代价很高，但多次运行 第 21 页 共 148 页 的代价却比第一次的代价乘以运行次数的值要小的多 2.2 渐进符号和基本效率类型渐进符号和基本效率类型 本课程所讨论函数均为非负函数。本课程所讨论函数均为非负函数。 1. o 记号记号：函数 t(n)o(g(n)如果存在某个正常数 c 和某个非负 整数 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( 2 1 nn 3 n +n+1 o(n2)。 4 2. 记号记号：函数 t(n)(g(n)如果存在某个正常数 c 和某个非 负整数 n0 使得对所有 nn0，t(n)c g(n)。 例， n (n2)，因为对所有 n0，n n2，此处 c=1，n0=0。 33 试证明，n2(n)，(n2)，100n+5 (n2)。) 1( 2 1 nn 3. 记号记号：函数 t(n)(g(n)如果存在正常数 c1 和 c2 和某个 非负整数 n0 使得对所有 nn0，c1 g(n)t(n)c2 g(n)。 例，（对所有 n0） 22 2 1 2 1 2 1 ) 1( 2 1 nnnnn （对所有 n2） 222 4 1 2 1 2 1 2 1 2 1 2 1 ) 1( 2 1 nnnnnnnn 所以，取 c1=，c2=，n0=2，有(n2)。 4 1 2 1 ) 1( 2 1 nn 4. 渐进符号的性质渐进符号的性质 第 22 页 共 148 页 性质性质 1 1如果如果 t1(n)o(g1(n)，t2(n)o(g2(n)，则 t1(n) + t2(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) + 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)与与 g(n)有相同的阶有相同的阶 t(n)的阶高于的阶高于 g(n) 例，(n2) 2 1 ) 1 1 (lim 2 1 lim 2 1 ) 1( 2 1 lim 2 2 2 nn nn n nn nnn ) 1( 2 1 nn ，比0limlog2 2 1 1 )(log lim )( )(log lim log lim 2 2 22 n n e n n e n n n n nnnn n 2 log 的阶小。n 6. 基本效率类型基本效率类型 即使不考虑常数因子，仍然有无穷多种函数的阶类型。即使不考虑常数因子，仍然有无穷多种函数的阶类型。 类型名称描述 1常数某些算法的最好情况，实际中很少 log n对数每次迭代输入规模以常数因子递减的算法 n线性需扫描整个输入的算法 n log n n-log-n 许多分治算法属于此类，如归并排序和快速排序 n 2 平方有两重循环的算法，如冒泡排序和选择排序 n 3 立方有三重循环的算法，如矩阵乘法 2 n 指数产生输入集所有子集的算法 n！阶乘产生输入集元素全排列的算法 )( )( lim ng nt n 第 24 页 共 148 页 2.3 非递归算法的数学分析非递归算法的数学分析 例 1在 n 个元素的线性表（以数组 a1n表示）中寻找最大元素。 maxelement(a1n) /input：数值型数组 a1n /output：a 中最大元素的值 maxval = a1 for i = 2 to n do if aimaxval maxval = ai return maxval 输入规模输入规模：数组中元素的个数 n 基本操作基本操作：最频繁执行的操作在循环内，循环内有比较和赋 值，但赋值不是每次都做，故比较为基本操作 是否依赖于输入是否依赖于输入：对所有输入都一样，故无须区分最好、最 差和平均情况 比较次数比较次数：c(n) = = n 1 (n) n i 2 1 非递归算法效率分析的一般模式非递归算法效率分析的一般模式： 确定描述输入规模的参数 识别算法的基本操作 检查基本操作的执行次数是否只和输入规模有关，如果还和 其他因素有关，则需根据最好、最差和平均情况分别求解 第 25 页 共 148 页 建立表示基本操作执行次数的公式 得出执行次数的通项公式，或者至少确定其阶 例 2检查给定数组中的元素是否彼此不同。 uniqueelement (a1n) /input：数组 a1n) /output：如果所有元素均不相同，返回 true；否则，返回 false for i = 1 to n 1 do for j = i + 1 to n do if ai = aj return false return true 输入规模输入规模：数组中元素的个数 n 基本操作基本操作：循环内只有比较操作 是否依赖于输入是否依赖于输入：比较的次数不仅与输入规模有关，还和数 组中是否有相同元素，以及相同元素在数组中的位置有关， 此例我们考虑最差情况最差情况 比较次数比较次数：每次内循环的比较都执行，cworst(n)= = 1 11 1 n i n ij = = = 1 1 )1( n i in 1 1 ) 1( n i n 1 1 n i i 1 1 1) 1( n i n 2 ) 1)(2(nn 2 ) 1( n =(n2) 2 ) 1)(2(nn 2 ) 1(nn 例 3给定两个 nn 的矩阵 a 和 b，求 c=ab。 matrixmultiplication(a1n, 1n, b1n, 1n) /input：两个 nn 的矩阵 a 和 b 第 26 页 共 148 页 /output：矩阵 c=ab for i = 1 to n do for j = 1 to n do ci, j = 0 for k = 1 to n do ci, j = ci, j + ai, k * bk, j return c 输入规模输入规模：矩阵的阶 n 基本操作基本操作：最内循环有加法和乘法两种操作，两种操作执行 次数相同，所以取哪个为基本操作都可以 是否依赖于输入是否依赖于输入：对所有输入都一样，故无须区分最好、最 差和平均情况 乘法次数乘法次数：m(n) = =n3 n i n j n k111 1 n i n j n 11 n i n 1 2 2.4 递归算法的数学分析递归算法的数学分析 例 1非负整数 n 的阶乘 f(n) = n! = 1(n1)n，其递归定义如下： 1n=0 f(n) = n f(n1) n0 由此定义，可得其递归算法如下 f(n) /input：非负整数 n 第 27 页 共 148 页 /output：n 的阶乘 if n=0 return 1 else return f(n1)*n 输入规模输入规模：非负整数 n 基本操作基本操作：有比较和乘法，但 n=0 时算法结束，所以基本操 作是 else 分支中的乘法 是否依赖于输入是否依赖于输入：输入仅是一整数，无须区分最好、最差和 平均情况 乘法次数乘法次数：m(n) =+ 对 n0) 1( 1 -nf nm ）中的乘法（计算 1 n*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 时，算法直接返回，不进行乘法，即，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) else hanoi(n1, a, c, b) 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)(2 21 iii inm12)(2 ii inm =12)1(2 11 nn nnm12) 1 (2 11 nn m122 11 nn 12 n 这是一个指数算法指数算法，并且，由于此问题本身的复杂性，这已经 是解决这个问题的最有效方法。另外注意，经常根据递归定义得到 第 29 页 共 148 页 的算法看上去非常简洁，但是要小心看上去的简洁掩盖了实际上的看上去的简洁掩盖了实际上的 低效低效! 2.5 例：例：fibonacci 数列数列 1fibonacci 数列的递推公式为 0n=0 f(n)=1n=1 f(n1)+f(n2) n1 解法一解法一求数列通项公式求数列通项公式 前面求解递归算法效率时，求得通项公式即可获知算法效率， 受此启发，对于递推式给出的数列，如能求得数列的通项公式，则 对任意的输入 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，即，x(n) = x(n1)， a b 这是一个等比数列，其通解为 x(n) = rn，公比 r = ， 的值由初 a b 始条件确定。 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。对此方程解的不同情况，递推关系的通解如下： 方程有二不等实根方程有二不等实根 r1，r2：递推关系的通解为 x(n)=+ ， n r1 n r2 其中 和 的值由初始条件确定 方程有二相等实根方程有二相等实根 r：递推关系的通解为 x(n)=+ n，其中 n r n r 和 的值由初始条件确定 方程有二共轭虚根方程有二共轭虚根 r1, 2=u iv：由于算法分析所考虑的数列均为 非负数，数列递推关系的通解 x(n)=( cos n+ sin n)，其中 n =，=arc tan ， 和 的值由初始条件确定 22 vu u v 对于 a x(n)+b x(n1)+c x(n2) = f(n)的情形，它的通解是相应齐 次递推关系的通解与该非齐次递推关系的一个特解之和。不像求通 解，求特解的无一般方法，常用的方法是尝试与 f(n)同阶的函数。 上述求解二阶常系数线性递推关系的方法可推广到上述求解二阶常系数线性递推关系的方法可推广到 n 阶常系数阶常系数 线性递推关系。线性递推关系。 例，解递推关系 x(n)6x(n1)+9x(n2) = 4。 特征方程为 r2 6 r + 9 = 0，有二相等实根 r=3，相应齐次递 推关系的通解为 x(n)=+ n n 3 n 3 f(n)