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

第2章 递归与分治策略,学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。,分治法概述,分治法是一种非常有用的算法技术，它可以用于求解许多算法问题.什么是分治法?,算法总体思想,计算机求解的复杂度与问题的规模有关，回忆：1、2、3n个元素的排序问题；1、2、3n个元素的查找问题；结论：多个元素的排序和查找比较少元素的排序和查找复杂和困难的多！想法：能否将“多个元素的排序和查找”变成数个“较少元素的排序和查找”，分别进行？,算法总体思想,分治法的可行性：如果原问题可以分成k个子问题且子问题都可解并可利用子问题的解求出原问题的解,算法总体思想,问题分解是求解复杂问题时很自然的做法。求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。,将要求解的较大规模的问题分割成k个更小规模的子问题。,算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,算法总体思想,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。-孙子兵法,算法总体思想,通常，由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。由此可知，分治法求解很自然地可用一个递归过程来表示。分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。,2.1 递归的概念,直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,2.1 递归的概念,递归的使用场合：数据结构本身是递归定义的，其实现算法往往是递归算法，比如二叉树和图等；求解过程需要递归，算法描述简捷其易于理解及分析，比如阶乘计算,下面来看几个实例。,在算法设计中使用递归技术，往往使算法的描述简单明了、易于理解、容易编程和验证。在计算机软件领域，递归算法是一种非常重要并且不可或缺的算法。,2.1 递归的概念,例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数列。它可以递归地定义为：,边界条件,递归方程,第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函数却无法找到非递归的定义。,2.1 递归的概念,例3 Ackerman函数A(n，m)的自变量m的每一个值都定义了一个单变量函数（根据m的不同可得到基于n的不同函数！）：m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nm=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 递归的概念,例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 排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。从n个不同元素中任取m(mn)个元素，按照一定的顺序排列起叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。如1,2,3三个元素的全排列为：1，2，31，3，22，1，32，3，13，1，23，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中元素的全排列记为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:/,n=2 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)，(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-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，后缀减1else/依次将原后缀中任一个元素放入到前缀中，得到新的前后缀，进行递归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：采用递归方式实现排列问题,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的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。注意：m的取值范围为1,)，我们可分段讨论。m=11n,(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 递归的概念,例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+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 m)/作用：用来得到正整数n，最大加数不大于m的划分个数public static int q(int n,int m)/若正整数或最大加数小于1，则返回0if(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 递归的概念,例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 a构成一顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移动到顺时针方向的下一个塔座上；若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移动到另一个塔座上去。以上算法如何理解？注意：圆盘数目不同，要ab，塔座的顺序也不同。奇数：abca 偶数：acba,非递归解法,若是奇数次移动，则将最小的圆盘移到顺时针方向的下一塔座上；若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移到另一塔座上去。,当n为奇数时，目的塔座是b，按顺时针方向移动；当n为偶数时，目的塔座是c，按逆时针方向移动。,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。,当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,int 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）为被调用算法的局部变量分配存储区；（3）将控制转移到被调用算法的入口。在从被调用算法返回调用算法时，系统也相应地要完成三件事：（1）保存被调用算法的计算结果；（2）释放分配给被调用算法的数据区；（3）依照被调用算法保存的返回地址将控制转移到调用算法。,系统在实现子程序的调用时,要用栈方式管理调用子程序时的返回地址。子程序调用的内部实现为两个方面。,2.1 递归的概念,当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。注意：信息传递和控制转移必须通过栈来实现。重要的是数据栈和工作栈。递归算法的实现类似于多个算法的嵌套调用，只不过调用算法和被调用算法是同一个算法。为了保证递归调用正确执行，系统要建立一个递归调用工作栈，为各层次的调用分配数据存储区。一个递归过程的执行类似于多个子程序的嵌套调用,递归过程是自己调用自己本身代码。如果把每一次的递归调用视为调用自身代码的复制件,则递归实现过程基本上和一般子程序的实现相同。,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显（常用方法！）。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;comb(n,r);,n=5，r=3时，从大到小排列的组合数为：5 4 35 4 25 4 15 3 25 3 15 2 14 3 24 3 14 2 13 2 1,分治法的基本思想,基本思想当要求解一个输入规模n相当大的问题时，直接求解往往是非常困难的，甚至没法求出。正确的方法是,首先应仔细分析问题本身所具有的特性，然后根据这些特性选择适当的设计策略来求解。在将这n个输入分成k个不同子集合的情况下，如果能得到k个不同的可独立求解的子问题，而且在求解之后，还可找到适当的方法把它们合并成整个问题的解，那么，可考虑使用分治法来求解。,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,边界条件：非递归定义的初始值,递归方程：递归定义式,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);/将各子问题的解合并为原问题的解,分治法的基本步骤,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,分治法的复杂性分析（了解）,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,注意：递归方程及其解只给出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)+nT(n)=T(3n/7)+1T(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是独立的子问题，因此满足分治法的第四个适用条件。,二分搜索技术（回忆查找算法）,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：,该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法（注意：C+程序！程序有问题吗？）：template int BinarySearch(Type a,const Type,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了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.精确表示运算时，必须用软件来实现！,大整数运算面临的问题：（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(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)较大的改进递归方程组解的渐进阶的求法套用公式法,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。,大整数的乘法,大整数的乘法,大整数的乘法,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。,Strassen矩阵乘法,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3),传统方法：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和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。,棋盘覆盖,在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,问题：在任何一个2k2k的棋盘覆盖中，用到的L型骨牌个数是多少？,（4k-1）/3个！,棋盘覆盖,考虑：使用分治策略，求解棋盘覆盖问题当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,下面讨论棋盘覆盖问题中数据结构的设计。（1）棋盘：可以用一个二维数组boardsizesize表示一个棋盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将数组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;/表示棋盘的大小为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(初始化参数错误！);elseboard=new intnn;dr=r;dc=c;boardSize=s;,public void 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.boardSize);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)/特殊方格在此棋盘中chessBoard(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;/分割棋盘/覆盖左上角子棋盘 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型骨牌的编号，其初始值为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个元素进行排序的算法,复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,public static void mergeSort(Comparable 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,合并排序,void mergesort(int a,int left,int right)int b100;if(leftright)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中,合并排序,void merge(int c,int d,int l,int m,int r)int i=l,j=m+1,k=l;while(im)for(int q=j;q=r;q+)dk+=cq;else for(int q=i;q=m;q+)dk+=cq;/merge可在 时间内完成void Copy(int a,int b,int m,int n)for(int i=m;i=n;i+)ai=bi;/copy可在 时间内完成,合并排序,int main()int n,m,a100;cinn;while(n!=0)cinm;for(int i=0;iai;mergesort(a,0,m-1);for(int j=0;jm;j+)coutaj;coutendl;n-;return 0;,合并排序,算法mergeSort的递归过程可以消去。（回忆上学期的方法）,合并排序,合并排序,合并排序,合并排序,/合并排序的非递归算法/对数组a中的所有元素进行合并排序public static void mergeSort(Comparable a)Comparable b=new Comparablea.length;int s=1;/合并的有序数组段的初始大小/有序数组段的长度小于数组长度继续合并while(sa.length)/从下界开始将a中的相邻的长度为s的元素合并排序到b中mergePass(a,b,s);s+=s;/待合并的有序数组段的长度增加一倍mergePass(b,a,s);s+=s;/待合并的有序数组段的长度增加一倍,/合并大小为s的相邻子数组/从数组下界开始，将数组x中相邻的长度为s的数组段合并排序到y中public static void mergePass(Comparable x,Comparable y,int s)int i=0;while(i=x.length-2*s)/合并大小为s的相邻2段子数组x