算法分析与设计

目录第一章绪论311算法的概念312算法问题求解基础613重要的问题类型914基本数据结构11第二章算法效率分析基础1621分析框架1622渐进符号和基本效率类型1923非递归算法的数学分析2224递归算法的数学分析2525例FIBONACCI数列27第三章蛮力法（BRUTEFORCE）和算术问题3331选择排序和冒泡排序3332蛮力字符串匹配3533穷举搜索（EXHAUSTIVESEARCH）3634基本算术4035模算术4236素性检测4237密码学42第四章分治法（DEVIDEANDCONQURE）4341主定理（MASTERTHEOREM）4342归并排序4443快速排序4644大整数乘法4945STRASSEN矩阵乘法5046快速傅里叶变换FFT52第五章减治法（DECRESEANDCONQURE）5851插入排序5852深度优先搜索和广度优先搜索5953生成组合对象的算法6354二叉搜索（折半查找）6755乘法和乘方问题6956EUCLID算法分析71第六章时空权衡（TIMEANDSPACETRADEOFFS）与动态规划（DYNAMICPROGRAMMING）7261计数排序7262高效串匹配算法7363再谈FIBONACCI数列7864有向无环图中最短路径7965计算传递闭包的WARSHALL算法和多源最短路径问题的FLOYD算法8166矩阵链相乘问题8467最优二叉搜索树8668最长递增子序列8969编辑距离89610背包问题92611旅行商TSP问题95第七章贪心法（GREEDYTECHNIQUES）9971连续背包问题9972最小生成树问题（MST，MINIMUMSPANNINGTREE）10273单源最短路径问题的DIJKSTRA算法10974HUFFMAN编码11275集合覆盖118第八章线性规划（LINEARPROGRAMMING）11981线性规划简介11982求解线性规划问题的单纯形算法12283网络流问题12984二部图的匹配问题12985对偶12986零和游戏130第九章算法能力的极限13191求算法下界的方法13192问题归约13293P，NP和NP完全问题13494回溯法（BACKTRACKING）13995分支限界法（BRANCHANDBOUND）14196近似算法（APPROXIMATIONALGORITHMS）144第一章绪论11算法的概念算法解决一个问题的无歧义的指令序列，对合法的输入在有限的时间内可得到需要的输出。算法的一些特点无歧义性（确定性）算法的每个步骤必须确定无疑有穷性算法的执行必须有限步终止输入的范围算法只对满足条件的输入有响应正确性算法应能解决要求的问题同一算法的不同表示形式自然语言、伪代码、高级语言同一问题存在的多种算法设计思想不同，时空性能各异例，求两个正整数M和N的最大公因子的算法算法一最容易想到的算法挨个检查STEP1TMINM,NSTEP2如果M除以T的余数为0，转STEP3；否则，转STEP4；STEP3如果N除以T的余数为0，返回T的值；否则，转STEP4；STEP4TT1，转STEP2。分析上述步骤每一步均确定没有歧义，是一个循环结构程序这才叫算法这指特定问题的算法循环执行次数未知，那么它会有限步终止吗（每次T1）该算法由自然语言描述该算法正确吗如何证明算法二小学数学中讲述的算法STEP1将M分解质因子；STEP2将N分解质因子；STEP3寻找STEP1和STEP2得到的两个质因子连乘积的公共部分（注若M的分解中质因子P出现了X次，N的分解中P出现了Y次，作为公共部分，P应出现MINX,Y次）；STEP4计算公共部分的连乘积，并将结果返回。分析此算法中，如何分解质因子没说明，如何寻找公共部分不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法，至少有待进一步具体说明考虑如何具体说明分解质因子需要知道有哪些质数寻找公共部分涉及到质因子连乘积的表示形式算法三EUCLID算法（记录于公元前3世纪EUCLID所著的ELEMENTS）EUCLIDM,N/INPUT两个正整数M和N/OUTPUTM和N的最大公因子WHILEN0DORMMODNMNNRRETURNM分析上述步骤每一步均确定没有歧义，是一个循环结构程序循环执行次数未知，那么它有限步终止吗（每次N都减小）该算法由伪代码描述伪代码是自然语言和编程语言的混合该算法正确吗如何证明证明设函数GCDM,N就是采用EUCLID算法计算最大公因子的函数。则算法的正确性基于两个事实若M0，则GCDM,0MGCDM,NGCDN,MMODN第一个事实显然易见。设DGCDM,N且MKNT。则存在A，B使得MAD，NBD，且A与B互质。MMODNTMKNADKBDAKBD。说明D是N和MMODN的公因子，还需说明，B与AKB互质。假设B与AKB有公因子C。即，BUC，AKBVC。则AKUCVCKUVC，MKUVCD，NBDUCD，由D是M与N的最大公因子得C1，即B与AKB互质。比较上述三个算法，很明显，EUCLID算法形式简单，循环次数少（后面会进行详细分析），所以我们说EUCLID算法更高效。12算法问题求解基础算法是求解的具体指令，不是解答。设计和分析算法的典型步骤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）不是算法效率的问题，而是算法解决问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价最少。某些问题的最优算法是存在的，比如，通过比较进行排序的最优算法需要进行NLOGN次比较；但某些看上去简单的问题，还未找到最优算法，例如，矩阵乘法。不可判定性UNDECIDABILITY不是说，每个问题均有算法解决（注意，这不同于一个问题没有解，例如，判别式为负的二次方程无实数解）。所幸的是，实际计算中的绝大多数问题还是有解决算法的。13重要的问题类型后面的章节将以以下问题展开，讨论不同算法的设计技术与分析方法。1排序我们经常遇到排序问题，比如学校学生按学号排序，学号通常被称为KEY。那么为什么要进行排序排序使得很多关于列表的问题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法的辅助步骤，比如，在几何算法中。当前，已有很多排序算法，在这些算法当中，有些较好的可将任意N个元素通过大约NLOG2N比较完成排序，但是没有哪一个通过关键字比较的排序算法能比NLOG2N作的更好排序算法的两个性质排序是否稳定（保持输入相等元素的相对次序不变）和是否需要大量辅助空间（INPLACE排序）。2搜索（查找）同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜索（要求元素已排序），等等。由于搜索经常与添加和删除操作联系在一起，所以，需仔细设计数据结构。3字符串处理由于所有程序在计算机看来都是字符串，所以此类算法同计算机语言和编译紧密相关。此类算法中最特殊的一个字符串匹配在给定文本中搜索给定单词，在实际中非常有用。4图论问题算法中最古老而又吸引人的领域就是图算法。图可以看作是由若干结点和若干个连接其中某些结点的边所构成，其准确定义下一小节给出。图可以为日常很多应用建模，比如，交通和通信网，项目调度，博弈。最基本的图算法包括图遍历算法（如何遍历网络中所有结点），最小生成树算法（如何铺设最经济的通信网络），最短路径算法（如何确定两城市间的最佳路线），有向图的拓扑排序（如何确定专业课程的学习顺序），等等。有些图论问题非常复杂，以至于最快的计算机也只能解决较小规模的这类问题，比如，旅行商问题（遍历N个城市每个一次的最短线路）和图着色问题（给图的结点着色以使相邻结点颜色不同的最少颜色数），例如，多叉路口交通灯的设计就是一个图着色问题。5组合问题更抽象的讲，旅行商问题和图着色问题都是组合问题的例子。组合问题寻求满足某些约束条件或者某些期望性质的组合对象（排列，组合，多重集）。组合问题被认为是计算机科学中最困难的问题，因为随着问题规模扩大，组合对象的数目急剧扩大没有已知的算法可在可接受的时间内解决大多数此类问题大多数计算机科学家相信不存在可接受时间内解决此类问题的算法，但不能证实和证伪6几何问题几何问题处理点、线、多边形。应用领域包括计算机图形学，机器人学，X线断层摄影学。典型算法，比如寻找平面内N个点中的最近点对算法。7数值问题涉及到数学问题的求解，比如，解方程或方程组，计算定积分，等等。大多数这类问题只能近似解决，主要一个原因是他们的操作对象是实数，计算机只能够近似表述。14基本数据结构1线性数据结构两种基本的线性数据结构是数组和链表。数组的特点每个元素类型相同，占有同样大小的存储空间整个数组连续存储，任意元素可通过下标随机访问单（双、循环）链表的特点非连续存储，访问某个元素的时间与其在链表中的位置有关无需预留存储空间，插入和删除操作方便数组和链表均可用于实现抽象数据结构线性表，其基本操作是搜索、插入、删除。两种特殊的线性表栈（LIFO）和队列（FIFO）。2图图GV,E，其中V是顶点（结点）的有限集，E是顶点对（边）所构成的集合。如果边没有方向性，称G是无向图；否则，称G为有向图。AEDCBDFACFEB例如上左图为无向图，其中VA,B,C,D,E,F，EA,C,A,D,B,C,B,F,C,E,D,E,E,F；右图为有向图，其中VA,B,C,D,E,F，EA,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）图的表示算法中最主要的两种表示是邻接矩阵和邻接表。上左图的邻接矩阵和邻接表表示如下FEDCBAFEDCBA0101100ACBFEDCFEBCAACDEDEBF对无向图而言，其邻接矩阵总是对称的。WHY显然，稀疏图用邻接表更节省存储空间。WHY但具体某问题采用何种表示，更加依赖于解决该问题的算法的性质。加权图（WEIGHTEDGRAPH）图中边赋有值，称为权或COST。比如实际应用中，交通图中两城市间的公路距离。邻接矩阵和邻接表均可用于存储加权图。矩阵中的值可表示距离（无边的是为），邻接表的每一结点可添加一项表示距离ADCB523187AB,2BDCA,2A,5A,7C,5C,8B,3B,8D,7D,3D,1C,1路径（PATH）从顶点U到顶点V的路径，是指始于U终于V有边连接的顶点序列（有向图中，要求边的方向均为从U至V方向）。若除起止点外路径中无顶点重复，称简单路径。路径长度指路径中的边数（即，顶点数减1）。连通图（CONNECTED）图中的每对顶点均有路径连接子图（SUBGRAPH）图GV,E称为图G的子图，当且仅当，VV并且EE连通子图（CONNECTEDCOMPONENT）如果一个图不是连通的，它将包含若干个连通子图。连通子图指，添加任何结点则不连通的极大子图。下图就不是一个连通图，它有两个连通子图，其顶点集分别是A,B,C,D,E和F,G,H,I。CBDAEFGHI思考中国的省际公路网是否是一个连通图注意台湾和海南环路（CYCLE）起止点为同一结点且路径长度为正的简单路径。没有环路的图称为无环图（ACYCLIC）。HAMILTON回路起止点为同一结点，且只经过图中其它结点一次的环路EULER回路起止点为同一结点，且只经过图中所有边一次的环路3树树是一个连通的无环图。森林不连通的无环图，其每个连通子图是一棵树。ABCFDE1树ABCFDG2森林EHIJ树的性质1|E|V|1。注意，这是图成为树的必要条件，而不是充分条件。WHY因为图不一定连通，不连通的图却可以有环，仍能满足此条件树的性质2任意两结点间均有唯一的简单路径。WHY根树（ROOTEDTREES）性质2使得选择任一结点为根成为可能。所得树称为根树。一般从上至下依次画出根和各层结点。根树有广泛的应用，常简称为树，下面的树均指根树。所谓双亲、孩子、祖先、子孙、子树、叶子等概念，不再详述。IDCHBGAEFABDECGFHI结点的深度（DEPTH）从根到该结点的简单路径的长度树的高度（HEIGHT）从根到叶子的最长的简单路径的长度。有序树（ORDEREDTREES）每个结点的所有孩子是有序的。假定树中以从左至右表示顺序。二叉树（BINARYTREES）是最常用的有序树，从而有左孩子、右孩子、左子树、右子树的概念。一般的有序树可以用“左孩子、右兄弟”的方式表示成二叉树。4集合与字典集合（SET）不同元素组成的一个无序的整体。常用的集合操作MEMBERSHIP、UNION和INTERSECTION。字典一种数据结构，用于实现对给定集合进行搜索、添加和删除元素这三种操作。集合的表示形式给定全集U的BITVECTOR表示和列表表示。第二章算法效率分析基础算法分析的重点是算法效率的分析，因为它可以量化（不像简洁性和通用性），关注的是时间效率（TIMEEFFICIENCY）和空间效率（SPACEEFFICIENCY）。21分析框架对于给定问题，一个算法的时间效率指它运行的有多快（RUNNINGTIME）空间效率指它需要多大的额外空间（MEMORYSPACE）随着计算机技术的革新，越来越大容量的存储器的出现，算法对空间的需要已不再是什么问题，但是时间效率却没有相应的提高，因此，我们关注的重点是时间效率，但分析框架完全适用于空间效率。1度量输入规模算法的效率和输入规模N有关，因为几乎所有算法对大的输入运行时间要长一些。例如，对较大的数组排序，两个较高维数的矩阵相乘，等等。关键是N如何确定例，对一个列表的排序、搜索或者寻找其中最小元素，显然，N即列表中元素的个数；矩阵相乘，N可以是矩阵的维数，也可以是矩阵中元素的个数；而大整数相乘，则N取大整数的位数比取大整数本身更合适。2度量运行时间的单位秒、毫秒等时间单位依赖于特定机器的性能，我们需要的是一种不依赖于外部因素、只决定于算法本身的衡量标准算法中各种操作执行的次数精确，但过于困难且没有必要算法中基本操作执行的次数对算法总运行时间贡献最大的、最重要的操作例，对一个列表的排序，位于最内循环中的操作肯定执行次数最大，选择元素的比较操作为基本操作；矩阵相乘，需要对应元素一一相乘并求和，又因为大多数计算机中乘法比加法慢，所以选择乘法为基本操作；而大整数相乘，则宜取每一位的乘法为其基本操作。因为实际运行时间T和基本操作的执行次数C关于输入规模N近似的成一定的比例，即，TNKCN，要分析时间效率，就要建立输入规模N和基本操作执行次数C之间的函数关系CN。例，假设CN，当输入规模翻番时，运行时N2121间如何变化（当N足够大时）421222NNNKCT注意实际运行时间和基本操作执行次数所成的比例K对最后的结果没有影响函数CN中的常数因子对最后的结果没有影响21考虑较大输入规模时，低阶量对最后的结果没有影响为什么分析效率只考虑较大输入规模的情形输入规模较小时，不同算法之间的效率差异不明显3函数的阶（分析效率时的关注重点）NN2LOGNN2LOGN2N32NN10331033101010103361061026610266102104106131009310157103101031010106109104131041310510810121051710517106101010510620106201071021018书上P7有类似表。，可见底数不同的对数函数之间只相差一个NBNAALOGLOG常数因子，由前讨论，可以忽略，今后忽略底数，写作LOGN。指数函数和阶乘函数增长过快，只适合求解很小的输入规模，今后统称作指数函数。4最坏、最好和平均情况有很多算法的性能不仅和输入规模有关，还和特定的输入有关。例，在以数组A1N表示的线性表中顺序搜索某个值K，找到则返回下标值，返回1表示未找到。SEQUENTIALSEARCHA1N,K/INPUT数组A1N和搜索值K/OUTPUT若有A中元素等于K，返回该元素下标，否则返回1I1WHILEINDOIFKAIRETURNI/基本操作为此处的比较ELSEII1RETURN1最坏情况所有同规模的输入中，算法运行时间最长的输入最好情况所有同规模的输入中，算法运行时间最快的输入平均情况随机输入的运行情况，需对输入做某些假定对上述线性搜索，CWORSTNN，CBESTN1。假定，对任意输入，能搜索到的概率为P，且在任一位置找到的可能性相同，则如果P1，则表12121NPNNPNCAVG示一定能找到，平均比较次数为；如果P0，则表示一定找不到，也需比较N次。最坏情况决定算法运行时间的上限，常用最好情况除极少情况，很难保证算法总处于最好，不常用平均情况需进行概率分析，运算复杂，但有时很有必要，尤其当平均情况远不像最差情况那么糟的时候。注意平均情况不是最坏情况和最好情况的平均分摊效率有些算法的第一次运行代价很高，但多次运行的代价却比第一次的代价乘以运行次数的值要小的多22渐进符号和基本效率类型本课程所讨论函数均为非负函数。1O记号函数TNOGN如果存在某个正常数C和某个非负整数N0使得对所有NN0，TNCGN。例，100N5100NN101N101N2（对所有N5），所以100N5ON2，此处，取C101，N05；又，100N5100N5N105N（对所有N1），100N5ON，此处，取C105，N01。试证明，NON2，ON2，000001NON2，1N3NN1ON2。42记号函数TNGN如果存在某个正常数C和某个非负整数N0使得对所有NN0，TNCGN。例，NN2，因为对所有N0，NN2，此处C1，N00。33试证明，N2N，N2，100N5N2。13记号函数TNGN如果存在正常数C1和C2和某个非负整数N0使得对所有NN0，C1GNTNC2GN。例，（对所有N0）22112N（对所有N2）241所以，取C1，C2，N02，有N2。424渐进符号的性质性质1如果T1NOG1N，T2NOG2N，则T1NT2NOMAXG1N,G2N性质2如果T1NG1N，T2NG2N，则T1NT2NMAXG1N,G2N性质3如果T1NG1N，T2NG2N，则T1NT2NMAXG1N,G2N性质1的证明T1NOG1N，C1和N1对所有NN1，T1NC1G1NT2NOG2N，C2和N2对所有NN2，T2NC2G2N对所有NMAXN1,N2，T1NT2NC1G1NC2G2NC1MAXG1N,G2NC2MAXG1N,G2NC1C2MAXG1N,G2N取CC1C2，N0MAXN1,N2，即，T1NT2NOMAXG1N,G2N。试证明另外两个性质。例，某算法判断数组中是否包含相同元素，其思想如下，首先将数组排序，然后比较相邻元素是否相同。假设所用排序算法属于ON2，比较相邻元素显然属于ON，则该算法属于OMAXN2,NON2。5使用极限比较函数的阶0TN的阶小于GNCTN与GN有相同的阶TN的阶高于GN例，N221LIM21LI21LIMNNN1N，比0LIOG21LILOGILOGI222ENENNNN2LOG的阶小。6基本效率类型即使不考虑常数因子，仍然有无穷多种函数的阶类型。类型名称描述1常数某些算法的最好情况，实际中很少LOGN对数每次迭代输入规模以常数因子递减的算法N线性需扫描整个输入的算法NLOGNNLOGN许多分治算法属于此类，如归并排序和快速排序N2平方有两重循环的算法，如冒泡排序和选择排序N3立方有三重循环的算法，如矩阵乘法2指数产生输入集所有子集的算法N阶乘产生输入集元素全排列的算法LINGT23非递归算法的数学分析例1在N个元素的线性表（以数组A1N表示）中寻找最大元素。MAXELEMENTA1N/INPUT数值型数组A1N/OUTPUTA中最大元素的值MAXVALA1FORI2TONDOIFAIMAXVALMAXVALAIRETURNMAXVAL输入规模数组中元素的个数N基本操作最频繁执行的操作在循环内，循环内有比较和赋值，但赋值不是每次都做，故比较为基本操作是否依赖于输入对所有输入都一样，故无须区分最好、最差和平均情况比较次数CNN1NI2非递归算法效率分析的一般模式确定描述输入规模的参数识别算法的基本操作检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解建立表示基本操作执行次数的公式得出执行次数的通项公式，或者至少确定其阶例2检查给定数组中的元素是否彼此不同。UNIQUEELEMENTA1N/INPUT数组A1N/OUTPUT如果所有元素均不相同，返回TRUE；否则，返回FALSEFORI1TON1DOFORJI1TONDOIFAIAJRETURNFALSERETURNTRUE输入规模数组中元素的个数N基本操作循环内只有比较操作是否依赖于输入比较的次数不仅与输入规模有关，还和数组中是否有相同元素，以及相同元素在数组中的位置有关，此例我们考虑最差情况比较次数每次内循环的比较都执行，CWORSTN1NIJ1NII1NI1NI1NI22N22例3给定两个NN的矩阵A和B，求CAB。MATRIXMULTIPLICATIONA1N,1N,B1N,1N/INPUT两个NN的矩阵A和B/OUTPUT矩阵CABFORI1TONDOFORJ1TONDOCI,J0FORK1TONDOCI,JCI,JAI,KBK,JRETURNC输入规模矩阵的阶N基本操作最内循环有加法和乘法两种操作，两种操作执行次数相同，所以取哪个为基本操作都可以是否依赖于输入对所有输入都一样，故无须区分最好、最差和平均情况乘法次数MNN3NIJK1NIJ1NI1224递归算法的数学分析例1非负整数N的阶乘FNN1N1N，其递归定义如下1N0FNNFN1N0由此定义，可得其递归算法如下FN/INPUT非负整数N/OUTPUTN的阶乘IFN0RETURN1ELSERETURNFN1N输入规模非负整数N基本操作有比较和乘法，但N0时算法结束，所以基本操作是ELSE分支中的乘法是否依赖于输入输入仅是一整数，无须区分最好、最差和平均情况乘法次数MN对N01NFM）中的乘法（计算N1F中的乘法）（这是一个递推公式，要求MN的通项公式，可逆向回推，得MNMN11MN211MN22MN33MNIIMNNNM0N，又N0时，算法直接返回，不进行乘法，即，M00,MNN递归算法效率分析的一般模式确定描述输入规模的参数识别算法的基本操作检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解建立表示基本操作执行次数的递推公式解递推式，得出执行次数的通项公式，或者至少确定其阶例2TOWEROFHANOI问题的递归算法如下HANOIN,A,B,C/INPUT要搬运的盘子总数N/OUTPUT塔上盘子的搬运过程IFN1MOVEN,A,CELSEHANOIN1,A,C,BMOVEN,A,CHANOIN1,B,A,C输入规模盘子总数N基本操作有比较和搬运操作MOVE，此处去MOVE，WHY是否依赖于输入输入仅是一整数，无须区分最好、最差和平均情况搬运次数MNMN11MN1对N1又，只有一个盘子（即N1）时，需MOVE一次，即，M11。逆向回推，得MN2MN1122MN2114MN22142MN31218MN3421124221IIINM12IINM1NNNN这是一个指数算法，并且，由于此问题本身的复杂性，这已经是解决这个问题的最有效方法。另外注意，经常根据递归定义得到的算法看上去非常简洁，但是要小心看上去的简洁掩盖了实际上的低效25例FIBONACCI数列1FIBONACCI数列的递推公式为0N0FN1N1FN1FN2N1解法一求数列通项公式前面求解递归算法效率时，求得通项公式即可获知算法效率，受此启发，对于递推式给出的数列，如能求得数列的通项公式，则对任意的输入N，求解FN的时间仅依赖于通项公式的复杂程度。但此处逆向回推法会让人迅速放弃二阶常系数线性递推关系AXNBXN1CXN2FN的求解二阶待求递推关系最高项XN与最低项XN2相差两阶线性左侧是递推关系未知项的线性组合常系数A，B，C均为常数齐次如果FN0；否则，称为非齐次考虑最简单情形AXNBXN10，即，XNXN1，AB这是一个等比数列，其通解为XNRN，公比R，的值由初始条件确定。1此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。对于AXNBXN1CXN20的情形，类比可猜想其通解也应为等比数列，设XNRN，则XN1RN1，XN2RN2，得ARNBRN1CRN20，考虑一般情况，0，R0，得特征方程AR2BRC0。对此方程解的不同情况，递推关系的通解如下方程有二不等实根R1，R2递推关系的通解为XN，NR1N2其中和的值由初始条件确定方程有二相等实根R递推关系的通解为XNN，其中NRN和的值由初始条件确定方程有二共轭虚根R1,2UIV由于算法分析所考虑的数列均为非负数，数列递推关系的通解XNCOSNSINN，其中N，ARCTAN，和的值由初始条件确定2VUUV对于AXNBXN1CXN2FN的情形，它的通解是相应齐次递推关系的通解与该非齐次递推关系的一个特解之和。不像求通解，求特解的无一般方法，常用的方法是尝试与FN同阶的函数。上述求解二阶常系数线性递推关系的方法可推广到N阶常系数线性递推关系。例，解递推关系XN6XN19XN24。特征方程为R26R90，有二相等实根R3，相应齐次递推关系的通解为XNNN3NFN4，同阶的函数同样为常数，设为C，代入得C6C9C4，解得C1递推关系XN6XN19XN24的通解为XNN1N3求解FIBONACCI数列的通项公式特征方程为R2R10，有二不等实根，251R，通解为FN512RN25N251将F00，F11代入得01251251解此二元一次方程组得，5FN51N251N2解法二用递归算法求数列第N项FN/INPUT非负整数N/OUTPUTFIBONACCI数列第N项IFN1RETURNNELSERETURNFN1FN2输入规模非负整数N基本操作有比较和加法，但N1时算法结束，所以基本操作是ELSE分支中的加法是否依赖于输入无须区分最好、最差和平均情况加法次数ANAN1AN21对N0，A0A10这是一个二阶常系数线性非齐次递推关系，其对应齐次递推关系的特征方程为R2R10，与FIBONACCI数列通解相同FN1，同阶的函数同样为常数，设为C，代入得CCC1，解得C1，通解为AN1N251N25将A00，A10代入得101025125解此二元一次方程组得，5AN1105N2105N2关于ANAN1AN21的另一解法AN1AN11AN21，显然这就是FIBANACCI数列的递推关系，而A011F1，A111F2，ANFN11，即AN1，WHY5112N52NN25显然，这是一个指数算法，递归算法的简洁掩盖了它实际的低效解法三用非递归算法求数列第N项FIBN/INPUT非负整数N/OUTPUTFIBONACCI数列第N项F00F11FORI2TONDOFIFI1FI2RETURNFN输入规模非负整数N基本操作循环内只有加法，故加法为基本操作是否依赖于输入无须区分最好、最差和平均情况加法次数ANN1NI2三种算法的比较第二种递归算法不可取如果第一种算法指数运算采用依次相乘的方法，其效率也属于N存在算法使得N次指数运算可以在LOGN时间内完成第三章蛮力法（BRUTEFORCE）和算术问题例，计算，由就是蛮力法的体现。NA次NNA为什么应用蛮力法进行算法设计不像其他算法设计方法只适合于某类问题，很难指出蛮力法不适合于什么问题对于小规模问题，采用蛮力法设计的算法速度可接受，花费大量时间设计高效算法不值蛮力法可作为评价更高效算法的标准31选择排序和冒泡排序1选择排序扫描整个列表选择最小的元素放在第一个位置，扫描余下的元素选择最小的放在第二个位置，依次继续，直至最后一个元素，这恐怕是我们进行排序所想到的第一个算法。例，对89，45，68，90，29，34，17的选择法排序。考虑一般情形，第I趟扫描是寻找第I小的元素，所以前面I1个元素已经排好序，要依次扫描从第I个元素开始的每个元素，这是内循环。经过N1趟扫描后，只余最后一个元素，无需比较，所以，共需N1趟扫描（外循环）完成排序。伪代码如下SELECTIONSORTA1N/INPUT一个可排序元素的数组A1N/OUTPUT以升序排列的数组A1NFORI1TON1DOMINIFORJI1TONDOIFAJ10，所以只能取物品4，这时背包内重量459，物品2已放不进去，所以此时总价值4025啊哈和上面那么麻烦的解法结果一样嘛，何必用上面那么繁的做法呢小心这种聪明做法的陷阱12重量1W价值2W考虑上表情形，虽然物品1的价值/重量比21物品2的价值/重量比，但显然当W2时，放物品2是最优解。虽然此例有些极端，但充分说明贪心技术适用范围在证明贪心技术得到的是最优解的领域，（如允许放入部分物品，则上面的聪明算法正确）背包问题的穷举搜索有时是不得不采取的方法在直接求解太复杂的情况下，可用贪心技术求近似解旅行商问题和背包问题是所谓的“NPHARD”问题的著名例子，对任何NPHARD问题，没有已知的多项式时间算法，而且大多数计算机科学家相信这样的算法不存在，虽然NPP是计算机科学领域最大的猜想。34基本算术算法一词最初仅应用于这类问题，所以，关注算法，关注数的计算是一个很好的起点。1加法十进制数有一个基本性质任意三个一位数的和至多是两位数。事实上，这个性质不仅仅适合于十进制，而且适合于任何进制。特别是对于计算机实现的基础二进制而言，也同样成立。十进制其实与其他进制并无什么特殊之处，只是我们人碰巧有十根手指而已。那么，我们如何表示一个B进制的数N呢我们通常采用如下写法，其中，而BKB01211,0,10KII对0221NBBKK显然，B进制表示数的N有位NBLOGLOGLOG数。由对数的换底公式BABLOGL因此，不同进制表示同一个数的长度只相差一个常数因子。由BALOG“大O表示法”，可以认为任何一个数N的位数可表示为。NO根据上述性质，对任意两个N位数相加，我们需要根据右端对齐这两个数；从右至左依次完成相应位的加法，每次最多是三个一位数相加（可能有低位的进位），而进位也是一位数是由三个一位数相加最多是两位数保证的。由于三个一位数相加可以在固定时间内完成，因此，两个N位数相加的算法的时间复杂度为O（N），并且，结果最多N1位数。并且，由于我们书写N位数的时间复杂度也是O（N），因此，上述加法算法是最优的。注意我们可能常说，在现代的计算机中，不管是32位还是64位机器，加法是基本操作，意味着任何两个数的加法只需一个指令，为什么这里却说时间复杂度是O（N）呢这是因为，第一，现代计算机可以一次处理的只能是不超过32位或64位的数，对于这个范围内的数只需一个指令，但是对于不只这么多的数呢第二，我们可以假想，计算机采用的是232进制或264进制，这样32位数或64位数在假想机上只是个1位数，1位数的加法可以在固定时间内完成。2乘法对于乘法，我们小学所学的是列竖式相乘。这里，我们以两个二进制数的乘法为例，说明该问题的算法复杂度。3除法扫描整个列表选择最小的元素放在第一个位置，扫描余下的元素选择最小的放在第二个位置，依次继续，直至最后一个元素，这恐怕是我们进行排序所想到的第一个算法。35模算术36素性检测37密码学第四章分治法（DEVIDEANDCONQURE）什么问题可以使用分治法解决划分问题可分成若干个彼此独立的规模更小（且最好规模相同）的同类问题解决小问题可解决（直接解决或者进一步分成规模更小的）合并从若干个小问题的解可以得到原始问题的解分治法最常见的情况是每次分成两个规模相同的子问题，但分治法是否一定比蛮力法高效呢41主定理（MASTERTHEOREM）求，蛮力法就是依次相加，共需N1次加法，考虑分治法NIA1A1A2AN/2AN/21ANNIASUMAPQ/INPUT可求和的数组APQ，最初调用为A1N/OUTPUT数组中元素之和IFPQRETURNSUMAPPQP1/21SUMAPQP1/2QELSERETURNAP输入规模数组中元素个数N基本操作基本操作为加法是否依赖于输入只和数组大小有关加法次数ANAN/2ANN/21，A10为计算方便，设N2K，K为非负整数，则AN2AN/212A2K11，逆向回推得，A2K2A2K1122A2K2114A2K238A2K3723A2K32312KA12K1NA12K1N1可见，分治法并没有比蛮力法高效。考虑上述推导AN2AN/21的一般情形ANAAN/BFN，有主定理如下主定理如果FNND，D0NDABDABNLOG对O和记号，有类似的结果。试用求和的例子验证主定理。42归并排序应用分治法进行归并排序的基本思想排整个列表复杂，可以分别排前面一半和后面一半，再将前后排好序的列表合并起来。例，对89，45，68，90，29，34，17进行归并排序。由主定理可知，归并排序的效率需视A和D的值而定。归并排序中AB2，D由合并算法的效率确定。1合并算法合并前列表的前后两半已排好序，而一般的将两个已排好序的列表进行合并的基本思想是，依次比较两列表的对应元素，将小的移入一个新的列表，直至合并完毕，其伪代码如下MERGEB1P,C1Q,A1PQ/INPUT两个已排好序的数组B1P和C1Q/OUTPUT由B和C中元素合并得到的排好序的数组A1PQI1J1K1WHILEIPANDJQDOIFBICJAKBIII1ELSEAKCJJJ1KK1IFIPCOPYCJQTOAKPQELSECOPYBIPTOAKPQ该算法的基本操作是BI与CJ的比较，至多比较N1次，所以其最差情况效率为PQ。2归并排序的效率分析由上分析，PQN，所以其最差情况效率为N，N为待排序数组的规模，即D1，ABD，归并排序的最差情况效率属于NLOGN，归并排序具有比选择排序、冒泡排序更好的时间效率。但归并排序需要额外的数组保存MERGE中间结果，所以空间效率还不如选择和冒泡排序，属于N。3归并排序算法MERGESORTA1N/INPUT可排序的数组A1N/OUTPUT排好序的数组A1NIFN1COPYA1N/2TOB1N/2COPYAN/21NTOC1NN/2MERGESORTB1N/2MERGESORTC1NN/2MERGEB,C,A43快速排序归并排序简单的将列表大小减半达到分治的效果。快速排序则是根据划分元素的值（又称为枢轴）将列表划分成前后两部分，前边的都小于划分元素，后边的都大于划分元素，中间的位置正好留给划分元素，然后对前后部分继续排序，分而治之。关键是枢轴如何选择又如何把枢轴放到它最终该放的位置1划分算法枢轴可以选择列表中任意一个元素，但最简单的是选择列表中第一个元素，那么具体又该如何划分呢如果从第二个开始到最后一个依次和第一个元素相比，小的，则移到第一个元素前面，大的则不必移动，那么小的移到第一个元素前面具体什么位置又用什么数据结构如何具体实现不妨考虑下面的更一般的算法P所有P的元素交换但有可能出现下面两种情况P所有P的元素PP所有P的元素P所有P的元素P所有P的元素此时其实我们已经找到了枢轴P最终的位置PARTITIONALR/INPUT数组A1N的子数组ALR/OUTPUTALR的划分，最初的AL已在枢轴位置S，返回SPALILJR1REPEATREPEATII1UNTILAIP如无检查，I可能无限自增（如果AL是最大元素），所以需设置检查哨如无“”，J可能减到小于LREPEATJJ1UNTILAJPSWAPAIANDAJUNTILIJSWAPAIANDAJ/WHYUNDOLASTSWAPWHENIJSWAPALANDAJ/将枢轴放到它的最终位置RETURNJ2快速排序算法QUICKSORTALR/INPUT数组A1N的子数组ALR，初次调用A1N/OUTPUT排好序的ALRIFLVDOAJ1AJ；JJ1AJ1V输入规模数组中元素个数N基本操作内循环内的操作最频繁，基本操作为比较是否依赖于输入和输入有关，最差情况下J降至0比较次数CWORSTNNIIJ21NI21NI2I1N212NN52深度优先搜索和广度优先搜索回忆前面第一章曾经提到过的图的基本概念及其两种表示形式邻接矩阵和邻接表。对于给定的图，如何系统的遍历图中每一个结点这是在验证图的连通性和无环性、解决图中任意两点间是否存在路径以及最短路径是多少等图论问题时，首先需要处理的问题。深度优先遍历和广度优先遍历是两种基本的常量递减算法，通过每次遍历一个可访问结点，将问题规模减1，来实现对图中所有结点的访问。1深度优先搜索（DEPTHFIRSTSEARCH）算法思想从任意结点出发，访问该结点（即，标记该结点已被访问过，避免重复访问），然后从该结点相邻的未被访问过的结点中任取一个，重复上述步骤直至出现下面两种情形某个结点的相邻结点均被访问过退回到上一个访问的结点，尝试该结点相邻的其它未被访问过的结点无结点可退已经退到了出发点却还要往后退，说明从该结点出发能访问到的结点均已被访问。此时如还有未被访问的结点，说明该图不是连通图，当前只是遍历了它的一个连通子图，还需从未被访问过的任意结点出发进行访问，直至所有结点均被放问基于上述算法思想，可得伪代码如下DFSG/INPUT图GV,E/OUTPUT以访问顺序的标记图的每个结点MARKEACHVERTEXINVWITH0ASAMARKOFBEING“UNVISITED”COUNT0/GLOBALVARIABLEFOREACHVERTEXVINVDOIFVISMARKEDWITH0DFSVDFSV/INPUT图中某个结点V/OUTPUT标记从V出发深度优先搜索到的所有结点的访问顺序COUNTCOUNT1MARKVWITHCOUNTFOREACHVERTEXWINVADJACENTTOVDOIFWISMARKEDWITH0DFSW上述伪代码还不足够具体，并未描述存储图G信息所采用的数据结构，以及算法递归调用所需的栈结构以存储访问的结点，结点入栈的顺序就是标记结点的COUNT。如果图G用邻接矩阵表示，对任一结点，与其相邻的结点均在邻接矩阵的同一行，因此访问完G中的|V|个结点，必然要访问邻接矩阵的每一行，同样，要获知任一结点相邻结点的信息，必然要访问该结点所对应邻接矩阵行的每个元素，因而，算法的效率和邻接矩阵的大小相关，属于|V|2。如果图G用邻接表表示，类似上面的分析，算法的效率和邻接表的大小相关，属于|V|E|。2广度优先搜索（BREATHFIRSTSEARCH）如果说，深度优先搜索是一种“大无畏”搜索的话（该算法从任意结点出发，逐步访问到尽可能远的结点后，再按原路退回进行其它尝试），广度优先搜索则是一种“谨慎”搜索，它严格按照与起始结点距离的递增顺序来访问每一个结点。算法思想从任意结点出发，将该结点入队并访问（即，标记该结点已被访问过，避免重复访问）。然后访问所有与队首结点相邻且未被访问过的结点，并将这些结点入队，队首结点出队，重复上述步骤直至出现下面两种情形队首结点的相邻结点均被访问过无需向队中添加任何结点，队首结点出队即可队空从该结点出发能访问到的结点均已被访问。此时如还有未被访问的结点，说明该图不是连通图，当前只是遍历了它的一个连通子图，还需从未被访问过的任意结点出发进行访问，直至所有结点均被放问基