《算法设计与分析教学资料》第2章.ppt

《《算法设计与分析教学资料》第2章.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析教学资料》第2章.ppt（150页珍藏版）》请在三一文库上搜索。

1、第2章 递归与分治策略,学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分搜索技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； （5）合并排序和快速排序； （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表。,分治法概述,分治法是一种非常有用的算法技术，它可以用于求解许多算法问题. 什么是分治法?,算法总体思想,计算机求解的复杂度与问题的规模有关，回忆： 1、2、3n个元素的排序问题； 1、2、3n个元素的查找问题； 结论：多个元素的排序和查找比较少元素的排序和查找复杂和困难的多！ 想法：能否

2、将“多个元素的排序和查找”变成数个“较少元素的排序和查找”，分别进行？,算法总体思想,分治法的可行性： 如果原问题可以分成k个子问题 且子问题都可解 并可利用子问题的解求出原问题的解,算法总体思想,问题分解是求解复杂问题时很自然的做法。 求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分

3、为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题， 分

4、割成一些规模较小的相同问题，以便各个击破， 分而治之。 凡治众如治寡，分数是也。 -孙子兵法,算法总体思想,通常，由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。由此可知，分治法求解很自然地可用一个递归过程来表示。 分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。,2.1 递归的概念,直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就

5、为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,2.1 递归的概念,递归的使用场合： 数据结构本身是递归定义的，其实现算法往往是递归算法，比如二叉树和图等； 求解过程需要递归，算法描述简捷其易于理解及分析，比如阶乘计算,下面来看几个实例。,在算法设计中使用递归技术，往往使算法的描述简单明了、易于理解、容易编程和验证。在计算机软件领域，递归算法是一种非常重要并且不可或缺的算法。,2.1 递归的概

6、念,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件： 非递归定义的初始值,递归方程：递归定义式,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,较小自变量的函数值表示较大自变量的函数值,2.1 递归的概念,例1 阶乘函数,第n个阶乘可递归地计算如下： int factorial(int n) if (n=0) return 1; return n*factorial(n-1); ,2.1 递归的概念,例2 Fibonacci数列（斐波那契数列） 无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归

7、地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下： int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,数列的第n项的值是它前面两项之和,2.1 递归的概念,例3 Ackerman函数（阿克曼函数） 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下-有两个独立的整型变量m、n：,2.1 递归的概念,例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：,本例中的Ackerman函

8、数却无法找到非递归的定义。,2.1 递归的概念,例3 Ackerman函数 A(n，m)的自变量m的每一个值都定义了一个单变量函数（根据m的不同可得到基于n的不同函数！）： m=0时，A(n,0)=n+2 m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。 m=3时，类似的可以推出 m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,2.1 递归

9、的概念,例3 Ackerman函数 定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。 定义其拟逆函数(n)为：(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。 因为：A(0)=1,A(1)=2,A(2)=4,A(3)=16 所以：(1)=0，(2)=1，(3)= (4)=2 (5)= (16)=3 (n)在复杂度分析中常遇到。对于通常所见到的正整数n，有(n)4。但在理论上(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。,2.1 递归的概念,例3 Ackerman函数 作业1：采用递归方式实现Ackerman函数,2.1 递归的概念,例4

10、 排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。 从n个不同元素中任取m(mn)个元素，按照一定的顺序排列起叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。 如1,2,3三个元素的全排列为： 1，2，3 1，3，2 2，1，3 2，3，1 3，1，2 3，2，1,集合X中元素的全排列记为perm(X)。 (r)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r得到的排列。,2.1 递归的概念,例4 排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 集合X

11、中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。,2.1 递归的概念,例4 排列问题(http:/ perm(R): (r1)perm(R1) (r2)perm(R2) 即： (r1)(r2) (r2)(r1),当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)

12、，(r2)perm(R2)，(rn)perm(Rn)构成。,n=3 perm(R): (r1)perm(R1) (r2)perm(R2) (r3)perm(R3) 即：(r1) perm(R2R3) (r2)perm(R1R3) (r3)perm(R1R2) 最终：(r1)(r2)（r3) (r1)(r3)(r2) (r2)(r1)(r3) (r2)(r3)(r1) (r3)(r1)(r2) (r3)(r2)(r1),2.1 递归的概念,例4 排列问题,/perm函数：perm(Object list ,int k,int m) /作用：输出数组list中，前缀为顺序的前k个元素，后缀为后m-

13、k个元素的全排列，所组成的排列 /参数：list数组，要进行排列的元素 / k，数组下标0-（k-1）为前缀 / m，数组下标0-m为要进行排列的元素 /说明：若要对list中的所有元素进行排列，k应为0，m应为数组上界,2.1 递归的概念,例4 排列问题,public static void perm(Object list ,int k,int m) /若所有要排列元素都为前缀，则依次输出 if(k=m) for (int i=0;i=m;i+) System.out.print(listi+“ “); System.out.println(); /否则，前缀增1，后缀减1 else/依次

14、将原后缀中任一个元素放入到前缀中，得到新的前后缀，进行递归 for(int i=k;i=m;i+) swap(list,k,i); perm(list,k+1,m); swap(list, k, i); ,2.1 递归的概念,例4 排列问题,public static void swap(Object list,int k,int m ) Object t; t=listk; listk=listm; listm=t; int main() int list= 1,2,3; perm(list,0,2); return 0; ,2.1 递归的概念,例4 排列问题 作业2：采用递归方式实现排列问

15、题,2.1 递归的概念,例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。,例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,2.1 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将

16、最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 注意：m的取值范围为1,)，我们可分段讨论。 m=1 1n,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。,(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1m-1 的划分组成。,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,2.1

17、 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,2.1 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,6； 5+

18、1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,例：q(6,3)=q(3,3)+q(6,2),2.1 递归的概念,例5 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,2.1 递归的概念,例5 整数划分问题,/函数：q(int n,int

19、m) /作用：用来得到正整数n，最大加数不大于m的划分个数 public static int q(int n,int m) /若正整数或最大加数小于1，则返回0 if(n1|m1) return 0; /若正整数或最大加数等于1，则划分个数为1（n个1相加） if(n=1|m=1) return 1; /若最大加数实际上不能大于正整数n，若大于则划分个数等于最大加数为n的划分个数 if(nm) return q(n,n); /若正整数等于最大加数，则划分个数等于 if (n=m) return 1+q(n,n-1); return q(n,m-1)+q(n-m,m); ,2.1 递归的概念,

20、例5 整数划分问题 作业3：采用递归方式实现整数划分问题,2.1 递归的概念,例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,2.1 递归的概念,例6 Hanoi塔问题 一个简单的解法： 假设塔座a,b,c排成一个三角形，a b c

21、 a构成一顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移动到顺时针方向的下一个塔座上；若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移动到另一个塔座上去。 以上算法如何理解？ 注意： 圆盘数目不同，要ab，塔座的顺序也不同。 奇数：abca 偶数：acba,非递归解法,若是奇数次移动，则将最小的圆盘移到顺时针方向的下一塔座上； 若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移到另一塔座上去。,当n为奇数时，目的塔座是b，按顺时针方向移动； 当n为偶数时，目的塔座是c，按逆时针方向移动。,在问题规模较大时，较难找到一般的方法，

22、因此我们尝试用递归技术来解决这个问题。,当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。,2.1 递归的概念,例6 Hanoi塔问题,public static void hanoi(int n, int a, i

23、nt b, int c) /将塔座a上自下而上，由大到小叠放在一起的n个圆盘依移动规 /则移至塔座b上并仍按同样顺序叠放。 if (n 0) hanoi(n-1, a, c, b); /在移动过程中，以塔座c作为辅助塔座 move(a,b); /将塔座a上编号为n的圆盘移至塔座b上 hanoi(n-1, c, b, a); ,2.1 递归的概念,例6 Hanoi塔问题 作业4：画图表示Hanoi塔问题 关键：为算法建立递归调用工作栈,2.1 递归的概念,通常，在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事： （1）将所有实参指针、返回地址等信息传递给被调用算法； （2）为被

24、调用算法的局部变量分配存储区； （3）将控制转移到被调用算法的入口。 在从被调用算法返回调用算法时，系统也相应地要完成三件事： （1）保存被调用算法的计算结果； （2）释放分配给被调用算法的数据区； （3）依照被调用算法保存的返回地址将控制转移到调用算法。,系统在实现子程序的调用时, 要用栈方式管理调用子程序时的返回地址。子程序调用的内部实现为两个方面。,2.1 递归的概念,当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。 注意：信息传递和控制转移必须通过栈来实现。重要的是数据栈和工作栈。 递归算法的实现类似于多个算法的嵌套调用，只不过调用算法和被调用算法是同一个算法。 为了保证递归调

25、用正确执行，系统要建立一个递归调用工作栈，为各层次的调用分配数据存储区。 一个递归过程的执行类似于多个子程序的嵌套调用, 递归过程是自己调用自己本身代码。如果把每一次的递归调用视为调用自身代码的复制件, 则递归实现过程基本上和一般子程序的实现相同。,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递

26、归，只不过人工做了本来由编译器做的事情，优化效果不明显（常用方法！）。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,递归小结,讨论：,找出n个自然数(1,2,.,n)中取r个数的组合。,int a100; void comb(int m,int k) for(int i=m;i=k;i-) ak=i; if(k1) comb(i-1,k-1); else for(int j=a0;j0;j-) coutaj ; coutendl; int main() int n=5,r=3; a0=r; co

27、mb(n,r); ,n=5，r=3时，从大到小 排列的组合数为： 5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1,分治法的基本思想,基本思想 当要求解一个输入规模n相当大的问题时，直接求解往往是非常困难的，甚至没法求出。正确的方法是, 首先应仔细分析问题本身所具有的特性，然后根据这些特性选择适当的设计策略来求解。 在将这n个输入分成k个不同子集合的情况下，如果能得到k个不同的可独立求解的子问题，而且在求解之后，还可找到适当的方法把它们合并成整个问题的解，那么，可考虑使用分治法来求解。,分治法的适用条件,分治法所能解决的问题

28、一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独

29、立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,边界条件： 非递归定义的初始值,递归方程：递归定义式,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、从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,分治法的复杂性分析（了解）,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,注意

31、：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。,主定理,注意：主定理的三种情况并没有覆盖所有f(n)，存在某些f(n)不满足以上任何一种情况的条件，则此时就不能用主方法求解递推试。,采用分治法求解问题通常得到一个递归算法，分析相应算法的时间复杂性，往往可得到如下的递归式： T(n)=kT(n/m)+cnb, T(1)=c 显然可以直接使用主方法得到如下定理：,例：,T(n)=16T(n/4)+n T(n)=T(

32、3n/7)+1 T(n)=7T(n/2)+n2,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。,二分搜索技术（回忆查找算法）,给定已按升序排好序

33、的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。 分析：,该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法（注意：C+程序！程序有问题吗？）： template int BinarySearch(Type a, const Type ,算法复杂度分析： 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环

34、被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x ,二分搜索技术,大整数的乘法,考虑计算机组成原理课程中关于基本运算的说法： 1.加法和乘法是基本运算，Why? 2.减法和除法如何实现？ 3.如果实现加法和乘法的计算数超过了机器表示的范围，How to do? 4.精

35、确表示运算时，必须用软件来实现！,大整数运算面临的问题： （1）直接以整数运算，可能超出硬件整数表示范围。 （2）若以浮点数表示，不能精确的表示大整数及其运算结果。 所以，采用某种算法来实现大整数运算是非常必要的。,大整数（二进制整数）的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法（a、b、c、d分段均为n/2位！并假设n为2的幂数！）:,X = Y = X = a 2n/2 + b Y = c 2n/2 + d(why?) XY = ac 2n + (ad+bc) 2n/2 + bd （式1）,a,b,c,d,复杂度分析 T(n)=O

36、(n2) 没有改进,将每2个1位数的乘法或加法看作一步运算,关键：减少乘法次数！,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法: 一种改进方法,XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。 XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd （式3） XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd （式4）,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进 递归方程组解的渐进阶的求法套用公

37、式法,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,大整数的乘法,大整数的乘法,大整数的乘法,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2) 效率太低 分治法: O(n1.59) 较大的改进 更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。 最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。 http:/ 个元素所需的计算时间为O(n3),

38、传统方法：O(n3),Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,传统方法：O(n3) 分治法:,由此可得：,复杂度分析 T(n)=O(n3),（式2） （式3） （式4）（式5）,关键：减少乘法次数！,Strassen矩阵乘法,传统方法：O(n3) 分治法:,为了降低时间复杂度，必须减少乘法的次数。,复杂度分析 T(n)=O(nlog7) =O(n2.81)较大的改进,Strassen矩阵乘法,Strassen矩阵乘法,传统方法：O(n3) 分治法: O(n2.81) 更快的方法?,Hopcroft和K

39、err已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。,棋盘覆盖,在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,问题：在

40、任何一个2k2k的棋盘覆盖中，用到的L型骨牌个数是多少？,（4k-1）/3个！,棋盘覆盖,考虑：使用分治策略，求解棋盘覆盖问题 当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,下面讨论棋盘覆盖问题中数据结构的设计。 （1）棋盘：可以用一个二维数组boardsizesize表示一个棋盘，其中，size=2k。为了

41、在递归处理的过程中使用同一个棋盘，将数组board设为全局变量； （2）子棋盘：整个棋盘用二维数组boardsizesize表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示； （3）特殊方格：用boarddrdc表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标; （4） L型骨牌：一个2k2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。,棋盘覆盖问题,public class Chess private int board; /用来表示棋盘 private int boardSize;

42、/表示棋盘的大小为2的多少次方 private int dr,dc; /棋盘中特殊方格的位置（行号、列号） private int tile;/骨牌标号 public Chess() board=new int11; dr=0;dc=0;boardSize=0; ,public Chess(int r,int c,int s) int n; n=(int) Math.pow(2, s); if (n=r | n=c) System.out.println(“初始化参数错误！“); else board=new intnn; dr=r;dc=c; boardSize=s; ,public voi

43、d Print() for(int i=0;iMath.pow(2, this.boardSize);i+) for(int j=0;jMath.pow(2, this.boardSize);j+) System.out.print(String.format(“%3d|“, this.boardij); System.out.println(); public static void main(String args) Chess c1= new Chess(3,4,3); c1.chessBoard(0, 0, c1.dc, c1.dr, (int)Math.pow(2,c1.boardS

44、ize); c1.Print(); ,/函数参数说明： /tr：棋盘左上角方格的行号； /tc：棋盘左上角方格的列号； /dr：特殊方格所在的行号； /dc：特殊方格所在的列号； /size：2k,棋盘规格为2k2k。 public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size=1) return; int t=tile+, s = size/2; / t:L型骨牌号,s分割棋盘 / 覆盖左上角子棋盘 if(drtr+s ,/ 覆盖右上角子棋盘 if (dr=tc+s) / 特殊方格在此棋盘中 chessB

45、oard(tr, tc+s, dr, dc, s); else / 无特殊方格，用t号骨牌覆盖左下角 boardtr + s - 1tc + s = t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr=tr+s ,/ 覆盖右下角子棋盘 if (dr=tr+s ,棋盘覆盖,void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子

46、棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角,boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s ,复杂度分析 T(n)=O(4k) 渐进意义下的最优算法,棋盘覆盖,其中用一个二维整型数组board表示棋盘。 Board00是棋盘的左上角方格。 Tile是算法中的一个全局整型变量，用来表示L型骨

47、牌的编号，其初始值为0。 算法的输入参数是： tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:size=2k 棋盘规格为2k2k,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,棋盘覆盖,合并排序,基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。,void MergeSort(Type a, int left, int right) if (leftright) /至少有2个元素 int i=(left+right)/2; /取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到数组b copy(a, b, left, right); /复制回数组a ,合并排序算法是用分治策略实现对n个元素进行排序的算法 http:/zh.wikipedia.org/wik