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

目录TOC\o"1-2"\h\z\u第一章 绪论 31.1算法的概念 31.2算法问题求解基础 61.3重要的问题类型 91.4基本数据结构 11第二章 算法效率分析基础 162.1分析框架 162.2渐进符号和基本效率类型 192.3非递归算法的数学分析 222.4递归算法的数学分析 252.5例：Fibonacci数列※ 27第三章 蛮力法（BruteForce）和算术问题 333.1选择排序和冒泡排序 333.2蛮力字符串匹配※ 353.3穷举搜索（ExhaustiveSearch） 363.4基本算术 403.5模算术 423.6素性检测 423.7密码学 42第四章 分治法（Devide-and-Conqure） 434.1主定理（MasterTheorem） 434.2归并排序 444.3快速排序 464.4大整数乘法※ 494.5Strassen矩阵乘法※ 504.6快速傅里叶变换FFT※ 52第五章 减治法（Decrese-and-Conqure） 585.1插入排序 585.2深度优先搜索和广度优先搜索※ 595.3生成组合对象的算法 635.4二叉搜索（折半查找） 675.5乘法和乘方问题※ 695.6Euclid算法分析※ 71第六章 时空权衡（TimeandSpaceTradeoffs）与动态规划（DynamicProgramming） 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第七章 贪心法（GreedyTechniques） 997.1连续背包问题※ 997.2最小生成树问题（MST，minimumspanningtree） 1027.3单源最短路径问题的Dijkstra算法 1097.4Huffman编码 1127.5集合覆盖 118第八章 线性规划（LinearProgramming） 1198.1线性规划简介 1198.2求解线性规划问题的单纯形算法 1228.3网络流问题 1298.4二部图的匹配问题 1298.5对偶 1298.6零和游戏 130第九章 算法能力的极限 1319.1求算法下界的方法 1319.2问题归约 1329.3P，NP和NP完全问题 1349.4回溯法（Backtracking） 1399.5分支限界法（Branch-and-Bound） 1419.6近似算法（Approximationalgorithms） 144

第一章 绪论1.1算法的概念算法：解决一个问题的无歧义的指令序列，对合法的输入在有限的时间内可得到需要的输出。算法的一些特点：这才叫算法无歧义性（确定性）：算法的每个步骤必须确定无疑这才叫算法有穷性：算法的执行必须有限步终止输入的范围：算法只对这指特定问题的算法满足条件的输入有响应这指特定问题的算法正确性：算法应能解决要求的问题同一算法的不同表示形式：自然语言、伪代码、高级语言同一问题存在的多种算法：设计思想不同，时空性能各异例，求两个正整数m和n的最大公因子的算法算法一 最容易想到的算法——挨个检查Step1 t=min{m,n}Step2 如果m除以t的余数为0，转Step3；否则，转Step4；Step3 如果n除以t的余数为0，返回t的值；否则，转Step4；Step4 t=t–1，转Step2。分析：上述步骤每一步均确定没有歧义，是一个循环结构程序循环执行次数未知，那么它会有限步终止吗？（每次t–1）该算法由自然语言描述该算法正确吗？如何证明？算法二 小学数学中讲述的算法Step1 将m分解质因子；Step2 将n分解质因子；Step3 寻找Step1和Step2得到的两个质因子连乘积的公共部分（注：若m的分解中质因子p出现了x次，n的分解中p出现了y次，作为公共部分，p应出现min{x,y}次）；Step4 计算公共部分的连乘积，并将结果返回。分析：此算法中，如何分解质因子没说明，如何寻找公共部分不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法，至少有待进一步具体说明！考虑如何具体说明：分解质因子需要知道有哪些质数寻找公共部分涉及到质因子连乘积的表示形式算法三 Euclid算法（记录于公元前3世纪Euclid所著的Elements）Euclid(m,n)//Input：两个正整数m和n//Output：m和n的最大公因子whilen≠0dor=mmodn m=n n=rreturnm分析：上述步骤每一步均确定没有歧义，是一个循环结构程序循环执行次数未知，那么它有限步终止吗？（每次n都减小）该算法由伪代码描述：伪代码是自然语言和编程语言的混合该算法正确吗？如何证明？证明：设函数gcd(m,n)就是采用Euclid算法计算最大公因子的函数。则算法的正确性基于两个事实：若m≠0，则gcd(m,0)=mgcd(m,n)=gcd(n,mmodn)第一个事实显然易见。设d=gcd(m,n)且m=kn+t。则存在a，b使得m=ad，n=bd，且a与b互质。mmodn=t=m–kn=ad–kbd=(a–kb)*d。说明d是n和mmodn的公因子，还需说明，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算法问题求解基础算法是求解的具体指令，不是解答。设计和分析算法的典型步骤：理解问题仔细阅读问题描述手工测试几个例子思考特殊情形分析是否已有该类问题的算法确定计算设备的能力现行的绝多数算法都是基于冯·诺依曼机器模型的，即，随机存储模型，它假定指令依次执行，每次执行一个操作，在这样机器上执行的算法称为sequential算法。适合于现在新兴的可同时执行多条操作的计算机的算法，称为并行算法。除非对某些本质上复杂、需处理大量数据或者对时间要求很高的问题，无需担心现在计算机的能力！！！选择精确算法还是近似算法存在某些问题不能精确解决，例如求平方根可精确解决的算法难以接受的慢，例如，TSP问题近似算法可以是某些更为复杂的精确算法的组成部分确定合适的数据结构存在某些算法设计方法固有依赖于描述问题的数据结构。算法设计方法本课程所要解决的主要问题。算法设计方法（或策略）是指：从算法上解决问题的通用方法，可适用于不同领域的各种各样的问题。学习这些方法的原因：有助于为新问题设计算法，授人以鱼不如授人以渔每门学科都对其研究主题进行分类，算法是计算机科学的基础，有助于根据设计思想对算法进行分类描述算法的方法自然语言描述，如前例中算法一、二伪代码描述，如前例中算法三Euclid算法，无统一格式流程图，只适合于描述很简单的算法某种计算机语言写成的程序证明算法的正确性一旦算法描述清楚，就需要证明其正确性，即，它对每一个合法的输入都可以在有限的时间内得出需要的结果。证明算法正确的一个常用方法是：数学归纳法。注意：测试几组输入数据的方法虽然简单，但却不足以说明算法正确！不过却可以说明一个算法不正确！算法分析算法应具有的几个品质：本课程所要解决的主要问题正确性效率：时间效率和空间效率。第二章详述简洁性：无法用数学定义精确描述，最好给人以美感例，前述的求gcd的算法哪个更简单？简单的算法易于理解，易于编程，通常包含较少的bug，一般也更有效率通用性：同样的效率，解决的问题可适用范围当然越广越好，但是有时通用算法难设计且效率差，或者根本无通用算法例，判定两个正整数是否互质的算法就没有求gcd的通用；二次方程求根公式存在的，但没有任意次方程的求根方法算法编码实现注意程序严格准确的实现算法算法到程序的过渡：算法中假设输入都是合法的，程序中需验证程序的正确性验证的实际方式：测试（testing）。学习编程技巧，以提高程序效率最优算法（optimality）：不是算法效率的问题，而是算法解决问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价最少。某些问题的最优算法是存在的，比如，通过比较进行排序的最优算法需要进行nlogn次比较；但某些看上去简单的问题，还未找到最优算法，例如，矩阵乘法。不可判定性(undecidability)：不是说，每个问题均有算法解决（注意，这不同于一个问题没有解，例如，判别式为负的二次方程无实数解）。所幸的是，实际计算中的绝大多数问题还是有解决算法的。1.3重要的问题类型后面的章节将以以下问题展开，讨论不同算法的设计技术与分析方法。排序我们经常遇到排序问题，比如学校学生按学号排序，学号通常被称为key。那么为什么要进行排序？排序使得很多关于列表的问题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法的辅助步骤，比如，在几何算法中。当前，已有很多排序算法，在这些算法当中，有些较好的可将任意n个元素通过大约nlog2n比较完成排序，但是没有哪一个通过关键字比较的排序算法能比nlog2n作的更好！排序算法的两个性质：排序是否稳定（保持输入相等元素的相对次序不变）和是否需要大量辅助空间（inplace排序）。搜索（查找）同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜索（要求元素已排序），等等。由于搜索经常与添加和删除操作联系在一起，所以，需仔细设计数据结构。字符串处理※由于所有程序在计算机看来都是字符串，所以此类算法同计算机语言和编译紧密相关。此类算法中最特殊的一个——字符串匹配——在给定文本中搜索给定单词，在实际中非常有用。图论问题算法中最古老而又吸引人的领域就是图算法。图可以看作是由若干结点和若干个连接其中某些结点的边所构成，其准确定义下一小节给出。图可以为日常很多应用建模，比如，交通和通信网，项目调度，博弈。最基本的图算法包括：图遍历算法（如何遍历网络中所有结点），最小生成树算法（如何铺设最经济的通信网络），最短路径算法（如何确定两城市间的最佳路线），有向图的拓扑排序（如何确定专业课程的学习顺序），等等。有些图论问题非常复杂，以至于最快的计算机也只能解决较小规模的这类问题，比如，旅行商问题（遍历n个城市每个一次的最短线路）和图着色问题（给图的结点着色以使相邻结点颜色不同的最少颜色数），例如，多叉路口交通灯的设计就是一个图着色问题。组合问题更抽象的讲，旅行商问题和图着色问题都是组合问题的例子。组合问题寻求满足某些约束条件或者某些期望性质的组合对象（排列，组合，多重集）。组合问题被认为是计算机科学中最困难的问题，因为：随着问题规模扩大，组合对象的数目急剧扩大没有已知的算法可在可接受的时间内解决大多数此类问题大多数计算机科学家相信不存在可接受时间内解决此类问题的算法，但不能证实和证伪几何问题※几何问题处理点、线、多边形。 应用领域包括计算机图形学，机器人学，X线断层摄影学。典型算法，比如寻找平面内n个点中的最近点对算法。数值问题※涉及到数学问题的求解，比如，解方程或方程组，计算定积分，等等。大多数这类问题只能近似解决，主要一个原因是他们的操作对象是实数，计算机只能够近似表述。1.4基本数据结构线性数据结构两种基本的线性数据结构是数组和链表。数组的特点：每个元素类型相同，占有同样大小的存储空间整个数组连续存储，任意元素可通过下标随机访问单（双、循环）链表的特点：非连续存储，访问某个元素的时间与其在链表中的位置有关无需预留存储空间，插入和删除操作方便数组和链表均可用于实现抽象数据结构——线性表，其基本操作是：搜索、插入、删除。两种特殊的线性表：栈（LIFO）和队列（FIFO）。图图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，自回路），但除非明确说明，我们所讲的图不包含圈。无向图的性质：0≤|E|≤|V|(|V|－1)/2完全图：每对顶点均有边相连，|V|个顶点的完全图记作K|V|稠密图（dense）和稀疏图（sparse）图的表示：算法中最主要的两种表示是邻接矩阵和邻接表。上左图的邻接矩阵和邻接表表示如下：对无向图而言，其邻接矩阵总是对称的。Why？显然，稀疏图用邻接表更节省存储空间。Why？但具体某问题采用何种表示，更加依赖于解决该问题的算法的性质。加权图（weightedgraph）：图中边赋有值，称为权或cost。比如实际应用中，交通图中两城市间的公路距离。邻接矩阵和邻接表均可用于存储加权图。矩阵中的值可表示距离（无边的是为∞），邻接表的每一结点可添加一项表示距离路径（path）：从顶点u到顶点v的路径，是指始于u终于v有边连接的顶点序列（有向图中，要求边的方向均为从u至v方向）。若除起止点外路径中无顶点重复，称简单路径。路径长度指路径中的边数（即，顶点数减1）。连通图（connected）：图中的每对顶点均有路径连接子图（subgraph）：图G’=(V’,E’)称为图G的子图，当且仅当，V’V并且E’E连通子图（connectedcomponent）：如果一个图不是连通的，它将包含若干个连通子图。连通子图指，添加任何结点则不连通的极大子图。下图就不是一个连通图，它有两个连通子图，其顶点集分别是{a,b,c,d,e}和{f,g,h,i}。思考：中国的省际公路网是否是一个连通图？(注意台湾和海南!)环路（cycle）：起止点为同一结点且路径长度为正的简单路径。没有环路的图称为无环图（acyclic）。Hamilton回路：起止点为同一结点，且只经过图中其它结点一次的环路Euler回路：起止点为同一结点，且只经过图中所有边一次的环路树树是一个连通的无环图。森林：不连通的无环图，其每个连通子图是一棵树。 树的性质1：|E|=|V|－1。注意，这是图成为树的必要条件，而不是充分条件。Why?因为图不一定连通，不连通的图却可以有环，仍能满足此条件！树的性质2：任意两结点间均有唯一的简单路径。Why?根树（rootedtrees）：性质2使得选择任一结点为根成为可能。所得树称为根树。一般从上至下依次画出根和各层结点。根树有广泛的应用，常简称为树，下面的树均指根树。所谓双亲、孩子、祖先、子孙、子树、叶子等概念，不再详述。 结点的深度（depth）：从根到该结点的简单路径的长度树的高度（height）：从根到叶子的最长的简单路径的长度。有序树（orderedtrees）：每个结点的所有孩子是有序的。假定树中以从左至右表示顺序。二叉树（binarytrees）是最常用的有序树，从而有左孩子、右孩子、左子树、右子树的概念。一般的有序树可以用“左孩子、右兄弟”的方式表示成二叉树。集合与字典※集合（set）：不同元素组成的一个无序的整体。常用的集合操作：membership、union和intersection。字典：一种数据结构，用于实现对给定集合进行搜索、添加和删除元素这三种操作。集合的表示形式：给定全集U的bitvector表示和列表表示。

第二章 算法效率分析基础算法分析的重点是算法效率的分析，因为它可以量化（不像简洁性和通用性），关注的是时间效率（timeefficiency）和空间效率（spaceefficiency）。2.1分析框架对于给定问题，一个算法的时间效率：指它运行的有多快（runningtime）空间效率：指它需要多大的额外空间（memoryspace）随着计算机技术的革新，越来越大容量的存储器的出现，算法对空间的需要已不再是什么问题，但是时间效率却没有相应的提高，因此，我们关注的重点是时间效率，但分析框架完全适用于空间效率。度量输入规模算法的效率和输入规模n有关，因为几乎所有算法对大的输入运行时间要长一些。例如，对较大的数组排序，两个较高维数的矩阵相乘，等等。关键是n如何确定?例，对一个列表的排序、搜索或者寻找其中最小元素，显然，n即列表中元素的个数；矩阵相乘，n可以是矩阵的维数，也可以是矩阵中元素的个数；而大整数相乘，则n取大整数的位数比取大整数本身更合适。度量运行时间的单位秒、毫秒等时间单位：依赖于特定机器的性能，我们需要的是一种不依赖于外部因素、只决定于算法本身的衡量标准算法中各种操作执行的次数：精确，但过于困难且没有必要算法中基本操作执行的次数：对算法总运行时间贡献最大的、最重要的操作例，对一个列表的排序，位于最内循环中的操作肯定执行次数最大，选择元素的比较操作为基本操作；矩阵相乘，需要对应元素一一相乘并求和，又因为大多数计算机中乘法比加法慢，所以选择乘法为基本操作；而大整数相乘，则宜取每一位的乘法为其基本操作。因为实际运行时间T和基本操作的执行次数C关于输入规模n近似的成一定的比例，即，T(n)≈kC(n)，要分析时间效率，就要建立输入规模n和基本操作执行次数C之间的函数关系C(n)。例，假设C(n)=，当输入规模翻番时，运行时间如何变化？（当n足够大时）注意：实际运行时间和基本操作执行次数所成的比例k对最后的结果没有影响函数C(n)中的常数因子对最后的结果没有影响考虑较大输入规模时，低阶量对最后的结果没有影响为什么分析效率只考虑较大输入规模的情形？输入规模较小时，不同算法之间的效率差异不明显！！！函数的阶（分析效率时的关注重点）nnnn2n!103.3103.3101010103.610106.6106.61010101.3109.3101010101.01010101013101.31010101017101.71010101020102.0101010书上P7有类似表。∵，可见底数不同的对数函数之间只相差一个常数因子，由前讨论，可以忽略，∴今后忽略底数，写作logn。指数函数和阶乘函数增长过快，只适合求解很小的输入规模，今后统称作指数函数。最坏、最好和平均情况有很多算法的性能不仅和输入规模有关，还和特定的输入有关。例，在以数组A[1..n]表示的线性表中顺序搜索某个值K，找到则返回下标值，返回–1表示未找到。SequentialSearch(A[1..n],K)//Input：数组A[1..n]和搜索值K//Output：若有A中元素等于K，返回该元素下标，否则返回–1i=1whilei≤ndo ifK=A[i]returni //基本操作为此处的比较 elsei=i+1return–1最坏情况：所有同规模的输入中，算法运行时间最长的输入最好情况：所有同规模的输入中，算法运行时间最快的输入平均情况：随机输入的运行情况，需对输入做某些假定对上述线性搜索，Cworst(n)=n，Cbest(n)=1。假定，对任意输入，能搜索到的概率为p，且在任一位置找到的可能性相同，则如果p=1，则表示一定能找到，平均比较次数为；如果p=0，则表示一定找不到，也需比较n次。最坏情况：决定算法运行时间的上限，常用最好情况：除极少情况，很难保证算法总处于最好，不常用平均情况：需进行概率分析，运算复杂，但有时很有必要，尤其当平均情况远不像最差情况那么糟的时候。注意：平均情况不是最坏情况和最好情况的平均分摊效率※：有些算法的第一次运行代价很高，但多次运行的代价却比第一次的代价乘以运行次数的值要小的多2.2渐进符号和基本效率类型本课程所讨论函数均为非负函数。O记号：函数t(n)∈O(g(n))如果存在某个正常数c和某个非负整数n0使得对所有n≥n0，t(n)≤cg(n)。例，100n+5≤100n+n=101n≤101n2（对所有n≥5），所以100n+5∈O(n2)，此处，取c=101，n0=5；又，100n+5≤100n+5n=105n（对所有n≥1），100n+5∈O(n)，此处，取c=105，n0=1。试证明，n∈O(n2)，∈O(n2)，0.00001nO(n2)，n+n+1O(n2)。Ω记号：函数t(n)∈Ω(g(n))如果存在某个正常数c和某个非负整数n0使得对所有n≥n0，t(n)≥cg(n)。例，n∈Ω(n2)，因为对所有n≥0，n≥n2，此处c=1，n0=0。试证明，n2∈Ω(n)，∈Ω(n2)，100n+5Ω(n2)。Θ记号：函数t(n)∈Θ(g(n))如果存在正常数c1和c2和某个非负整数n0使得对所有n≥n0，c1g(n)≤t(n)≤c2g(n)。例， （对所有n≥0） （对所有n≥2）所以，取c1=，c2=，n0=2，有∈Θ(n2)。渐进符号的性质性质1 如果t1(n)∈O(g1(n))，t2(n)∈O(g2(n))，则t1(n)+t2(n)∈O(max{g1(n),g2(n)})性质2 如果t1(n)∈Ω(g1(n))，t2(n)∈Ω(g2(n))，则t1(n)+t2(n)∈Ω(max{g1(n),g2(n)})性质3 如果t1(n)∈Θ(g1(n))，t2(n)∈Θ(g2(n))，则t1(n)+t2(n)∈Θ(max{g1(n),g2(n)})性质1的证明：∵t1(n)∈O(g1(n))，∴c1和n1对所有n≥n1，t1(n)≤c1g1(n)∵t2(n)∈O(g2(n))，∴c2和n2对所有n≥n2，t2(n)≤c2g2(n)∴对所有n≥max{n1,n2}，t1(n)+t2(n)≤c1g1(n)+c2g2(n)≤c1max{g1(n),g2(n)}+c2max{g1(n),g2(n)}≤(c1+c2)max{g1(n),g2(n)}∴取c=c1+c2，n0=max{n1,n2}，即，t1(n)+t2(n)∈O(max{g1(n),g2(n)})。 ■试证明另外两个性质。例，某算法判断数组中是否包含相同元素，其思想如下，首先将数组排序，然后比较相邻元素是否相同。假设所用排序算法属于O(n2)，比较相邻元素显然属于O(n)，则该算法属于O(max{n2,n})=O(n2)。使用极限比较函数的阶※0 t(n)的阶小于g(n)ct(n)与g(n)有相同的阶∞t(n)的阶高于g(n)例，，∴∈Θ(n2)，∴比的阶小。基本效率类型即使不考虑常数因子，仍然有无穷多种函数的阶类型。类型名称描述1常数某些算法的最好情况，实际中很少logn对数每次迭代输入规模以常数因子递减的算法n线性需扫描整个输入的算法nlognn-log-n许多分治算法属于此类，如归并排序和快速排序n平方有两重循环的算法，如冒泡排序和选择排序n立方有三重循环的算法，如矩阵乘法2指数产生输入集所有子集的算法n！阶乘产生输入集元素全排列的算法2.3非递归算法的数学分析例1 在n个元素的线性表（以数组A[1..n]表示）中寻找最大元素。MaxElement(A[1..n]) //Input：数值型数组A[1..n] //Output：A中最大元素的值 maxval=A[1] fori=2tondo ifa[i]>maxvalmaxval=A[i] returnmaxval输入规模：数组中元素的个数n基本操作：最频繁执行的操作在循环内，循环内有比较和赋值，但赋值不是每次都做，故比较为基本操作是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况比较次数：C(n)==n–1∈Θ(n)非递归算法效率分析的一般模式：确定描述输入规模的参数识别算法的基本操作检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解建立表示基本操作执行次数的公式得出执行次数的通项公式，或者至少确定其阶例2 检查给定数组中的元素是否彼此不同。UniqueElement(A[1..n]) //Input：数组A[1..n]) //Output：如果所有元素均不相同，返回true；否则，返回false fori=1ton–1do forj=i+1tondo ifA[i]=A[j]returnfalse returntrue输入规模：数组中元素的个数n基本操作：循环内只有比较操作是否依赖于输入：比较的次数不仅与输入规模有关，还和数组中是否有相同元素，以及相同元素在数组中的位置有关，此例我们考虑最差情况比较次数：每次内循环的比较都执行，Cworst(n)===－=－=－=∈Θ(n2)例3 给定两个n×n的矩阵A和B，求C=AB。MatrixMultiplication(A[1..n,1..n],B[1..n,1..n]) //Input：两个n×n的矩阵A和B //Output：矩阵C=AB fori=1tondo forj=1tondo C[i,j]=0 fork=1tondo C[i,j]=C[i,j]+A[i,k]*B[k,j] returnC输入规模：矩阵的阶n基本操作：最内循环有加法和乘法两种操作，两种操作执行次数相同，所以取哪个为基本操作都可以是否依赖于输入：对所有输入都一样，故无须区分最好、最差和平均情况乘法次数：M(n)====n32.4递归算法的数学分析例1 非负整数n的阶乘F(n)=n!=1…(n–1)n，其递归定义如下： 1 n=0F(n)= nF(n–1) n>0由此定义，可得其递归算法如下F(n) //Input：非负整数n //Output：n的阶乘 ifn=0return1 elsereturnF(n–1)*n输入规模：非负整数n基本操作：有比较和乘法，但n=0时算法结束，所以基本操作是else分支中的乘法是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况乘法次数：M(n)=+对n>0这是一个递推公式，要求M(n)的通项公式，可逆向回推，得M(n)=M(n–1)+1=[M(n–2)+1]+1=M(n–2)+2=M(n–3)+3=…=M(n–i)+i=…=M(n–n)+n=M(0)+n，又n=0时，算法直接返回，不进行乘法，即，M(0)=0,∴M(n)=n递归算法效率分析的一般模式：确定描述输入规模的参数识别算法的基本操作检查基本操作的执行次数是否只和输入规模有关，如果还和其他因素有关，则需根据最好、最差和平均情况分别求解建立表示基本操作执行次数的递推公式解递推式，得出执行次数的通项公式，或者至少确定其阶例2 TowerofHanoi问题的递归算法如下Hanoi(n,A,B,C) //Input：要搬运的盘子总数n //Output：塔上盘子的搬运过程 ifn=1Move(n,A,C) else Hanoi(n–1,A,C,B) Move(n,A,C) Hanoi(n–1,B,A,C)输入规模：盘子总数n基本操作：有比较和搬运操作Move，此处去Move，why？是否依赖于输入：输入仅是一整数，无须区分最好、最差和平均情况搬运次数：M(n)=M(n–1)+1+M(n–1) 对n>1又，只有一个盘子（即n=1）时，需Move一次，即，M(1)=1。逆向回推，得M(n)=2M(n–1)+1=2[2M(n–2)+1]+1=4M(n–2)+2+1=4[2M(n–3)+1]+2+1=8M(n–3)+4+2+1=…======这是一个指数算法，并且，由于此问题本身的复杂性，这已经是解决这个问题的最有效方法。另外注意，经常根据递归定义得到的算法看上去非常简洁，但是要小心看上去的简洁掩盖了实际上的低效!2.5例：Fibonacci数列※此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。Fibonacci数列的递推公式为此处可只选讲二阶常系数递推关系的求解，而把两个算法留到讲动态规划时。 0 n=0F(n)= 1 n=1 F(n–1)+F(n–2) n>1解法一 求数列通项公式前面求解递归算法效率时，求得通项公式即可获知算法效率，受此启发，对于递推式给出的数列，如能求得数列的通项公式，则对任意的输入n，求解F(n)的时间仅依赖于通项公式的复杂程度。但此处逆向回推法会让人迅速放弃！二阶常系数线性递推关系ax(n)+bx(n–1)+cx(n–2)=f(n)的求解二阶：待求递推关系最高项x(n)与最低项x(n–2)相差两阶线性：左侧是递推关系未知项的线性组合常系数：a，b，c均为常数齐次：如果f(n)=0；否则，称为非齐次考虑最简单情形ax(n)+bx(n–1)=0，即，x(n)=x(n–1)，这是一个等比数列，其通解为x(n)=αrn，公比r=，α的值由初始条件确定。对于ax(n)+bx(n–1)+cx(n–2)=0的情形，类比可猜想其通解也应为等比数列，设x(n)=δrn，则x(n–1)=δrn–1，x(n–2)=δrn–2，得aδrn+bδrn–1+cδrn–2=0，考虑一般情况，δ≠0，r≠0，得特征方程ar2+br+c=0。对此方程解的不同情况，递推关系的通解如下：方程有二不等实根r1，r2：递推关系的通解为x(n)=α+β，其中α和β的值由初始条件确定方程有二相等实根r：递推关系的通解为x(n)=α+βn，其中α和β的值由初始条件确定方程有二共轭虚根r1,2=u±iv：由于算法分析所考虑的数列均为非负数，数列递推关系的通解x(n)=(αcosnθ+βsinnθ)，其中γ=，θ=arctan，α和β的值由初始条件确定对于ax(n)+bx(n–1)+cx(n–2)=f(n)的情形，它的通解是相应齐次递推关系的通解与该非齐次递推关系的一个特解之和。不像求通解，求特解的无一般方法，常用的方法是尝试与f(n)同阶的函数。上述求解二阶常系数线性递推关系的方法可推广到n阶常系数线性递推关系。例，解递推关系x(n)–6x(n–1)+9x(n–2)=4。特征方程为r2–6r+9=0，有二相等实根r=3，相应齐次递推关系的通解为x(n)=α+βnf(n)=4，同阶的函数同样为常数，设为c，代入得c–6c+9c=4，解得c=1递推关系x(n)–6x(n–1)+9x(n–2)=4的通解为x(n)=α+βn+1求解Fibonacci数列的通项公式特征方程为r2–r–1=0，有二不等实根，，通解为F(n)=α+β将F(0)=0，F(1)=1代入得 α + β =0 α + β =1解此二元一次方程组得α=，β=∴F(n)=–解法二 用递归算法求数列第n项F(n) //Input：非负整数n //Output：Fibonacci数列第n项 ifn≤1returnn elsereturnF(n–1)+F(n–2)输入规模：非负整数n基本操作：有比较和加法，但n≤1时算法结束，所以基本操作是else分支中的加法是否依赖于输入：无须区分最好、最差和平均情况加法次数：A(n)=A(n–1)+A(n–2)+1对n>0，A(0)=A(1)=0这是一个二阶常系数线性非齐次递推关系，其对应齐次递推关系的特征方程为r2–r–1=0，与Fibonacci数列通解相同f(n)=1，同阶的函数同样为常数，设为c，代入得c–c–c=1，解得c=–1，通解为A(n)=α+β–1将A(0)=0，A(1)=0代入得 α + β –1=0 α + β –1=0解此二元一次方程组得α=，β=，∴A(n)=+–1关于A(n)=A(n–1)+A(n–2)+1的另一解法：A(n)+1=[A(n–1)+1]+[A(n–2)+1]，显然这就是Fibanacci数列的递推关系，而A(0)+1=1=F(1)，A(1)+1=1=F(2)，∴A(n)=F(n+1)–1，即A(n)=––1∈Θ()，why？显然，这是一个指数算法，递归算法的简洁掩盖了它实际的低效!解法三 用非递归算法求数列第n项Fib(n) //Input：非负整数n //Output：Fibonacci数列第n项 F[0]=0;F[1]=1fori=2tondo F[i]=F[i–1]+F[i–2] returnF[n]输入规模：非负整数n基本操作：循环内只有加法，故加法为基本操作是否依赖于输入：无须区分最好、最差和平均情况加法次数：A(n)==n–1∈Θ(n)三种算法的比较：第二种递归算法不可取如果第一种算法指数运算采用依次相乘的方法，其效率也属于Θ(n)存在算法使得n次指数运算可以在Θ(logn)时间内完成

第三章 蛮力法（BruteForce）和算术问题例，计算，由就是蛮力法的体现。为什么应用蛮力法进行算法设计？不像其他算法设计方法只适合于某类问题，很难指出蛮力法不适合于什么问题对于小规模问题，采用蛮力法设计的算法速度可接受，花费大量时间设计高效算法不值蛮力法可作为评价更高效算法的标准3.1选择排序和冒泡排序选择排序扫描整个列表选择最小的元素放在第一个位置，扫描余下的元素选择最小的放在第二个位置，依次继续，直至最后一个元素，这恐怕是我们进行排序所想到的第一个算法。例，对89，45，68，90，29，34，17的选择法排序。考虑一般情形，第i趟扫描是寻找第i小的元素，所以前面i–1个元素已经排好序，要依次扫描从第i个元素开始的每个元素，这是内循环。经过n–1趟扫描后，只余最后一个元素，无需比较，所以，共需n–1趟扫描（外循环）完成排序。伪代码如下SelectionSort(A[1..n])//Input：一个可排序元素的数组A[1..n]//Output：以升序排列的数组A[1..n]fori=1ton–1do min=i forj=i+1tondo ifA[j]<A[min]min=j swapA[i]andA[min]输入规模：数组中元素个数n基本操作：内循环内的操作最频繁，基本操作为比较是否依赖于输入：只和数组大小有关比较次数：C(n)===–=－=－=∈Θ(n2)交换次数：交换位于外循环，所以进行次数S(n)=n–1∈Θ(n)冒泡排序基于事实：排好序的列表必遵循相邻元素“前小后大”原则从第一个元素开始依次扫描整个列表比较相邻元素，如果不是“前小后大”则交换，则第一趟扫描后，没有一个元素会在最大元素后面，即，最大元素在最后的位置了。例，对89，45，68，90，29，34，17的冒泡法排序。考虑一般情形，第i趟扫描是要将第i大的元素放在它该在的位置，而最大到第i–1大的元素已排在它们该在的倒数第一到倒数第i–1的位置。所以待排序的元素从第1个元素开始到倒数第i个元素，这是内循环的起止区间。经过n–1趟扫描后，只余第一个元素，无需比较，所以，共需n–1趟扫描（外循环）完成排序。伪代码如下BubbleSort(A[1..n])//Input：一个可排序元素的数组A[1..n]//Output：以升序排列的数组A[1..n]fori=1ton–1do forj=1ton–ido ifA[j]<A[j+1]swapA[j]andA[j+1] 输入规模：数组中元素个数n基本操作：内循环内的操作最频繁，基本操作为比较是否依赖于输入：只和数组大小有关比较次数：C(n)====∈Θ(n2)交换次数：交换位于内循环，最差情况下每次都要交换，则进行次数Sworst(n)=C(n)=∈Θ(n2)3.2蛮力字符串匹配※在给定的文章中搜索给定的关键词，这是文献检索常做的事情，这其实就是在给定文本中进行模式字符串匹配的问题。例，在文本“nobodynoticedhim”中搜索“not”。对此问题的最直接想法是：将模式字符串与文本第一个字符对齐后，一一比较相应字符，成功匹配则返回当前模式字符串所对应文本的第一个字符位置；否则，将模式字符串右移一个字符，继续一一比较，直到成功匹配或者剩下文本已没有模式字符串长。伪代码如下BruteForceStringMatch(T[1..n],P[1..m])//Input：表示文本的字符数组T和表示模式字符串的字符数组P//Output：成功匹配返回第一个匹配位置；否则返回–1fori=1ton–m+1do j=1whilej≤mandP[j]=T[i+j–1]do j=j+1 ifj=mreturnireturn–1输入规模：文本长度n和模式字符串基本操作：基本操作为比较P[j]=T[i+j–1]是否依赖于输入：比较的次数不仅与输入有关，还和对应比较元素P[j]与T[i+j–1]是否相等有关，此例我们考虑最差情况比较次数：Cworst(n)===(n–m+1)m∈Θ(nm)试举例说明，最差情况下确实需要(n–m+1)m次比较！3.3穷举搜索（ExhaustiveSearch）许多重要的问题要求在一个随输入规模指数阶（或更快）的范围内寻找满足某些性质的元素，这些问题通常涉及排列、组合、幂集等组合对象，并且很多此类问题都是寻求最优解的优化问题。穷举搜索是解决组合问题的一种蛮力法，它一一枚举每个组合对象，然后从满足要求性质的元素中选择最优解。本节在假设已知产生组合对象的算法的前提下，讨论旅行商问题和背包问题。旅行商问题（TravelingSalesmanProblem，TSP)找到访问n个城市每个正好一次后回到出发点的最短路线。如果用加权图为n个城市间的道路建模，则该问题即寻找图中最短的Hamilton回路。例，对上述加权图，任意两结点间均有边，故对四个顶点的任一排列（如cadb），可对应一条Hamilton回路c→a→d→b→c，所以共有Hamilton回路4！条，但因为任意结点为出发点，回路并无实质不同，所以有4！/4=3！=6条Hamilton回路，如下：a→b→c→d→a 路径长=2+8+1+7=18a→b→d→c→a 路径长=2+3+1+5=11 最优a→c→b→d→a 路径长=5+8+3+7=23a→c→d→b→a 路径长=5+1+3+2=11 最优a→d→b→c→a 路径长=7+3+8+5=23a→d→c→b→a 路径长=7+1+8+2=18经观察可知，这六条路线实质上只是三条，另三条只是方向反过来而已，所以经改进后，Hamilton回路数仅3！/2条。推广到一般情形，n个结点彼此相通的图中，Himilton回路数为(n–1)!/2条。显然，这是一个指数算法，n稍微大一些，待考察的Hamilton回路就大到难以计算的地步了，这还要基于一个前提，即，产生全排列的时间与全排列个数线性相关。背包问题（KnapsackProblem）将重量、价值不完全相同的n件物品放在一个承重为L的背包中，使得背包中物品价值总和最大。例，有四件物品重量、价值如下，承重L=10。1234重量7345价值42124025笨算法：穷举搜索四件物品的任一子集，将子集内物品的重量和同承重L相比，再对合适的子集比较价值的大小子集总重总价值{}00{1}742{2}312{3}440{4}525{1,2}1036{1,3}11放不下{1,4}12放不下{2,3}752{2,4}837{3,4}965{1,2,3}14放不下{1,2,4}15放不下{1,3,4}16放不下{2,3,4}12放不下{1,2,3,4}19放不下“聪明”的算法（后面将介绍的贪心技术）：优先放入价值/重量比高的物品。首先计算四件物品的价值/重量比，得1234重量7345价值42124025价值/重量比64105所以先放入物品3，虽然接下来物品1的价值/重量比最大，但是物品1、3的重量和=7+4=11>10，所以只能取物品4，这时背包内重量=4+5=9，物品2已放不进去，所以此时总价值=40+25！啊哈！和上面那么麻烦的解法结果一样嘛，何必用上面那么繁的做法呢？小心这种聪明做法的陷阱：12重量1W价值2W考虑上表情形，虽然物品1的价值/重量比=2>1=物品2的价值/重量比，但显然当W>2时，放物品2是最优解。虽然此例有些极端，但充分说明贪心技术适用范围：在证明贪心技术得到的是最优解的领域，（如允许放入部分物品，则上面的聪明算法正确）背包问题的穷举搜索有时是不得不采取的方法在直接求解太复杂的情况下，可用贪心技术求近似解旅行商问题和背包问题是所谓的“NP-hard”问题的著名例子，对任何NP-hard问题，没有已知的多项式时间算法，而且大多数计算机科学家相信这样的算法不存在，虽然NPP是计算机科学领域最大的猜想。3.4基本算术算法一词最初仅应用于这类问题，所以，关注算法，关注数的计算是一个很好的起点。加法十进制数有一个基本性质：任意三个一位数的和至多是两位数。事实上，这个性质不仅仅适合于十进制，而且适合于任何进制。特别是对于计算机实现的基础——二进制——而言，也同样成立。十进制其实与其他进制并无什么特殊之处，只是我们人碰巧有十根手指而已。那么，我们如何表示一个b进制的数N呢？我们通常采用如下写法：，其中，，而显然，b进制表示数的N有位数。由对数的换底公式因此，不同进制表示同一个数的长度只相差一个常数因子。由“大O表示法”，可以认为任何一个数N的位数可表示为。根据上述性质，对任意两个n位数相加，我们需要：根据右端对齐这两个数；从右至左依次完成相应位的加法，每次最多是三个一位数相加（可能有低位的进位），而进位也是一位数是由三个一位数相加最多是两位数保证的。由于三个一位数相加可以在固定时间内完成，因此，两个n位数相加的算法的时间复杂度为O（n），并且，结果最多n+1位数。并且，由于我们书写n位数的时间复杂度也是O（n），因此，上述加法算法是最优的。注意：我们可能常说，在现代的计算机中，不管是32位还是64位机器，加法是基本操作，意味着任何两个数的加法只需一个指令，为什么这里却说时间复杂度是O（n）呢？这是因为，第一，现代计算机可以一次处理的只能是不超过32位或64位的数，对于这个范围内的数只需一个指令，但是对于不只这么多的数呢？第二，我们可以假想，计算机采用的是232进制或264进制，这样32位数或64位数在假想机上只是个1位数，1位数的加法可以在固定时间内完成。乘法对于乘法，我们小学所学的是列竖式相乘。这里，我们以两个二进制数的乘法为例，说明该问题的算法复杂度。除法扫描整个列表选择最小的元素放在第一个位置，扫描余下的元素选择最小的放在第二个位置，依次继续，直至最后一个元素，这恐怕是我们进行排序所想到的第一个算法。3.5模算术3.6素性检测3.7密码学

第四章 分治法（Devide-and-Conqure）什么问题可以使用分治法解决？划分：问题可分成若干个彼此独立的规模更小（且最好规模相同）的同类问题解决：小问题可解决（直接解决或者进一步分成规模更小的）合并：从若干个小问题的解可以得到原始问题的解分治法最常见的情况是每次分成两个规模相同的子问题，但分治法是否一定比蛮力法高效呢？4.1主定理（MasterTheorem）求，蛮力法就是依次相加，共需n–1次加法，考虑分治法：=(a1+a2+…+a└n/2┘)+(a└n/2┘+1+…+an)Sum(A[p..q])//Input：可求和的数组A[p..q]，最初调用为A[1..n]//Output：数组中元素之和ifp≠qreturnSum(A[p..p+└(q–p+1)/2┘–1])+Sum(A[p+└(q–p+1)/2┘..q]) elsereturnA[p]输入规模：数组中元素个数n基本操作：基本操作为加法是否依赖于输入：只和数组大小有关加法次数：A(n)=A(└n/2┘)+A(n–└n/2┘)+1，A(1)=0为计算方便，设n=2k，k为非负整数，则A(n)=2A(n/2)+1=2A(2k–1)+1，逆向回推得，A(2k)=2A(2k–1)+1=2[2A(2k–2)+1]+1=4A(2k–2)+3=8A(2k–3)+7=23A(2k–3)+23–1=2kA(1)+2k–1=nA(1)+2k–1=n可见，分治法并没有比蛮力法高效。考虑上述推导A(n)=2A(n/2)+1的一般情形A(n)=aA(n/b)+f(n)，有主定理如下主定理 如果f(n)∈Θ(nd)，d≥0 Θ(nd) a<bdA(n)∈ Θ(ndlogn) a=bd Θ() a>bd对O和Ω记号，有类似的结果。试用求和的例子验证主定理。4.2归并排序应用分治法进行归并排序的基本思想：排整个列表复杂，可以分别排前面一半和后面一半，再将前后排好序的列表合并起来。例，对89，45，68，90，29，34，17进行归并排序。由主定理可知，归并排序的效率需视a和d的值而定。归并排序中a=b=2，d由合并算法的效率确定。合并算法合并前列表的前后两半已排好序，而一般的将两个已排好序的列表进行合并的基本思想是，依次比较两列表的对应元素，将小的移入一个新的列表，直至合并完毕，其伪代码如下Merge(B[1..p],C[1..q],A[1..p+q])//Input：两个已排好序的数组B[1..p]和C[1..q]//Output：由B和C中元素合并得到的排好序的数组A[1..p+q]i=1;j=1;k=1whilei≤pandj≤qdo ifB[i]≤C[j] A[k]=B[i];i=i+1 else A[k]=C[j];j=j+1 k=k+1ifi>p copyC[j..q]toA[k..p+q]else copyB[i..p]toA[k..p+q]该算法的基本操作是B[i]与C[j]的比较，至多比较n–1次，所以其最差情况效率为Θ(p+q)。归并排序的效率分析由上分析，p+q=n，所以其最差情况效率为Θ(n)，n为待排序数组的规模，即d=1，∴a=bd，归并排序的最差情况效率属于Θ(nlogn)，归并排序具有比选择排序、冒泡排序更好的时间效率。但归并排序需要额外的数组保存Merge中间结果，所以空间效率还不如选择和冒泡排序，属于Θ(n)。归并排序算法MergeSort(A[1..n])//Input：可排序的数组A[1..n]//Output：排好序的数组A[1..n]ifn>1 copyA[1..└n/2┘]toB[1..└n/2┘] copyA[└n/2┘+1..n]toC[1..n–└n/2┘] MergeSort(B[1..└n/2┘]) MergeSort(C[1..n–└n/2┘]) Merge(B,C,A)4.3快速排序归并排序简单的将列表大小减半达到分治的效果。快速排序则是根据划分元素的值（又称为枢轴）将列表划分成前后两部分，前边的都小于划分元素，后边的都大于划分元素，中间的位置正好留给划分元素，然后对前后部分继续排序，分而治之。关键是枢轴如何选择？又如何把枢轴放到它最终该放的位置？划分算法枢轴可以选择列表中任意一个元素，但最简单的是选择列表中第一个元素，那么具体又该如何划分呢？如果从第二个开始到最后一个依次和第一个元素相比，小的，则移到第一个元素前面，大的则不必移动，那么小的移到第一个元素前面具体什么位置？又用什么数据结构如何具体实现？不妨考虑下面的更一般的算法：但有可能出现下面两种情况此时其实我们已经找到了枢轴p最终的位置！Partition(A[l..r])//Input：数组A[1..n]的子数组A[l..r]//Output：A[l..r]的划分，最初的A[l]已在枢轴位置s，返回sp=A[l]如无检查，i可能无限自增（如果A[l]是最大元素），所以需设置检查哨i=l;j=r+1如无检查，i可能无限自增（如果A[l]是最大元素），所以需设置检查哨repeat如无“=”，j可能减到小于l repeati=i+1如无“=”，j可能减到小于l repeatj=j–1untilA[j]≤p swapA[i]andA[j]untili≥jswapA[i]andA[j] //why？undolastswapwheni≥jswapA[l]andA[j] //将枢轴放到它的最终位置returnj快速排序算法QuickSort(A[l..r]) //Input：数组A[1..n]的子数组A[l..r]，初次调用A[1..n] //Output：排好序的A[l..r] ifl<r s=Partition(A[l..r]) QuickSort(A[l..s–1]) QuickSort(A[s+1..r])例，对89，45，68，90，29，34，17进行快速排序。快速排序的效率分析快速排序的效率C(n)=C(s–1)+C(n–s)+P(n)，其中P(n)为划分算法的效率，而划分算法基本操作是每个元素同枢轴的比较，所以从第二个到第n个共需比较n或n+1次（why？），属于Θ(n)。为推导C(n)，先考虑一种特殊情况，即，每次划分正好将列表分成规模相同的两部分，则，C(n)=2C(n/2)+Θ(n)，由归并排序的分析可知，快速排序在这种特殊情况下效率属于Θ(nlogn)，而这种特殊情况其实是最好情况。考虑已按升序排好的列表，每次划分返回的位置就是要排序的第一个元素，所以此时C(n)=C(0)+C(n–1)+n+1，而C(0)=0，C(1)=0，所以得C(n)=C(n–1)+n+1，逆向回推得C(n)=(n+1)+n+(n–1)+…+3=，显然此时是最差情况。因此快速排序是否值得应用就得看它的平均情况了。Cavg(n)==∴用n–1代换，得求二者之差，得两边同除以n(n+1)，得∴，由高数知识，∴Cavg(n)≈2(n+1)ln(n+1)∈Θ(nlogn)。借助更加复杂的数学分析，快速排序的常数因子比同类的Θ(nlogn)排序算法要小，这也是它被称为“快速”的原因。仅交换时需额外空间，空间效率和选择和冒泡排序一样。4.4大整数乘法※考虑两个n位数a和b的乘法，小学算术通过竖式计算，需要进行n2次1位乘法，以及次加法。因为对大多数机器而言，1位乘法比1位加法要费时的多，所以忽略1位加法运算，以1位乘法为基本操作，则两个n位数的乘法的蛮力法效率为。基本的分治策略考虑将n位整数分成两个n/2位的部分，即令a=a1*10n/2+a0，b=b1*10n/2+b0，则c=a*b=(a1*b1)*10n+(a1*b0+a0*b1)*10n/2+a0*b0其中乘10的幂通过移位补零即可，不计入乘法运算次数。所以按此进行，1位乘法次数M(n)=4M(n/2)，M(1)=1，为计算方便，设n=2k，则M(n)=4M(n/2)=16M(n/4)=…=4kM(n/2k)=4k=n改进的分治策略c =a*b=(a1*b1)*10n+[(a0+a1)*(b0+b1)–(a1*b1+a0*b0)]*10n/2+a0*b0∴M(n)=3M(n/2)=9M(n/4)=…=3kM(n/2k)=3k==≈4.5Strassen矩阵乘法※前已分析蛮力法求两个n*n的矩阵A和B乘积的效率为。基本的分治策略C==*=A*B即，将矩阵A、B分成四个(n/2)*(n/2)的矩阵相乘。如果 C00=A00*B00+A01*B10C01=A00*B01+A01*B11C10=A10*B00+A11*B10C11=A10*B01+A11*B11为计算方便，设n=2k，则乘法次数M(n)=8M(n/2)=64M(n/4)=…=8kM(n/2k)=8k=n改进的分治策略M1=(A00+A11)*(B00+B11)M2=(A10+A11)*B00M3=A00*(B01–B11)M4=A11*(B10–B00)M5=(A00+A01)*B11M6=(A10–A00)*(B00+B01)M7=(A01–A11)*(B10+B11)=∴乘法次数M(n)=7M(n/2)=49M(n/4)=…=7kM(n/2k)=7k==≈。但要完成这样的矩阵乘法，还需18次n/2阶的矩阵加法，加法次数A(n)=7A(n/2)+18*(n/2)2，由主定理，A(n)∈。这进一步确保Strassen算法的效率为，好于蛮力法的。在Strassen发现此算法之后，又有很多新的算法不断降低n的幂指数，但这些算法对矩阵进行了更为复杂的分块计算再合并的分治策略，以至于具有很大的常数因子，使得它们的理论意义大于实际价值。而通过分成两块进行求解已有Hopcroft等人证明7次n/2阶矩阵乘法已不可再少，即，分成两块进行矩阵求解的算法已是最佳。4.6快速傅里叶变换FFT※前面我们介绍了运用分治法实现的高效排序方法、整数乘法和矩阵乘法，本小节我们来看多项式的乘法。多项式乘法在数字信号处理中有非常重要的作用。信号，是时间的函数，比如它可能刻画的是人说话的语音。为了提取信号的信息，我们需要通过采样将信号数字化，然后将之输入系统，由系统处理后做出某种响应。在数字信号处理中，一类很重要的系统是线性时不变系统，线性是指对多个信号之和的响应等于各个信号响应之和，时不变是指将信号延时间轴的移动t单位则响应也相应移动t单位。假设信号为a（t），对0时刻单位信号的响应函数为b（t），则在T时刻对信号a（t）的响应c（T）是根据0到T–1时刻的a（t）的采样计算得到的，可以表示为这正是要运用FFT的地方！两个n–1次多项式的乘积是一个2n–2次多项式，例如一般的，如果，，他们的乘积的系数应满足 （对i≥n，取和为0）可见，计算的时间效率为O（k），要计算所有2n–1个系数的时间效率为O（n2）。那么，我们可以算的比这更快吗？快速傅里叶变换正是用分治法解决此问题的高效算法，由于它的重要性，它已经对数字信号处理产生了革命性的影响。多项式的值表示要理解FFT，我们首先需要知道多项式的一个重要性质：任何一个n–