02 递归与分治策略(精品).ppt

《02 递归与分治策略(精品).ppt》由会员分享，可在线阅读，更多相关《02 递归与分治策略(精品).ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学本章主要内容本章主要内容n2.1 递归的概念n2.2 分治法的基本思想n2.3 二分搜索技术n2.4 大整数的乘法n2.5 Strassen矩阵乘法n2.7 合并排序n2.8 快速排序n2.11 循环赛日程表段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n2.1.1 递归的概念n直接或间接地直接或间接地调用自身调用自身的算法称为递归算法。的算法称为递归算法。n用函数自身给出定义的函数用函数自身给出定义的函数称为称为递归函数递归函数。n在计算机算法设计与分析中，使用递归技术往往使在计算机算法设计与分析中，使

2、用递归技术往往使函数的定义和算法的函数的定义和算法的描述简洁且易于理解描述简洁且易于理解。n使用递归解决问题，思路清晰，代码少。但是在主使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如流高级语言中（如C语言、语言、Pascal语言等）使用递归语言等）使用递归算法要算法要耗用更多的栈空间耗用更多的栈空间，应避免采用。，应避免采用。n一般的的递归算法都一般的的递归算法都可以可以改写成与之等价的改写成与之等价的非递归非递归算法。算法。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n2.1.2 递归的几个实例n例例1 阶乘函数（理解）阶乘函数（理解）n可

3、以递归可以递归地定义为：地定义为：n其中：其中：nn=0时，时，n!=1为边界条件为边界条件nn0时，时，n!=n(n-1)!为递归方程为递归方程n边界条件与递归方程是递归函数的二个要素，边界条件与递归方程是递归函数的二个要素，只有具只有具备这两个要素，才能在备这两个要素，才能在有限次有限次计算后得出结果。计算后得出结果。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n若若乘法执行次数记作记作M(n)，则有如下结论：，则有如下结论：nM(n)没有定义为没有定义为n的函数，而是定义的函数，而是定义它本身在另一点它本身在另一点上值的函数上值的函数，这种等式称为，

4、这种等式称为递推关系递推关系，或，或递推式递推式。n用用反向替换法反向替换法求解递推关系式：求解递推关系式：M(n)=M(n-1)+1替换 M(n-1)=M(n-2)+1=M(n-2)+1+1=M(n-2)+2替换 M(n-2)=M(n-3)+1=M(n-3)+1+1=M(n-3)+3=M(n-i)+i=M(n-n)+n=n段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n例例2 斐波那契数斐波那契数列（理解）列（理解）nFibonacci Sequencen黄金分割数列黄金分割数列兔子繁殖问题 1202年，意大利数学家斐波那契(Fibonacci)在他的算盘

5、书中提出这样一个问题：有人想知道一年内一对兔子可繁殖成多少对，便筑了一道围墙把一对兔子关在里面。已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后第二个月就开始生小兔子。假如一年内没有发生死亡，则一对兔子一年内能繁殖成多少对？段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念表示一对成熟的兔子；表示未成熟的兔子。每一对成熟的兔子经过一个月变成本身的及新生的未成熟；未成熟的一对经过一个月变成成熟的，没有出生新兔；画出左图。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n在数学上，斐波那契数列是以递归的方法来定义：在数学上，斐

6、波那契数列是以递归的方法来定义：n第第n个个Fibonacci数可递归地计算如下：数可递归地计算如下：段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n斐波那契数列一般表达式的初等代数解法斐波那契数列一般表达式的初等代数解法n已知已知na1=1，a2=1，an=an 1+an 2n首先构建等比数列首先构建等比数列n令令 0，0,n设设an+an 1=(an 1+an 2)n化化简简得得nan=()an 1+an 2比较系数可比较系数可得得解得解得段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n预知后事如何变换.n参见维基百科

7、参见维基百科斐波那契数列斐波那契数列nhttp:/zh.wikipedia.org/zh-cn/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97 段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n斐波那契数斐波那契数列的列的通项公式通项公式为（为（又叫又叫“比内公式比内公式”，是，是用无理数表示有理数用无理数表示有理数的一个的一个范例）范例）n可它的每一项却都是整数。开普勒发现两个斐波那契可它的每一项却都是整数。开普勒发现两个斐波那契数数的的后两项比后两项比会趋近黄金分割会趋近黄金分割：n这个数列有广

8、泛的应用，如这个数列有广泛的应用，如树的年分枝数目树的年分枝数目就遵循斐就遵循斐波那契数列的规律；而且计算机科学的发展，为斐波波那契数列的规律；而且计算机科学的发展，为斐波那契数列提供了新的应用场所。那契数列提供了新的应用场所。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n斐波那契的另一种表示法段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n前面定义的前面定义的递归算法效率并不高递归算法效率并不高，为什么？，为什么？F(5)F(4)F(3)

9、F(3)F(2)F(2)F(1)F(1)F(0)F(2)F(1)F(1)F(0)F(1)F(0)数列的递归调用树Fib(n)/输入：非负整数n/输出：第n个斐波那契数Create F0nF0=1;F1=1for i=2 to n do Fi=Fi-1+Fi-2return F(n)段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n例例3 Ackerman函数（了解）函数（了解）n当一个当一个函数函数及及它的一个变量它的一个变量是由是由函数自身函数自身定义时，称定义时，称这个函数是这个函数是双递归函数双递归函数。n前两例都能找到函数的非递归定义，但前两例都能找到

10、函数的非递归定义，但Ackerman函函数却无法数却无法找到找到(?但是有非递归的算法但是有非递归的算法)。nAckerman函数函数A(n,m)定义如下：定义如下：段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念nA(n,m)的自变量的自变量m的每个值都定义了一个单变量函数的每个值都定义了一个单变量函数nM=0时：时：A(n,0)=n+2nM=1时：时：nA(n,1)=A(A(n-1,1),0)=A(n-1,1)+2nA(1,1)=2n故故A(n,1)=2*n(n=1)nM=2时：时：nA(n,2)=A(A(n-1,2),1)=2A(n-1,2)nA(1,2

11、)=A(A(0,2),1)=A(1,1)=2n故故A(n,2)=2n。nM=3时，类似的可以推出时，类似的可以推出 ，2的层数为的层数为nnM=4时，时，A(n,4)的的增长速度非常快增长速度非常快，没有适当的数学，没有适当的数学式子来表示这一函数。式子来表示这一函数。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n定义单变量的定义单变量的Ackerman函数函数A(n)为，为，A(n)=A(n,n)。n定义其拟逆函数定义其拟逆函数(n)为为n(n)=minkA(k)nn即即(n)是使是使nA(k)成立的最小的成立的最小的k值。值。nA(0)=1,A(1)=

12、2,A(2)=4,A(3)=16,A(4)=溢出溢出推知推知(1)=0,(2)=1,(3)=(4)=2,(5)=(16)=3.n(n)在复杂度分析中常遇到。在复杂度分析中常遇到。n对于通常所见到的正整数对于通常所见到的正整数n，有，有(n)4。n但在理论上但在理论上(n)没有上界，随着没有上界，随着n的增加，它以难以想的增加，它以难以想象的慢速度趋向正无穷大。象的慢速度趋向正无穷大。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n例例4 排列排列问题（理解）问题（理解）n全排列是全排列是将一组数按一定顺序进行排列将一组数按一定顺序进行排列，如果这组数，如果这

13、组数有有n个，那么全排列数为个，那么全排列数为n!个。个。n设计设计一个递归算法生成一个递归算法生成n个元素个元素r1,r2,rn的全排列的全排列（所有元素按不同顺序所有的组合所有元素按不同顺序所有的组合）。n以以1,2,3,4,5为例说明全排列的递归算法。为例说明全排列的递归算法。n先看最后两个数先看最后两个数4,5。它们的全排列为它们的全排列为4 5和和5 4,即即以以4开头和开头和5的全排列的全排列和和以以5开头和开头和4的全排列的全排列。n再看后三个数再看后三个数3,4,5。它们的全排列为。它们的全排列为3 4 5、3 5 4、4 3 5、4 5 3、5 3 4、5 4 3 六组数。即

14、六组数。即以以3开头和开头和45的全的全排列的排列的、以、以4开头和开头和35的全排列的全排列和和以以5开头和开头和34的全排的全排列列。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n根据以上分析，可有如下递归定义根据以上分析，可有如下递归定义n设设R=r1,r2,rn是待排列的是待排列的n个元素，个元素，Ri=R-ri。n集合集合X中元素的全排列记为中元素的全排列记为Perm(X)。n(ri)Perm(X)表示在全排列表示在全排列Perm(X)的每一个排列前加的每一个排列前加上前缀得到的排列。上前缀得到的排列。nR的全排列可归纳定义如下：的全排列可归纳定

15、义如下：n当当n=1时，时，Perm(R)=(r)，其中，其中r是集合是集合R中唯一的中唯一的元素；元素；n当当n1时，时，Perm(R)由由(r1)Perm(R1)，(r2)Perm(R2)，(rn)Perm(Rn)构成。构成。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n例例5 整数划分整数划分问题（了解）问题（了解）n将正整数将正整数n表示成表示成一系列正整数之和一系列正整数之和：n=n1

16、+n2+nk，其中，其中n1n2nk1，k1。n正整数正整数n的这种表示称为的这种表示称为正整数正整数n的划分的划分。n求正整数求正整数n的不同划分个数。的不同划分个数。n例如正整数例如正整数6有如下有如下11种不同的划分：种不同的划分：n6n5+1n4+2，4+1+1n3+3，3+2+1，3+1+1+1n2+2+2，2+2+1+1，2+1+1+1+1n1+1+1+1+1+1段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n前面问题本身都有明显递归关系，容易求解。前面问题本身都有明显递归关系，容易求解。n本例中，若设本例中，若设p(n)为正整数为正整数n的划分

17、数，难以找到递的划分数，难以找到递归关系归关系；n增加增加一个变量：一个变量：将最大加数将最大加数n不大于不大于m的划分个数记的划分个数记作作q(n,m)。q(n,m)有如下递归关系：有如下递归关系：nq(n,1)=1，n1n当最大数当最大数n1时，任何正整数时，任何正整数n只有一种划分形式：只有一种划分形式：n=1+1+.+1（共（共n个）。个）。nq(n,m)=q(n,n)，mnn最大加数最大加数n 实际上实际上不能大于不能大于n。nq(1,m)=1。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念nq(n,n)=1+q(n,n-1)n正整数正整数n的划分

18、由的划分由n=n的划分和的划分和nn-1的划分组成。的划分组成。nq(n,m)=q(n,m-1)+q(n-m,m),nm1n正整数正整数n的最大加数的最大加数n不大于不大于m的划分由的划分由n=m的划分和的划分和nm-1 的划分组成。的划分组成。n计算计算q(n,m)的递归式如下，可以的递归式如下，可以发现发现 p(n)=q(n,n)段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学相传相传.n印度北部贝拿勒斯圣庙里n一块一块黄铜板上插着三根宝石黄铜板上插着三根宝石针，针，在其中一根针上从在其中一根针上从下到

19、上地穿好了由大到小下到上地穿好了由大到小的的64片片金片，这金片，这就是就是汉诺汉诺塔塔。不论。不论白天黑夜，总有一个僧侣在按照下面的法白天黑夜，总有一个僧侣在按照下面的法则移动这些金片则移动这些金片：n一一次只移动一次只移动一片片n不管不管在哪根针在哪根针上上n小小片必须在大片片必须在大片上面上面n僧侣们预言，当所有的金片都从梵天穿好的那根针僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。灭，而梵塔、庙宇和众生也都将同归于尽。段旭良四川农业大学段旭良四川农业大学段旭良四川

20、农业大学假如这个假如这个传说是真的传说是真的！n2012年？n假设假设有有n片，移动次数是片，移动次数是f(n)。n显然显然f(1)=1，f(2)=3，f(3)=7，且，且f(k+1)=2*f(k)+1。n即即f(n)=2n-1。nn=64时时nf(64)=264-1=18446744073709551615n假如假如每秒钟一次，平均每年每秒钟一次，平均每年31556952秒，则秒，则18446744073709551615/31556952=584554049253.855年年=5845亿亿年年以上以上段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n例例6

21、 Hanoi塔塔问题（理解）问题（理解）n设设a,b,c是是3个塔座。开始时，在塔座个塔座。开始时，在塔座a上有一叠共上有一叠共n个个圆盘，这些圆盘圆盘，这些圆盘自下而上自下而上，由大到小由大到小地叠在一起。地叠在一起。n各圆盘从小到大编号为各圆盘从小到大编号为1,2,n,现要求将塔座现要求将塔座a上的上的这一叠圆盘移到塔座这一叠圆盘移到塔座b上，并仍按同样顺序叠置。上，并仍按同样顺序叠置。n在移动圆盘时应遵守以下移动规则：在移动圆盘时应遵守以下移动规则：n每次只能移动每次只能移动1个圆盘；个圆盘；n任何时刻都任何时刻都不允许不允许将较大的圆盘压在较小的圆盘上；将较大的圆盘压在较小的圆盘上；n

22、在满足移动规则在满足移动规则1和和2的前提下，可将圆盘移至的前提下，可将圆盘移至a,b,c中中任一塔座上。任一塔座上。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n解法解法n为了把为了把n1个盘子从木桩个盘子从木桩1移到木桩移到木桩3，需要把，需要把n-1个盘个盘子递归的移到木桩子递归的移到木桩2（借助（借助3）；）；n然后把最大的盘子（第然后把最大的盘子（第n个）移到木桩个）移到木桩3；n再把再把n-1个盘子由木桩个盘子由木桩2移动到木桩移动到木桩3（借助（借助1）。）。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n

23、移动次数为移动次数为M(n)，n为盘子数量，则有如下递推式为盘子数量，则有如下递推式nM(1)=1nM(n)=M(n-1)+1+M(n-1)，n1n建立如下递推关系：建立如下递推关系：nM(1)=1nM(n)=2M(n-1)+1，n1n使用使用反向替换法反向替换法求解：求解：nM(n)=2M(n-1)+1n=22M(n-2)+1+1=22M(n-2)+2+1n=222M(n-3)+1+2+1=23M(n-3)+22+2+1n=2iM(n-i)+2i-1+2i-2+2+1=2iM(n-i)+2i-1段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n由于初始条件是

24、由于初始条件是n=1，所以，所以i=n-1，求解递推式：，求解递推式：nM(n)=2n-1M(n-(n-1)+2n-1-1n=2n-1M(1)+2n-1-1=2n-1n这是一个这是一个指数级指数级的算法，但是，对于此问题来说，这的算法，但是，对于此问题来说，这是最高效的算法。是最高效的算法。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n递归算法递归算法n/hanoi(n,a,b,c)表示将塔座表示将塔座a上自下而上、由大到小上自下而上、由大到小叠放的叠放的n个圆盘依规则移动到个圆盘依规则移动到b上，移动过程中以上，移动过程中以c为为辅助塔座。辅助塔座。n/

25、move(a,b)表示将表示将a上编号为上编号为n的圆盘移动到的圆盘移动到b上上npublic static void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n递归小结n优点优点n结构清晰，可读性强结构清晰，可读性强，而且容易用数学归纳法来证明，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很算法的正确性，因此它为设计算法、调试程序带来很大方便。大方便。n缺点缺点n递

26、归算法的递归算法的运行效率较低运行效率较低，无论是耗费的计算，无论是耗费的计算时间时间还还是占用的存储是占用的存储空间空间都比非递归算法要多。都比非递归算法要多。n解决方法解决方法n在递归算法中消除递归调用，使其转化为非递归算法。在递归算法中消除递归调用，使其转化为非递归算法。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.1 递归的概念递归的概念n采用一个用户定义的栈来模拟系统的递归调用工作栈。采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但该方法通用性强，但本质上还是递归本质上还是递归，只不过，只不过人工做人工做了本来由编译器做的事情了本来由编译器做的事情，优化

27、效果不明显。，优化效果不明显。n用递推来实现递归函数用递推来实现递归函数。总之，总之，递归式一种优雅的算法。递归式一种优雅的算法。但我们应该但我们应该谨慎使用递归谨慎使用递归算法，因为算法，因为它们的简洁可能会掩盖它们的低效率。它们的简洁可能会掩盖它们的低效率。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治分治法（法（Divide-Conquer）n分治法的分治法的基本思想基本思想是是将一个规模为将一个规模为n的问题分解为的问题分解为k个规模较小的子问题，这些个规模较小的子问题，这些子问题互相独立且与原子问题互相独立且与原问题相同问题相同。n对对k个子问题分别求解个子问题分

28、别求解。若子。若子问题的规模仍然不够问题的规模仍然不够小小，再，再划分为划分为k个子问题，如此个子问题，如此递归进行，递归进行，直到问直到问题规模足够小题规模足够小，容易求解，容易求解为止为止。n分治法对于分治法对于并行计算并行计算是非常理想的。是非常理想的。凡治众如治寡，分数是也。凡治众如治寡，分数是也。孙子兵法孙子兵法段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想n将求出的小规模的问题的解合并为一个更大规模的将求出的小规模的问题的解合并为一个更大规模的问题的解，问题的解，自底向上自底向上逐步求出逐步求出原问题原问题的解。的解。n分治法的设计思

29、想是，将一个难以直接解决的大问分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便题，分割成一些规模较小的相同问题，以便各个击各个击破，分而治之。破，分而治之。sub problem 2 of size n/2sub problem 1 of size n/2a solution to sub problem 1a solution tothe original problema solution to sub problem 2a problem of size n段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想例例

30、n伪币问题n给你一个装有给你一个装有16个硬币的袋子。个硬币的袋子。16个硬币中有一个个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要是伪造的，并且那个伪造的硬币比真的硬币要轻一轻一些些。你的任务是。你的任务是找出这个伪造的硬币找出这个伪造的硬币。n提供一台可用来比较两组硬币重量的仪器，可比较提供一台可用来比较两组硬币重量的仪器，可比较硬币的重量是否相同。硬币的重量是否相同。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想例例n笨办法笨办法n比较硬币比较硬币1与与2的重量。假如硬币的重量。假如硬币1比比2轻，则轻，则1是伪造是伪造的；假如的；

31、假如2比比1轻，则硬币轻，则硬币2是伪造的；假如两硬币重是伪造的；假如两硬币重量相等，则比较硬币量相等，则比较硬币 3和硬币和硬币4按照这种方式，按照这种方式，可以可以最多通过最多通过8次次比较来判断伪币的存在并找出这一比较来判断伪币的存在并找出这一伪币。伪币。n分治分治n把把1 6个硬币的问题分成两个个硬币的问题分成两个8硬币的问题来解决。一硬币的问题来解决。一次比较即可判断是否存在伪币。次比较即可判断是否存在伪币。n两个（三个？）硬币的情况作为不可再分的小问题。两个（三个？）硬币的情况作为不可再分的小问题。需要几步可找出伪币？需要几步可找出伪币？段旭良四川农业大学段旭良四川农业大学段旭良四

32、川农业大学2.2 分治法的基本思想分治法的基本思想例例n金块问题n有一个老板有一袋金块。每个月将有有一个老板有一袋金块。每个月将有两名雇员两名雇员会因会因其优异的表现分别被奖励一个金块。排名第一的雇其优异的表现分别被奖励一个金块。排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。袋中最轻的金块。n如果有新的金块周期性的加入袋中，则如果有新的金块周期性的加入袋中，则每个月都必每个月都必须找出最轻和最重的金块。须找出最轻和最重的金块。n假设有一台比较重量的仪器，我们希望用最少的比假设有一台比较重量的仪器，我们希望用最少的比较次数找出

33、最轻和最重的金块。较次数找出最轻和最重的金块。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想例例n通常通常n假设袋中有假设袋中有n 个金块。可以用函数个金块。可以用函数Max通过通过n-1次比次比较找到最重的金块较找到最重的金块，从，从余下的余下的 n-1个金块中用类似的个金块中用类似的方法方法通过通过 n-2次比较次比较找出最轻的金块。这样，比较的找出最轻的金块。这样，比较的总次数为总次数为2n-3。需要需要2n-2次比较次比较段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想例例n分而治之分而治之n

34、用二叉树来表示。叶子表示用二叉树来表示。叶子表示8个金块（个金块（a,b,h)，每个阴影节点表示一个包含其子树中所有叶子的问题。每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点因此，根节点A表示寻找表示寻找8个金块中最轻、最重金块个金块中最轻、最重金块的问题的问题n1 把大问题划分成许多个小问题，小问题的大小为把大问题划分成许多个小问题，小问题的大小为1或或2。n2 比较每个大小为比较每个大小为2的问题中的金块，确定哪一个较重的问题中的金块，确定哪一个较重和哪一个较轻。和哪一个较轻。n3 对较轻的金块进行比较以确定哪一个金块最轻，对对较轻的金块进行比较以确定哪一个金块最轻，对较重的

35、金块进行比较以确定哪一个金块最重。较重的金块进行比较以确定哪一个金块最重。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想例例n金块比较问题复杂度金块比较问题复杂度n设设c(n)为使用分而治之方法所需要的比较次数。为了为使用分而治之方法所需要的比较次数。为了简便，假设简便，假设 n是是2的幂。的幂。n当当n=2时，时，c(n)=1。对于较大的。对于较大的 n，递归关系，递归关系nc(n)=2c(n/2)+2n求解得求解得c(n)=3n/2 2n在本例中，使用分而治之方法比逐个比较的方法少用在本例中，使用分而治之方法比逐个比较的方法少用了了25的比较

36、次数。的比较次数。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想n分治法的适用条件n分治法所能解决的问题一般具有以下分治法所能解决的问题一般具有以下几个特征几个特征：n问题问题规模缩小规模缩小到一定的程度就可以到一定的程度就可以容易地解决容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该问题可以分解为若干个规模较小的相同问题，即该该问题具有问题具有最优子结构最优子结构性质性质；n利用分解出的子问题的利用分解出的子问题的解可合并为该问题的解解可合并为该问题的解；n该问题所分解出的各个该问题所分解出的各个子问题是相互独立子问题是相互独立的，

37、即子问的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。n这条特征涉及到分治法的效率，如果各子问题是不独这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用共的子问题，此时虽然也可用分治法，但一般用动态动态规划规划较好。较好。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想n分治法的基本步骤（伪码描述）ndivide-and-conquer(P)if(|P|=n0)adhoc(P);/n0为一阈值，表示当问题为

38、一阈值，表示当问题P的规模不超过的规模不超过n0时，问题已容易直接解出，不必再继续时，问题已容易直接解出，不必再继续分解。分解。adhoc(P)为基本子算法。为基本子算法。divide P into smaller sub-instances P1,P2,.,Pk;/分解分解for(i=1;i=k;i+)yi=divide-and-conquer(Pi);/递归求解子递归求解子问题问题return merge(y1,.,yk);/合并子问题解为原问题解合并子问题解为原问题解段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想n子问题平衡n人们人们从大量

39、实践中发现，在用分治法设计算法时，从大量实践中发现，在用分治法设计算法时，最好使最好使子问题的规模大致相同子问题的规模大致相同。即将一个问题分成。即将一个问题分成大小相等的大小相等的k个子问题的处理方法是行之有效的。个子问题的处理方法是行之有效的。n这种使子问题规模大致相等的做法是出自一种这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规的思想，它几乎总是比子问题规模不等的做法要好。模不等的做法要好。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想分治法的基本思想n分治法的复杂性分析n一个分治法将一个分治

40、法将规模为规模为n的问题分成的问题分成k个规模为个规模为n/m的的子问题去解。设子问题去解。设分解阀值分解阀值n0=1，且，且adhoc(P)解解规模规模为为1的问题耗费的问题耗费1个单位时间。再设将原问题分解为个单位时间。再设将原问题分解为k个子问题以及用个子问题以及用merge将将k个子问题的解合并为原个子问题的解合并为原问题的解需用问题的解需用f(n)个单位时间个单位时间。n用用T(n)表示该分治法解规模为表示该分治法解规模为|P|=n的问题所需的计的问题所需的计算时间，则算时间，则有如下递推式：有如下递推式：段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.2 分治法的基本思想

41、分治法的基本思想n通过迭代法求得方程解：通过迭代法求得方程解：n注意注意n递归方程及其解只给出递归方程及其解只给出n等于等于m的方幂时的方幂时T(n)的的值值n通常通常假定假定T(n)是单调上升的，从而当是单调上升的，从而当minmi+1时，时，T(mi)T(n)T(mi+1)。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.3 二分搜索技术二分搜索技术n给定已按升序排好序的n个元素a0:n-1，要在这n个元素中找出一特定元素x。n适用分治法求解问题的基本特征：适用分治法求解问题的基本特征：n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；

42、n该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;n分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；n分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。n很显然此问题分解出的很显然此问题分解出的子问题相互独立子问题相互独立，即在，即在ai的的前面或后面查找前面或后面查找x是独立的子问题，因此是独立的子问题，因此满足分治满足分治法法的适用的适用条件。条件。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.3 二分搜索技术二分搜索技术n二分搜索（折半查找）n二分查找例(70?)n二分查找明显基于递归思想，但可以

43、非递归实现。二分查找明显基于递归思想，但可以非递归实现。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.3 二分搜索技术二分搜索技术n二分查找非递归伪代码BinarySearch(A0n-1,K)/非递归折半查找/输入：升序数组A和查找键K/输出：数组下标，该元素等于K；若没有，返回-1l=0;r=n-1while l=r dom=(l+r)/2 if K=Am return melse if KAm r=m-1else l=m+1return-1段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.3 二分搜索技术二分搜索技术n二分搜索C+代码：npublic static i

44、nt BinarySearch(int a,int x,int n)/在在 a0=a1=.=an-1 中搜索中搜索 x/找到找到x时返回其在数组中的位置，否则返回时返回其在数组中的位置，否则返回-1int left=0;int right=n-1;while(left amiddle)left=middle+1;else right=middle-1;return-1;/未找到未找到x段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.3 二分搜索技术二分搜索技术T(1)=1T(2)=T(1)+1=2T(4)=T(2)+1=3T(8)=T(4)+1=4T(n)=T(2m)=T(2m-1)

45、+1=m+1=log2n+1=O(logn)n算法复杂度分析算法复杂度分析n每执行一次算法的每执行一次算法的while循环，循环，待搜索数组的大待搜索数组的大小减少一半。小减少一半。n最坏情况下，最坏情况下，while循环循环被执行了被执行了O(logn)次。次。n循环体内运算需要循环体内运算需要O(1)时间，因此整个算法在时间，因此整个算法在最坏情况下的计算时间最坏情况下的计算时间复杂性为复杂性为O(logn)。令n=2mm=0m=1m=2m=3段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.4 大整数的乘法大整数的乘法n密码技术常要对超过100位的十进制数进行乘法运算，需作特别处

46、理。n计算两数乘法，例如计算两数乘法，例如23*14n23=2*101+3*100,14=1*101+4*100n23*14=(2*101+3*100)*(1*101+4*100)=2*1*102+(3*1+2*4)101+(3*4)100n对于任何两位数对于任何两位数a=a1a0和和b=b1b0，乘积，乘积c为为nc=a*b=c2102+c1*101+c0n其中：其中：c2=a1*b1,c0=a0*b0c1=(a1+a0)*(b1+b0)-(c2+c0)段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.4 大整数的乘法大整数的乘法n设计一个有效的算法，可以进行两个n位大整数的乘法运算

47、n分分治法治法:nX=A2n/2+BnY=C2n/2+DnXY=AC2n+(AD+BC)2n/2+BD=c2*2n+c1*2n/2+c0n其中，其中，c2、c1、c0采用相同的方法计算。采用相同的方法计算。n如果如果n是是2的乘方，就是一个计算两个的乘方，就是一个计算两个n位数乘积的递位数乘积的递归算法。归算法。ABn/2位 n/2位X=CDn/2位 n/2位Y=段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.4 大整数的乘法大整数的乘法n复杂性分析复杂性分析nn位数的乘法运算需要对位数的乘法运算需要对n/2位做三次乘法运算，乘法位做三次乘法运算，乘法次数次数M(n)的递推式为：的递

48、推式为：nM(n)=3M(n-1),n1nM(1)=1n当当b=2k时，用反向替换法求解：时，用反向替换法求解：nM(2k)=3M(2k-1)=32M(2k-2)=3iM(2k-i)=3kM(2k-k)=3kn因为因为k=log2n，所以，所以M(n)=3log2n=nlog23n1.585alogbc=clogba段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.4 大整数的乘法大整数的乘法n更快的方法n传统方法：传统方法：O(n2)效率太低效率太低n分治法分治法:O(n1.585)较大的改进较大的改进n更快的方法？更快的方法？n如果将大整数分成更多段，用更复杂的方式把它们组如果将大

49、整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。合起来，将有可能得到更优的算法。n最终这个最终这个思想导致了思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生的产生。该。该方法也可以看作是一个复杂的方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在分治算法，对于大整数乘法，它能在O(nlogn)时间内时间内解决。解决。n是否能找到线性时间的算法？是否能找到线性时间的算法？目前还目前还没有结果。没有结果。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.5 Strassen矩阵乘法矩阵乘法n矩阵乘法nV.Strass

50、en在在1969年发表的矩阵乘法算法。年发表的矩阵乘法算法。nnn矩阵矩阵A和和B的乘积矩阵的乘积矩阵C中的元素中的元素Ci,j定义为定义为n则每计算则每计算C的一个元素的一个元素Cij，需要做，需要做n次乘法和次乘法和n-1次加法。次加法。n算算出矩阵出矩阵C的的 个元素所需的计算时间为个元素所需的计算时间为O(n3)。段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学2.5 Strassen矩阵乘法矩阵乘法n首先假定首先假定n是是2的幂。将矩阵的幂。将矩阵A，B和和C中每一矩阵都分块中每一矩阵都分块成成4个大小相等的子矩阵。由此可将方程个大小相等的子矩阵。由此可将方程C=AB重写为：重