算法分析与设计讲稿(1)重点讲义资料.doc

目录第一章绪论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.5模算术423.6素性检测423.7密码学42第四章分治法（DEVIDE-AND-CONQURE）434.1 主定理（Master Theorem）434.2 归并排序444.3 快速排序464.4 大整数乘法494.5 Strassen矩阵乘法504.6快速傅里叶变换FFT52第五章减治法（DECRESE-AND-CONQURE）585.1 插入排序585.2 深度优先搜索和广度优先搜索595.3 生成组合对象的算法635.4 二叉搜索（折半查找）675.5 乘法和乘方问题695.6 Euclid算法分析71第六章时空权衡（TIME AND SPACE TRADEOFFS）与动态规划（DYNAMIC PROGRAMMING）726.1 计数排序726.2 高效串匹配算法736.3 再谈Fibonacci数列786.4 有向无环图中最短路径796.5 计算传递闭包的Warshall算法和多源最短路径问题的Floyd算法816.6 矩阵链相乘问题846.7 最优二叉搜索树866.8 最长递增子序列896.9 编辑距离896.10 背包问题926.11 旅行商TSP问题95第七章贪心法（GREEDY TECHNIQUES）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.3 P，NP和NP完全问题1349.4 回溯法（Backtracking）1399.5 分支限界法（Branch-and-Bound）1419.6 近似算法（Approximation algorithms）144第一章绪论1.1 算法的概念算法：解决一个问题的无歧义的指令序列，对合法的输入在有限的时间内可得到需要的输出。算法的一些特点：这才叫算法n 无歧义性（确定性）：算法的每个步骤必须确定无疑n 有穷性：算法的执行必须有限步终止n 输入的范围：算法只对这指特定问题的算法满足条件的输入有响应 n 正确性：算法应能解决要求的问题n 同一算法的不同表示形式：自然语言、伪代码、高级语言n 同一问题存在的多种算法：设计思想不同，时空性能各异例，求两个正整数m和n的最大公因子的算法算法一最容易想到的算法挨个检查Step 1t = min m, nStep 2如果m除以t的余数为0，转Step 3；否则，转Step 4；Step 3如果n除以t的余数为0，返回t的值；否则，转Step 4；Step 4t = t 1，转Step 2。分析：n 上述步骤每一步均确定没有歧义，是一个循环结构程序n 循环执行次数未知，那么它会有限步终止吗？（每次t 1）n 该算法由自然语言描述n 该算法正确吗？如何证明？算法二小学数学中讲述的算法Step 1将m分解质因子；Step 2将n分解质因子；Step 3寻找Step 1和Step 2得到的两个质因子连乘积的公共部分（注：若m的分解中质因子p出现了x次，n的分解中p出现了y次，作为公共部分，p应出现minx, y次）；Step 4计算公共部分的连乘积，并将结果返回。分析：此算法中，如何分解质因子没说明，如何寻找公共部分不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法，至少有待进一步具体说明！考虑如何具体说明：n 分解质因子需要知道有哪些质数n 寻找公共部分涉及到质因子连乘积的表示形式算法三Euclid算法（记录于公元前3世纪Euclid所著的Elements）Euclid (m, n)/Input：两个正整数m和n/Output：m和n的最大公因子while n0 dor = m mod nm = nn = rreturn m分析：n 上述步骤每一步均确定没有歧义，是一个循环结构程序n 循环执行次数未知，那么它有限步终止吗？（每次n都减小）n 该算法由伪代码描述：伪代码是自然语言和编程语言的混合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互质。比较上述三个算法，很明显，Euclid算法形式简单，循环次数少（后面会进行详细分析），所以我们说Euclid算法更高效。1.2 算法问题求解基础算法是求解的具体指令，不是解答。设计和分析算法的典型步骤：1. 理解问题1) 仔细阅读问题描述2) 手工测试几个例子3) 思考特殊情形4) 分析是否已有该类问题的算法2. 确定计算设备的能力现行的绝多数算法都是基于冯·诺依曼机器模型的，即，随机存储模型，它假定指令依次执行，每次执行一个操作，在这样机器上执行的算法称为sequential算法。适合于现在新兴的可同时执行多条操作的计算机的算法，称为并行算法。除非对某些本质上复杂、需处理大量数据或者对时间要求很高的问题，无需担心现在计算机的能力！3. 选择精确算法还是近似算法1) 存在某些问题不能精确解决，例如求平方根2) 可精确解决的算法难以接受的慢，例如，TSP问题3) 近似算法可以是某些更为复杂的精确算法的组成部分4. 确定合适的数据结构存在某些算法设计方法固有依赖于描述问题的数据结构。5. 算法设计方法本课程所要解决的主要问题。算法设计方法（或策略）是指：从算法上解决问题的通用方法，可适用于不同领域的各种各样的问题。学习这些方法的原因：1) 有助于为新问题设计算法，授人以鱼不如授人以渔2) 每门学科都对其研究主题进行分类，算法是计算机科学的基础，有助于根据设计思想对算法进行分类6. 描述算法的方法1) 自然语言描述，如前例中算法一、二2) 伪代码描述，如前例中算法三Euclid算法，无统一格式3) 流程图，只适合于描述很简单的算法4) 某种计算机语言写成的程序7. 证明算法的正确性一旦算法描述清楚，就需要证明其正确性，即，它对每一个合法的输入都可以在有限的时间内得出需要的结果。证明算法正确的一个常用方法是：数学归纳法。注意：测试几组输入数据的方法虽然简单，但却不足以说明算法正确！不过却可以说明一个算法不正确！8. 算法分析算法应具有的几个品质：本课程所要解决的主要问题1) 正确性2) 效率：时间效率和空间效率。第二章详述3) 简洁性：无法用数学定义精确描述，最好给人以美感例，前述的求gcd的算法哪个更简单？简单的算法易于理解，易于编程，通常包含较少的bug，一般也更有效率4) 通用性：同样的效率，解决的问题可适用范围当然越广越好，但是有时通用算法难设计且效率差，或者根本无通用算法例，判定两个正整数是否互质的算法就没有求gcd的通用；二次方程求根公式存在的，但没有任意次方程的求根方法9. 算法编码实现1) 注意程序严格准确的实现算法2) 算法到程序的过渡：算法中假设输入都是合法的，程序中需验证3) 程序的正确性验证的实际方式：测试（testing）。4) 学习编程技巧，以提高程序效率最优算法（optimality）：不是算法效率的问题，而是算法解决问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价最少。某些问题的最优算法是存在的，比如，通过比较进行排序的最优算法需要进行n log n次比较；但某些看上去简单的问题，还未找到最优算法，例如，矩阵乘法。不可判定性(undecidability)：不是说，每个问题均有算法解决（注意，这不同于一个问题没有解，例如，判别式为负的二次方程无实数解）。所幸的是，实际计算中的绝大多数问题还是有解决算法的。1.3 重要的问题类型后面的章节将以以下问题展开，讨论不同算法的设计技术与分析方法。1. 排序我们经常遇到排序问题，比如学校学生按学号排序，学号通常被称为key。那么为什么要进行排序？排序使得很多关于列表的问题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法的辅助步骤，比如，在几何算法中。当前，已有很多排序算法，在这些算法当中，有些较好的可将任意n个元素通过大约n log2 n比较完成排序，但是没有哪一个通过关键字比较的排序算法能比n log2 n作的更好！排序算法的两个性质：排序是否稳定（保持输入相等元素的相对次序不变）和是否需要大量辅助空间（in place排序）。2. 搜索（查找）同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜索（要求元素已排序），等等。由于搜索经常与添加和删除操作联系在一起，所以，需仔细设计数据结构。3. 字符串处理由于所有程序在计算机看来都是字符串，所以此类算法同计算机语言和编译紧密相关。此类算法中最特殊的一个字符串匹配在给定文本中搜索给定单词，在实际中非常有用。4. 图论问题算法中最古老而又吸引人的领域就是图算法。图可以看作是由若干结点和若干个连接其中某些结点的边所构成，其准确定义下一小节给出。图可以为日常很多应用建模，比如，交通和通信网，项目调度，博弈。最基本的图算法包括：图遍历算法（如何遍历网络中所有结点），最小生成树算法（如何铺设最经济的通信网络），最短路径算法（如何确定两城市间的最佳路线），有向图的拓扑排序（如何确定专业课程的学习顺序），等等。有些图论问题非常复杂，以至于最快的计算机也只能解决较小规模的这类问题，比如，旅行商问题（遍历n个城市每个一次的最短线路）和图着色问题（给图的结点着色以使相邻结点颜色不同的最少颜色数），例如，多叉路口交通灯的设计就是一个图着色问题。5. 组合问题更抽象的讲，旅行商问题和图着色问题都是组合问题的例子。组合问题寻求满足某些约束条件或者某些期望性质的组合对象（排列，组合，多重集）。组合问题被认为是计算机科学中最困难的问题，因为：n 随着问题规模扩大，组合对象的数目急剧扩大n 没有已知的算法可在可接受的时间内解决大多数此类问题n 大多数计算机科学家相信不存在可接受时间内解决此类问题的算法，但不能证实和证伪6. 几何问题几何问题处理点、线、多边形。应用领域包括计算机图形学，机器人学，X线断层摄影学。典型算法，比如寻找平面内n个点中的最近点对算法。7. 数值问题涉及到数学问题的求解，比如，解方程或方程组，计算定积分，等等。大多数这类问题只能近似解决，主要一个原因是他们的操作对象是实数，计算机只能够近似表述。1.4 基本数据结构1. 线性数据结构两种基本的线性数据结构是数组和链表。数组的特点：n 每个元素类型相同，占有同样大小的存储空间n 整个数组连续存储，任意元素可通过下标随机访问单（双、循环）链表的特点：n 非连续存储，访问某个元素的时间与其在链表中的位置有关n 无需预留存储空间，插入和删除操作方便数组和链表均可用于实现抽象数据结构线性表，其基本操作是：搜索、插入、删除。两种特殊的线性表：栈（LIFO）和队列（FIFO）。2. 图图G =(V, E)，其中V是顶点（结点）的有限集，E是顶点对（边）所构成的集合。如果边没有方向性，称G是无向图；否则，称G为有向图。 例：如上左图为无向图，其中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，自回路），但除非明确说明，我们所讲的图不包含圈。n 无向图的性质：0 |E| |V|(|V| 1)/ 2n 完全图：每对顶点均有边相连，|V|个顶点的完全图记作K|V|n 稠密图（dense）和稀疏图（sparse）图的表示：算法中最主要的两种表示是邻接矩阵和邻接表。上左图的邻接矩阵和邻接表表示如下：对无向图而言，其邻接矩阵总是对称的。Why？显然，稀疏图用邻接表更节省存储空间。Why？但具体某问题采用何种表示，更加依赖于解决该问题的算法的性质。n 加权图（weighted graph）：图中边赋有值，称为权或cost。比如实际应用中，交通图中两城市间的公路距离。邻接矩阵和邻接表均可用于存储加权图。矩阵中的值可表示距离（无边的是为），邻接表的每一结点可添加一项表示距离n 路径（path）：从顶点u到顶点v的路径，是指始于u终于v有边连接的顶点序列（有向图中，要求边的方向均为从u至v方向）。若除起止点外路径中无顶点重复，称简单路径。路径长度指路径中的边数（即，顶点数减1）。n 连通图（connected）：图中的每对顶点均有路径连接n 子图（subgraph）：图G=(V, E)称为图G的子图，当且仅当，VV并且E En 连通子图（connected component）：如果一个图不是连通的，它将包含若干个连通子图。连通子图指，添加任何结点则不连通的极大子图。下图就不是一个连通图，它有两个连通子图，其顶点集分别是a, b, c, d, e和f, g, h, i。思考：中国的省际公路网是否是一个连通图？(注意台湾和海南!)n 环路（cycle）：起止点为同一结点且路径长度为正的简单路径。没有环路的图称为无环图（acyclic）。n Hamilton回路：起止点为同一结点，且只经过图中其它结点一次的环路n Euler回路：起止点为同一结点，且只经过图中所有边一次的环路3. 树树是一个连通的无环图。森林：不连通的无环图，其每个连通子图是一棵树。n 树的性质1：|E| = |V| 1。注意，这是图成为树的必要条件，而不是充分条件。Why? 因为图不一定连通，不连通的图却可以有环，仍能满足此条件！n 树的性质2：任意两结点间均有唯一的简单路径。Why?n 根树（rooted trees）：性质2使得选择任一结点为根成为可能。所得树称为根树。一般从上至下依次画出根和各层结点。根树有广泛的应用，常简称为树，下面的树均指根树。所谓双亲、孩子、祖先、子孙、子树、叶子等概念，不再详述。n 结点的深度（depth）：从根到该结点的简单路径的长度n 树的高度（height）：从根到叶子的最长的简单路径的长度。n 有序树（ordered trees）：每个结点的所有孩子是有序的。假定树中以从左至右表示顺序。二叉树（binary trees）是最常用的有序树，从而有左孩子、右孩子、左子树、右子树的概念。一般的有序树可以用“左孩子、右兄弟”的方式表示成二叉树。4. 集合与字典集合（set）：不同元素组成的一个无序的整体。常用的集合操作：membership、union和intersection。字典：一种数据结构，用于实现对给定集合进行搜索、添加和删除元素这三种操作。集合的表示形式：给定全集U的bit vector表示和列表表示。第二章算法效率分析基础算法分析的重点是算法效率的分析，因为它可以量化（不像简洁性和通用性），关注的是时间效率（time efficiency）和空间效率（space efficiency）。2.1 分析框架对于给定问题，一个算法的n 时间效率：指它运行的有多快（running time）n 空间效率：指它需要多大的额外空间（memory space）随着计算机技术的革新，越来越大容量的存储器的出现，算法对空间的需要已不再是什么问题，但是时间效率却没有相应的提高，因此，我们关注的重点是时间效率，但分析框架完全适用于空间效率。1. 度量输入规模算法的效率和输入规模n有关，因为几乎所有算法对大的输入运行时间要长一些。例如，对较大的数组排序，两个较高维数的矩阵相乘，等等。关键是n如何确定?例，对一个列表的排序、搜索或者寻找其中最小元素，显然，n即列表中元素的个数；矩阵相乘，n可以是矩阵的维数，也可以是矩阵中元素的个数；而大整数相乘，则n取大整数的位数比取大整数本身更合适。2. 度量运行时间的单位n 秒、毫秒等时间单位：依赖于特定机器的性能，我们需要的是一种不依赖于外部因素、只决定于算法本身的衡量标准n 算法中各种操作执行的次数：精确，但过于困难且没有必要n 算法中基本操作执行的次数：对算法总运行时间贡献最大的、最重要的操作例，对一个列表的排序，位于最内循环中的操作肯定执行次数最大，选择元素的比较操作为基本操作；矩阵相乘，需要对应元素一一相乘并求和，又因为大多数计算机中乘法比加法慢，所以选择乘法为基本操作；而大整数相乘，则宜取每一位的乘法为其基本操作。因为实际运行时间T和基本操作的执行次数C关于输入规模n近似的成一定的比例，即，T(n) k C(n)，要分析时间效率，就要建立输入规模n和基本操作执行次数C之间的函数关系C(n)。例，假设C(n)=，当输入规模翻番时，运行时间如何变化？（当n足够大时）注意：n 实际运行时间和基本操作执行次数所成的比例k对最后的结果没有影响n 函数C(n)中的常数因子对最后的结果没有影响n 考虑较大输入规模时，低阶量对最后的结果没有影响为什么分析效率只考虑较大输入规模的情形？输入规模较小时，不同算法之间的效率差异不明显！3. 函数的阶（分析效率时的关注重点）nnnn2n!103.3103.3101010103.610106.6106.61010101.3109.3101010101.01010101013101.31010101017101.71010101020102.0101010书上P7有类似表。，可见底数不同的对数函数之间只相差一个常数因子，由前讨论，可以忽略，今后忽略底数，写作log n。指数函数和阶乘函数增长过快，只适合求解很小的输入规模，今后统称作指数函数。4. 最坏、最好和平均情况有很多算法的性能不仅和输入规模有关，还和特定的输入有关。例，在以数组A1 . n表示的线性表中顺序搜索某个值K，找到则返回下标值，返回1表示未找到。 SequentialSearch (A1.n, K)/Input：数组A1.n和搜索值K/Output：若有A中元素等于K，返回该元素下标，否则返回1i = 1while i n doif K = Ai return i/基本操作为此处的比较else i = i + 1return 1n 最坏情况：所有同规模的输入中，算法运行时间最长的输入n 最好情况：所有同规模的输入中，算法运行时间最快的输入n 平均情况：随机输入的运行情况，需对输入做某些假定对上述线性搜索，Cworst(n)= n，Cbest(n)=1。假定，对任意输入，能搜索到的概率为p，且在任一位置找到的可能性相同，则如果p=1，则表示一定能找到，平均比较次数为；如果p=0，则表示一定找不到，也需比较n次。n 最坏情况：决定算法运行时间的上限，常用n 最好情况：除极少情况，很难保证算法总处于最好，不常用n 平均情况：需进行概率分析，运算复杂，但有时很有必要，尤其当平均情况远不像最差情况那么糟的时候。注意：平均情况不是最坏情况和最好情况的平均n 分摊效率：有些算法的第一次运行代价很高，但多次运行的代价却比第一次的代价乘以运行次数的值要小的多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)，n+n+1O(n2)。2. 记号：函数t(n)(g(n)如果存在某个正常数c和某个非负整数n0使得对所有nn0，t(n)c g(n)。例， n(n2)，因为对所有n0，nn2，此处c=1，n0=0。试证明，n2(n)，(n2)，100n+5(n2)。3. 记号：函数t(n)(g(n)如果存在正常数c1和c2和某个非负整数n0使得对所有nn0，c1 g(n)t(n)c2 g(n)。例，（对所有n0）（对所有n2）所以，取c1=，c2=，n0=2，有(n2)。4. 渐进符号的性质n 性质1如果t1(n)O(g1(n)，t2(n)O(g2(n)，则t1(n) + t2(n) O(maxg1(n),g2(n)n 性质2如果t1(n)(g1(n)，t2(n)(g2(n)，则t1(n) + t2(n) (maxg1(n),g2(n)n 性质3如果t1(n)(g1(n)，t2(n)(g2(n)，则t1(n) + t2(n) (maxg1(n),g2(n)性质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)。5. 使用极限比较函数的阶0t(n)的阶小于g(n)c t(n)与g(n)有相同的阶 t(n)的阶高于g(n)例，(n2)，比的阶小。6. 基本效率类型即使不考虑常数因子，仍然有无穷多种函数的阶类型。类型名称描述1常数某些算法的最好情况，实际中很少log n对数每次迭代输入规模以常数因子递减的算法n线性需扫描整个输入的算法n log nn-log-n许多分治算法属于此类，如归并排序和快速排序n平方有两重循环的算法，如冒泡排序和选择排序n立方有三重循环的算法，如矩阵乘法2指数产生输入集所有子集的算法n！阶乘产生输入集元素全排列的算法2.3 非递归算法的数学分析例1在n个元素的线性表（以数组A1.n表示）中寻找最大元素。MaxElement(A1.n)/Input：数值型数组A1.n/Output：A中最大元素的值maxval = A1for i = 2 to n doif ai>maxval maxval = Aireturn maxvaln 输入规模：数组中元素的个数nn 基本操作：最频繁执行的操作在循环内，循环内有比较和赋值，但赋值不是每次都做，故比较为基本操作n 是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况n 比较次数：C(n) = = n 1 (n)非递归算法效率分析的一般模式：n 确定描述输入规模的参数n 识别算法的基本操作n 检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解n 建立表示基本操作执行次数的公式n 得出执行次数的通项公式，或者至少确定其阶例2检查给定数组中的元素是否彼此不同。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 truen 输入规模：数组中元素的个数nn 基本操作：循环内只有比较操作n 是否依赖于输入：比较的次数不仅与输入规模有关，还和数组中是否有相同元素，以及相同元素在数组中的位置有关，此例我们考虑最差情况n 比较次数：每次内循环的比较都执行，Cworst(n)= = = = =(n2)例3给定两个n×n的矩阵A和B，求C=AB。MatrixMultiplication(A1.n, 1.n, B1.n, 1.n)/Input：两个n×n的矩阵A和B/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, jreturn Cn 输入规模：矩阵的阶nn 基本操作：最内循环有加法和乘法两种操作，两种操作执行次数相同，所以取哪个为基本操作都可以n 是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况n 乘法次数：M(n) = =n32.4 递归算法的数学分析例1非负整数n的阶乘F(n) = n! = 1(n1)n，其递归定义如下：1n=0F(n) = n F(n1)n>0由此定义，可得其递归算法如下F(n)/Input：非负整数n/Output：n的阶乘if n=0 return 1else return F(n1)*nn 输入规模：非负整数nn 基本操作：有比较和乘法，但n=0时算法结束，所以基本操作是else分支中的乘法n 是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况n 乘法次数：M(n) =+ 对n>0这是一个递推公式，要求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递归算法效率分析的一般模式：n 确定描述输入规模的参数n 识别算法的基本操作n 检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解n 建立表示基本操作执行次数的递推公式n 解递推式，得出执行次数的通项公式，或者至少确定其阶例2Tower of Hanoi问题的递归算法如下Hanoi(n, A, B, C)/Input：要搬运的盘子总数n/Output：塔上盘子的搬运过程if n=1 Move(n, A, C)elseHanoi(n1, A, C, B)Move(n, A, C)Hanoi(n1, B, A, C)n 输入规模：盘子总数nn 基本操作：有比较和搬运操作Move，此处去Move，why？n 是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况n 搬运次数：M(n) = M(n1)+1+ M(n1) 对n>1又，只有一个盘子（即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 = =这是一个指数算法，并且，由于此问题本身的复杂性，这已经是解决这个问题的最有效方法。另外注意，经常根据递归定义得到的算法看上去非常简洁，但是要小心看上去的简洁掩盖了实际上的低效!2.5 例：Fibonacci数列此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。Fibonacci数列的递推公式为0n=0F(n)=1n=1F(n1)+F(n2)n>1解法一求数列通项公式前面求解递归算法效率时，求得通项公式即可获知算法效率，受此启发，对于递推式给出的数列，如能求得数列的通项公式，则对任意的输入n，求解F(n)的时间仅依赖于通项公式的复杂程度。但此处逆向回推法会让人迅速放弃！二阶常系数线性递推关系a x(n)+b x(n1)+c x(n2) = f(n)的求解n 二阶：待求递推关系最高项x(n)与最低项x(n2)相差两阶n 线性：左侧是递推关系未知项的线性组合n 常系数：a，b，c均为常数n 齐次：如果f(n)=0；否则，称为非齐次考虑最简单情形a x(n) + b x(n1) = 0，即，x(n) = x(n1)，这是一个等比数列，其通解为x(n) = rn，公比r = ，的值由初始条件确定。对于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。对此方程解的不同情况，递推关系的通解如下：n 方程有二不等实根r1，r2：递推关系的通解为x(n)=+ ，其中和的值由初始条件确定n 方程有二相等实根r：递推关系的通解为x(n)=+ n，其中和的值由初始条件确定n 方程有二共轭虚根r1, 2=u±iv：由于算法分析所考虑的数列均为非负数，数列递推关系的通解x(n)=( cos n+ sin n)，其中=，=arc tan ，和的值由初始条件确定对于a x(n)+b x(n1)+c x(n2) = f(n)的情形，它的通解是相应齐次递推关系的通解与该非齐次递推关系的一个特解之和。不像求通解，求特解的无一般方法，常用的方法是尝试与f(n)同阶的函数。上述求解二阶常系数线性递推关系的方法可推广到n阶常系数线性递推关系。例，解递推关系x(n)6x(n1)+9x(n2) = 4。n 特征方程为r2 6 r + 9 = 0，有二相等实根r=3，相应齐次递推关系的通解为x(n)=+ nn f(n)=4，同阶的函数同样为常数，设为c，代入得c6c+9c=4，解得c=1n 递推关系x(n)6x(n1)+9x(n2) = 4的通解为x(n)=+n+1求解Fibonacci数列的通项公式n 特征方程为r2 r1 = 0，有二不等实根，通解为F(n)=+ n 将F(0)=0，F(1)=1代入得 += 0+ = 1n 解此二元一次方程组得=，=F(n) = 解法二用递归算法求数列第n项F(n)/Input：非负整数n/Output：Fibonacci数列第n项if n1 return nelse return F(n1)+ F(n2)n 输入规模：非负整数nn 基本操作：有比较和加法，但n1时算法结束，所以基本操作是else分支中的加法n 是否依赖于输入：无须区分最好、最差和平均情况n 加法次数：A(n) = A(n1)+A(n2)+1 对n>0，A(0) = A(1) =0n 这是一个二阶常系数线性非齐次递推关系，其对应齐次递推关系的特征方程为r2r1=0，与Fibonacci数列通解相同n f(n)=1，同阶的函数同