【教学课件】第2章递归与分治.ppt

《【教学课件】第2章递归与分治.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章递归与分治.ppt（122页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 2005第2章 递归与分治策略最通用的算法设计技术最通用的算法设计技术学习要点学习要点:o理解递归的概念。理解递归的概念。o掌握设计有效算法的分治策略。掌握设计有效算法的分治策略。o通过典型的范例学习分治策略设计通过典型的范例学习分治策略设计技巧。技巧。1算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念例例1:阶乘函数阶乘函数 阶乘函数可递归地定义为：阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程注意：注意：(1)边界条件与递归方程是递归函数的二个要素，递归函数只边界条件与递归方程是递归函数的二个要素，递归函数只有具备

2、了这两个要素，才能在有限次计算后得出结果。有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：非递归定义：2算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例2:Fibonacci数列数列n问题引入问题引入n裴波那契（裴波那契（Fibonaccileonardo，约，约1170-1250）是意大）是意大利著名数学家在他的著作算盘书中许多有趣的问利著名数学家在他的著作算盘书中许多有趣的问题，最富成功的问题是著名的题，最富成功的问题是著名的“兔子繁殖问题兔子繁殖问题”：如如果每对兔子每月繁殖一对子兔，而子兔在出生后第

3、二个果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？n问题分析问题分析月份月份初生初生成熟成熟总数总数110120113112412352356358758133算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|数列的特点数列的特点n（1）数列的增长速度）数列的增长速度n（2）自然科学中的若干实例）自然科学中的若干实例n（3）构造一个新数列）构造一个新数列4算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机

4、科学学院 刘芳|定义：定义：2.1 递归的概念5算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念如何求解？如何求解？n解法解法1：0(0.618n)int fibonacci(int n)if(n=0)|(n=1)return n;return fibonacci(n-1)+fibonacci(n-2);n解法解法2：0(n)n解法解法3：0(logn)6算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|思考：思考：n楼梯问题楼梯问题n有一楼梯共有有一楼梯共有n阶，上

5、楼可以一步上一阶，也可以一步阶，上楼可以一步上一阶，也可以一步上两阶。上两阶。n编一个程序，计算共有多少种不同的走法？编一个程序，计算共有多少种不同的走法？7算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 例例3Ackerman函数函数 当一个函数及它的一个变量是由函数自身定义时，称这个当一个函数及它的一个变量是由函数自身定义时，称这个函数是函数是双递归函数双递归函数。Ackerman函数函数A(n,m)定义如下定义如下：2.1 递归的概念8算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的

6、概念|Ackerman函数函数nA(n,0)n+2nA(n,1)2nnA(n,2)2n。nnA(n,4)的增长速度非常快，以至于没有适当的数的增长速度非常快，以至于没有适当的数学式子来表示这一函数。学式子来表示这一函数。9算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例4排列问题排列问题n设计一个递归算法生成设计一个递归算法生成n个元素个元素r1,r2,rn的全的全排列。排列。n设设R=r1,r2,rn是要进行排列的是要进行排列的n个元素，个元素，Ri=R-ri。n集合集合X中元素的全排列记为中元素的全排列记为perm(X)

7、，(ri)perm(X)表示在全排列表示在全排列perm(X)的每一个排列前加上前缀得的每一个排列前加上前缀得到的排列。到的排列。10算法设计与分析算法设计与分析1时，时，perm(R)由由:(r1)perm(R1)(r2)perm(R2)(rn)perm(Rn)n构成。构成。|参考算法：参考算法：11算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例5整数划分问题整数划分问题n将一个正整数将一个正整数n表示成形如下式的一系列正整数的表示成形如下式的一系列正整数的和，称为和，称为n的一个划分。的一个划分。n形如：形如：nn1n

8、2nk其中：其中：(ni1，i1,2,k，k1)且且nn1n2nk112算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念n例如：整数例如：整数6的分划数有的分划数有11种种:n6；n5+1；n4+2，4+1+1；n3+3，3+2+1，3+1+1+1；n2+2+2，2+2+1+1，2+1+1+1+1；n1+1+1+1+1+1;13算法设计与分析算法设计与分析m1;n正整数正整数n的最大加数的最大加数n1不大于不大于m的划分的划分由由n1=m的划分的划分和和n1m-1的划分的划分组成。组成。14算法设计与分析算法设计与分析递归与分治策

9、略递归与分治策略 四川师范大学 计算机科学学院 刘芳 而：正整数而：正整数n n的划分数的划分数p(n)=q(n,n)。2.1 递归的概念|因此：因此：nq(n,m)的递归定义如下的递归定义如下15算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例6Hanoi塔问题塔问题n问题描述：问题描述：16算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题分析问题分析：2.1 递归的概念？A B C A B CHanoi(n ,A ,B ,C )圆盘数圆盘数 源柱源柱 辅助柱辅助柱 目标柱

10、目标柱17算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 =+A B CHanoi(n-1,A,C,B)A B CHanoi(n-1,B,A,C)A B CMove(n,A,C)2.1 递归的概念18算法设计与分析算法设计与分析 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);|递归函数的运行轨迹递归函数的运行轨迹2.1 递归的概念19算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B

11、,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束20算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分析：分析：n规模为规模为n的的Hanoi(n)问题，可以分解为问题，可以分解为2

12、个规模为个规模为n-1的的Hanoi(n-1)问题和一个问题和一个Move操作。操作。n所以，所以，n个盘子的移动次数为个盘子的移动次数为2.1 递归的概念若若n=64，则移动次数为，则移动次数为264-1264118,446,744,073,709,551,61521算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|264118,446,744,073,709,551,615是个什么概念？是个什么概念？n实例实例1：n假设每秒钟移动一次，一年约假设每秒钟移动一次，一年约31556926秒，秒，n计算表明：移动计算表明：移动64个盘子需要个盘子需要5

13、800多亿年。多亿年。n实例实例2：n国王的麦子问题国王的麦子问题22算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|广义广义hanoi问题问题n问题描述问题描述n算法分析算法分析？Hanoi(n ,A ,B ,C ,D)圆盘数圆盘数 源柱源柱 辅助柱辅助柱 目标柱目标柱 A B C D A B C D2.1 递归的概念23算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|递归的优点和缺点递归的优点和缺点n优点：优点：n结构清晰，可读性强，而且容易用数学归纳法来证明算结构清晰，可读性强

14、，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方法的正确性，因此它为设计算法、调试程序带来很大方便。便。n缺点：缺点：n递归算法的运行效率较低，无论是耗费的计算时间还是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。占用的存储空间都比非递归算法要多。24算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难2.1 递归的概念25算

15、法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|消除递归的方法消除递归的方法n采用一个用户定义的栈来模拟系统的递归调用工作栈。该采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。由编译器做的事情，优化效果不明显。n用递推来实现递归函数。用递推来实现递归函数。n通过变换能将一些递归转化为尾递归，从而迭代求出结果。通过变换能将一些递归转化为尾递归，从而迭代求出结果。|注意：注意：n后两种方法在时空复杂度

16、上均有较大改善，但其适用范围后两种方法在时空复杂度上均有较大改善，但其适用范围有限。有限。26算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 分治法的设计思想是分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法2.2 分治法的基本思想27算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分治法所能解决的问题一

17、般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解该问题的规模缩小到一定的程度就可以容易地解决；决；n该问题可以分解为若干个规模较小的相同问题，该问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，即子问题之间不包且各个子问题是相互独立的，即子问题之间不包含公共的子问题。含公共的子问题。n利用该问题分解出的子问题的解可以合并为该问利用该问题分解出的子问题的解可以合并为该问题的解；题的解；28算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法（分治法（

18、Divide and Conquer）的基本思想）的基本思想:n分解分解(Divide)：n将一个规模为将一个规模为n的问题，的问题，分解分解为为k个规模较小的子问题，个规模较小的子问题，这些子问题互相独立且与原问题形式相同。这些子问题互相独立且与原问题形式相同。n求解求解(Conquer):n若子问题规模较小而容易被解决则直接解，否则若子问题规模较小而容易被解决则直接解，否则递归递归地地解这些子问题。解这些子问题。n合并合并(Merge)：n将各个子问题的解将各个子问题的解合并合并得到原问题的解。得到原问题的解。29算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算

19、机科学学院 刘芳 2.2 分治法的基本思想|分治法的分治法的设计模式设计模式divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题解决小规模的问题divide P into smaller subinstances P1,P2,.,Pk；/分解问题分解问题for(i=1;i=k;i+)/递归的解各子问题递归的解各子问题 yi=divide-and-conquer(Pi);return merge(y1,.,yk);/将各子问题的解合将各子问题的解合并并/为原问题的解为原问题的解30算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学

20、 计算机科学学院 刘芳 2.2 分治法的基本思想|启发式规则：启发式规则：n平衡子问题：平衡子问题：n在用分治法设计算法时，最好使子问题的规模大致相同。在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的也就是将一个问题划分成大小相等的k个子问题（通常个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种），这种使子问题规模大致相等的做法是出自一种平衡（平衡（Balancing）子问题）子问题的思想，它几乎总是比子问的思想，它几乎总是比子问题规模不等的做法要好。题规模不等的做法要好。n独立子问题：独立子问题：n各子问题之间相互独立，这涉及到分治法的效率，如

21、果各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子各子问题不是独立的，则分治法需要重复地解公共的子问题。问题。31算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法的典型情况分治法的典型情况 A Problem of size nSubproblem1 of size n/2Subproblem2 of size n/2A solution to subproblem1A solution to subproblem2A solution to the original

22、problem32算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分治法的时间复杂性分析分治法的时间复杂性分析通过迭代法求得方程的解通过迭代法求得方程的解：2.2 分治法的基本思想33算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 例：二分搜索技术|问题提出：问题提出：n给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n1，现要在，现要在这这n个元素中找出一特定元素个元素中找出一特定元素x。|分析：分析：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地

23、解决；n该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解分解出的各个子问题是相互独立的。出的各个子问题是相互独立的。n分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；34算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 例1:二分搜索技术35算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 补充材料减治法|减治法的基本思想减治法的基本思想n减治法（减治法（reduce and conquer method）n将原问题分解为若干个子问题后，

24、只求解其中一个子问将原问题分解为若干个子问题后，只求解其中一个子问题：题：p原问题的解只存在于其中一个较小规模的子问题中原问题的解只存在于其中一个较小规模的子问题中p原问题的解与其中一个较小规模的子问题的解之间原问题的解与其中一个较小规模的子问题的解之间存在对应关系；存在对应关系；n减治法是一种退化了的分治法。减治法是一种退化了的分治法。36算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 补充材料减治法|减治法的典型情况：减治法的典型情况：A Problem of size nSubproblem of size n/2A solution to

25、subproblemA solution to the original problem37算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 分治法的应用n数值计算问题中的分治法数值计算问题中的分治法n组合问题中的分治法组合问题中的分治法n排序问题中的分治法排序问题中的分治法n几何问题中的分治法几何问题中的分治法38算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 应用专题一|数值计算问题中的分治法数值计算问题中的分治法n大整数的乘法大整数的乘法nstrassen矩阵乘法矩阵乘法39算法设计与分析算法设计与

26、分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|引：大整数的存储与运算引：大整数的存储与运算n计算机存储数据是按类型分配空间的。计算机存储数据是按类型分配空间的。n例如：在微型机上，例如：在微型机上，n为整型提供为整型提供2个字节的存储空间，则整型数据的范围为个字节的存储空间，则整型数据的范围为3276832767；n为长整型提供为长整型提供4个字节的存储空间，则长整型数据的范个字节的存储空间，则长整型数据的范围为围为21474836482147483647；大整数的乘法40算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整

27、数的乘法n为实型提供为实型提供4个字节的存储空间，但不是精确存储数个字节的存储空间，但不是精确存储数据，只有据，只有6位精度，数据的范围位精度，数据的范围(3.4e-383.4e+38)；n为双精度型数据提供为双精度型数据提供8个字节的存储空间，数据的范个字节的存储空间，数据的范围围(1.7e-3081.7e+308)，其精确位数是，其精确位数是17位。位。41算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|在用数组存储高精度数据时，在用数组存储高精度数据时，n从计算的方便性考虑，决定将数据是由低到高还从计算的方便性考虑，决定将数据是由低到高还是由

28、高到低存储到数组中；可以每位占一个数组是由高到低存储到数组中；可以每位占一个数组元素空间，也可几位占一个数组元素空间。元素空间，也可几位占一个数组元素空间。n若需从键盘输入要处理的高精度数据，一般用字若需从键盘输入要处理的高精度数据，一般用字符数型组存储，这样无需对高精度数据进行分段符数型组存储，这样无需对高精度数据进行分段输入。输入。大整数的乘法42算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|当当N=100时，时，N！的准确值！的准确值|问题分析：问题分析：n问题要求对输入的正整数问题要求对输入的正整数N，计算，计算N！的准确值，！的准确值，

29、而而N！的增长速度仅次于指数增长的速度，所以！的增长速度仅次于指数增长的速度，所以这是一个高精度计算问题。这是一个高精度计算问题。大整数的乘法43算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法|例如：例如：n9！=362880n100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916

30、864000000 000000 000000 000000 44算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题描述：问题描述：n设设X和和Y都是都是n位的二进制整数，请设计一个有效位的二进制整数，请设计一个有效的算法，可以进行两个的算法，可以进行两个n位大整数的乘法运算。位大整数的乘法运算。|分析：分析：n1.小学的方法：小学的方法：O(n2)效率太低效率太低111101100010000000011011001110145算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 n2.可以用分治法的原理

31、设计一个更有效的算法。可以用分治法的原理设计一个更有效的算法。将将n位的二进制整数分为位的二进制整数分为2段：段：An/2位位Bn/2位位Cn/2位位Dn/2位位X=Y=则：则：X=A2n/2+B（乘乘2n/2，相当于左移相当于左移n/2位位）Y=C2n/2+D于是：于是：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD (1)46算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法效率：效率：4次次n/2位整数乘法位整数乘法(AC,AD,BC,BD)；3次不超过次不超过n位整数加法；位整数加法；2次移位次

32、移位(分别对应乘以分别对应乘以2n和和2n/2)所有加法和移位共用所有加法和移位共用O(n)步计算。步计算。时间复杂性分析时间复杂性分析T(n)=O(n2)没有改进没有改进47算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 时间复杂性分析时间复杂性分析 T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进大整数的乘法改进：把改进：把(1)式稍作修改：式稍作修改：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD (2)效率：效率：3次次n/2位整数乘法位整数乘法(AC,BD,(AB)(DC)；6次不超过次不超过n位整数加、减法

33、和位整数加、减法和2次移位；次移位；48算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法Char*Mult(char X,char Y,int n)/两个两个n位整数相乘位整数相乘 S=sign(X)*sign(Y);/取乘积的符号取乘积的符号 X=abs(X);Y=abs(Y);if(n=1)return(S*X*Y);else A=X的左边的左边n/2位；位；B=X的右边的右边n/2位；位；C=Y的左边的左边n/2位；位；D=Y的右边的右边n/2位；位；m1=Mult(A,C,n/2);m2=Mult(A-B,D-C,n/2);m3

34、=Mult(B,D,n/2);S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return S;注意注意：该算法可改为十进制数乘法，只需将基数该算法可改为十进制数乘法，只需将基数2变为变为10，即：即：2n 10n,2n/2 10n/249算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法u小学的方法小学的方法：O(n2)效率太低效率太低u分治法分治法:O(n1.59)较大的较大的改进改进50算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法|更快的方法？更快的方法？n

35、如果将大整数分成更多段，用更复杂的方式把它如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。们组合起来，将有可能得到更优的算法。n这个思想导致了快速傅利叶变换这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生，该方法也可以看作是一个复的产生，该方法也可以看作是一个复杂的分治算法。杂的分治算法。n对于大整数乘法，它能在对于大整数乘法，它能在O(nlogn)时间内解决。时间内解决。|是否能找到线性时间的算法？是否能找到线性时间的算法？n目前为止还没有结果目前为止还没有结果。51算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川

36、师范大学 计算机科学学院 刘芳 strassen矩阵乘法|传统的方法传统的方法n若若A和和B是是2个个nn的矩阵，则它们的乘积的矩阵，则它们的乘积C=AB同同样是一个样是一个nn的矩阵。的矩阵。A和和B的乘积矩阵的乘积矩阵C中的元中的元素素Ci,j定义为定义为:若依此定义来计算若依此定义来计算A和和B的乘积矩阵的乘积矩阵C，则每计算，则每计算C的一个元素的一个元素Ci,j，需要做，需要做n个乘法和个乘法和n1次加法。次加法。因此，求出矩阵因此，求出矩阵C的的n2个元素所需的计算时间为个元素所需的计算时间为O(n3)。52算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计

37、算机科学学院 刘芳|分治法分治法n将矩阵将矩阵A，B和和C中每一矩阵都分块成中每一矩阵都分块成4个大小相等的子矩个大小相等的子矩阵，每个子矩阵都是阵，每个子矩阵都是n/2n/2的方阵。的方阵。n由此可将方程由此可将方程C=AB重写为：重写为：由此可得由此可得：strassen矩阵乘法53算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 n为了降低时间复杂度，必须减少乘法的次数。为了降低时间复杂度，必须减少乘法的次数。nStrassen矩阵乘法矩阵乘法strassen矩阵乘法54算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计

38、算机科学学院 刘芳 验证验证:C22=M5+M1-M3-M7 =(A11+A22)(B11+B22)+A11(B12-B21)-(A21+A22)B11-(A11-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22-A21B11-A22B11-A11B11 -A11B12+A21B11+A21B12 =A21B12+A22B22strassen矩阵乘法55算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 strassen矩阵乘法56算法设计与分析算法设计与分析递归与分治策略递归与分治策略

39、四川师范大学 计算机科学学院 刘芳 完整的完整的Strassen算法如下：算法如下：STRASSEN(n,A,B,C)if(n=2)MATRIX-MULTIPLY(A，B，C);/普通普通2*2矩阵相乘矩阵相乘 else /将矩阵将矩阵A和和B分块分块;STRASSEN(n/2,A11,B12-B22,M1);STRASSEN(n/2,A11+A12,B22,M2);STRASSEN(n/2,A21+A22,B11,M3);STRASSEN(n/2,A22,B21-B11,M4);STRASSEN(n/2,A11+A22,B11+B22,M5);STRASSEN(n/2,A12-A22,B21

40、+B22,M6);STRASSEN(n/2,A11-A21,B11+B12,M7);strassen矩阵乘法57算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 strassen矩阵乘法|传统方法：传统方法：O(n3)|分治法分治法:O(n2.81)nStrassen将将2个个n/2阶方阵乘积的乘法次数由传统的阶方阵乘积的乘法次数由传统的8次变为次变为7次，但增加了加、减法的运算次数。次，但增加了加、减法的运算次数。nStrassen矩阵乘法目前没有太大实际意义。矩阵乘法目前没有太大实际意义。n当当n120时，它与普通矩阵乘法在计算时间上并无明时，它

41、与普通矩阵乘法在计算时间上并无明显的差异。只有当显的差异。只有当n很大时，才会显示出优越性。很大时，才会显示出优越性。58算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 strassen矩阵乘法|更快的方法更快的方法?nHopcroft和和Kerr已经证明已经证明(1971)，计算，计算2个个22矩阵的乘积，矩阵的乘积，7次乘法是必要的。次乘法是必要的。n因此，要想进一步改进矩阵乘法的时间复杂性，就不能再因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算基于计算22矩阵的矩阵的7次乘法这样的方法了，或许应当研究次乘法这样的方法了，或许应当研

42、究33或或55矩阵的更好算法。矩阵的更好算法。n在在Strassen之后又有许多算法改进了矩阵乘法的计算时间之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是复杂性。目前最好的计算时间上界是O(n2.376)。|是否能找到是否能找到O(n2)的算法？的算法？59算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 应用专题二|组合问题中的分治法组合问题中的分治法n棋盘覆盖问题棋盘覆盖问题n循环日程赛安排问题循环日程赛安排问题n最大子段和问题最大子段和问题60算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算

43、机科学学院 刘芳|问题描述：问题描述：n在一个在一个2k2k个方格组成的棋盘中，恰有一个方格个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称与其它方格不同，称该方格为一特殊方格，且称该棋盘为特殊棋盘。该棋盘为特殊棋盘。n在棋盘覆盖问题中，要用图示的在棋盘覆盖问题中，要用图示的4种不同形态的种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何所有方格，且任何2个个L型骨牌不得重叠覆盖。型骨牌不得重叠覆盖。棋盘覆盖问题61算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘

44、芳 棋盘覆盖问题|例如：例如：nk2时的一个特殊棋盘时的一个特殊棋盘2k 2k的棋盘覆盖中，用到的骨牌数为的棋盘覆盖中，用到的骨牌数为(4k-1)/362算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|例如：例如：554451143122332棋盘覆盖问题63算法设计与分析算法设计与分析0时，考虑采用分治策略：时，考虑采用分治策略：棋盘覆盖问题64算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|算法实现：算法实现：nP18棋盘覆盖问题65算法设计与分析算法设计与分析0时时,测试哪个子棋盘残缺以及形成测试

45、哪个子棋盘残缺以及形成3个残个残缺子棋盘需要缺子棋盘需要O(1),覆盖覆盖4个残缺子棋盘需四次递个残缺子棋盘需四次递归调用归调用,共需时间共需时间4T(k1)。T(k)=O(4k)渐进意义下的最优算法渐进意义下的最优算法与所需骨与所需骨牌数同阶牌数同阶棋盘覆盖问题66算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|还可以将棋盘覆盖推广到一般情况：还可以将棋盘覆盖推广到一般情况：887786675446554321133221121111109912121110109877655887665433211443221棋盘覆盖问题67算法设计与分析算法设

46、计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题描述：问题描述：n设计一个满足以下要求的比赛日程表：设计一个满足以下要求的比赛日程表：n(1)每个选手必须与其他每个选手必须与其他n1个选手各赛一次；个选手各赛一次；n(2)每个选手一天只能赛一次；每个选手一天只能赛一次；n(3)循环赛一共进行循环赛一共进行n1天。天。循环赛日程表68算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|例如：例如：1234567821436587341278564321876556781234658721437856341287

47、654321队队天天69算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|分析：分析：n法法1：分治策略：分治策略n按分治策略，将所有的选手分为两半，按分治策略，将所有的选手分为两半，n个选手的比赛个选手的比赛日程表就可以通过为日程表就可以通过为n/2个选手设计的比赛日程表来决个选手设计的比赛日程表来决定。定。n递归地用对选手进行分割，直到只剩下递归地用对选手进行分割，直到只剩下2个选手时，比个选手时，比赛日程表的制定就变得很简单。这时只要让这赛日程表的制定就变得很简单。这时只要让这2个选手个选手进行比赛就可以了。进行比赛就可以了。A1

48、A2A2A170算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|分析分析n法法2：递推法：递推法(迭代法迭代法)122112342143341243211234567821436587341278564321876556781234658721437856341287654321加加2加加471算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|递推法递推法(迭代法迭代法)n即即2k个选手的比赛日程在个选手的比赛日程在2k-1个选手的比赛日程基础上通过个选手的比赛日程基础上通过迭

49、代完成，每次迭代，将问题分为迭代完成，每次迭代，将问题分为4个部分：个部分：n左上角：左上角：2k-1个选手前半程的比赛日程个选手前半程的比赛日程n左下角：另左下角：另2k-1个选手前半程的比赛日程，由左上角加个选手前半程的比赛日程，由左上角加2k-1得到得到n右上角：将左下角抄到右上角，得到另右上角：将左下角抄到右上角，得到另2k-1个选手后半程的比赛日程。个选手后半程的比赛日程。n右上角：将左上角抄到右下角，得到右上角：将左上角抄到右下角，得到2k-1个选手后半程的比赛日程。个选手后半程的比赛日程。72算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院

50、刘芳|问题提出：问题提出：n给定由给定由n个整数（可能为负数）组成的序列：个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为均为负数，定义其最大子段和为0。依其定义，所。依其定义，所求的最优值为：求的最优值为：最大子段和问题73算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|1.最大子段和问题的简单算法最大子段和问题的简单算法int MaxSum(int n,int*a,int&besti,int&bestj)int sum=0;for(int i=1;i=