第2章-递归与分治策略课件

第2章 递归与分治策略将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/4)T(n/4)T(n/4)T(n/4)T(n)=对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法2.1 递归的概念直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。例1 阶乘函数阶乘函数可递归地定义为：边界条件边界条件递推方程递推方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。第n个阶乘函数可递归地计算如下：public static int factorial(int n)if(n=0)return 1;return n*factorial(n-1);类成员访问级别为公有，在程序的任何部分都可访问静态类方法，只有一份拷贝，调用为方法名（实际参数）例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：public static int fibonacci(int n)if(n m1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。以上的关系给出了计算q(n,m)的递推式如下：(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。public static int q(int n,int m)if（(n 1)(m 1)）return 0;if（(n=1)(m=1)）return 1;if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到b，移动规则不变，求移动步数最小的方案。递归小结优点：优点：结构清晰，可读性强，而且容易用数学归纳结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是耗费的计递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。算时间还是占用的存储空间都比非递归算法要多。分析递归算法时间效率的通用方案1.决定用哪个（哪些）参数作为输入规模的度量。2.找出算法的基本操作。3.检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这种可能，则必须对最坏情况、最好情况和平均情况做单独研究。4.对于算法的基本操作执行次数，建立一个递推关系以及相应的初始条件。5.解这个递推式，或者至少确定它的解的增长次数。我们应该谨慎使用递归算法，因为他们的简洁可能我们应该谨慎使用递归算法，因为他们的简洁可能会掩盖他们的低效率。会掩盖他们的低效率。算法可视法算法可视法除了算法的数学分析和经验分析，还有第三种研究算法的方法。我们称之为算法可视法（算法可视法（使用图形来传达关于算法的一些有用的信息）。这些信息可以是关于算法操作的图示，比如算法对于不同输入的性能，算法的执行速度与求解相同问题的其他算法的比较。为了达到这个目标，算法可视法使用图形元素（点、线段、二维或三维柱状图等）来表现算法操作中的一些“令人关注的结果”。算法可视法有两种主要的变种：静态算法可视法 动态算法可视法，也称为算法动画算法动画。静态算法可视法使用一系列静态的图形来显示一个算法的操作过程。而算法动画则以一种连续的、类似电影的表达方式来展现算法操作过程。在算法可视领域所做的早期努力可以追溯到20世纪70年代。1981年是该技术的分水岭，算法可视的经典诞生了，它是一部长30分钟的有声彩色电影，名为排序比赛（Sorting out Sorting）。它包含了9种著名排序算法的动态展现，并且提供了它们之间相对速度的十分有说服力的演示。算法动画通用系统2.22.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);/将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的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)。2.3二分搜索技术分析：如果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。据此容易设计出二分搜索算法二分搜索算法：public static int binarySearch(int a,int x,int n)/在 a0=a1=.=an-1 中搜索 x /找到x时返回其在数组中的位置，否则返回-1 int left=0;int right=n-1;while(left amiddle)left=middle+1;else right=middle-1;return-1;/未找到x 算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。T(n)=T(n/2)+1T(n)=T(n/2)+1时间复杂度分析？时间复杂度分析？X=Y=X=a 2n/2+b Y=c 2n/2+d XY=ac 2n+(ad+bc)2n/2+bd 2.42.4大整数的乘法大整数的乘法 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)效率太低u分治法:abcd复杂度分析复杂度分析T(n)=O(n2)没有改进没有改进n/2位n/2位n/2位n/2位XY=ac 2n+(ad+bc)2n/2+bd 为了降低时间复杂度，必须减少乘法的次数。1.XY=ac 2n+(a-c)(b-d)+ac+bd)2n/2+bd2.XY=ac 2n+(a+c)(b+d)-ac-bd)2n/2+bd复杂度分析复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2)效率太低u分治法:O(n1.59)较大的改进u更快的方法?如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。练习题1.用分治算法来计算21011130.2.在统计大整数乘法算法的乘法次数时，问什么不把乘以2n时所做的乘法包含进去？3.在用笔算算法计算两个n位数乘法的时候，需要做多少次一位数的加法（可以忽略进位）？2.5Strassen矩阵乘法A和B的乘积矩阵C中的元素Ci,j定义为:若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)没有改进没有改进u分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进Strassen矩阵乘法u传统方法：O(n3)u分治法:O(n2.81)u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。2.6棋盘覆盖在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。public 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 tr+s&dc tc+s)/特殊方格在此棋盘中 chessBoard(tr,tc,dr,dc,s);else/此棋盘中无特殊方格 /用 t 号L型骨牌覆盖右下角 boardtr+s-1tc+s-1=t;/覆盖其余方格 chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘 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&dc=tr+s&dc=tc+s)/特殊方格在此棋盘中 chessBoard(tr+s,tc+s,dr,dc,s);else/用 t 号L型骨牌覆盖左上角 boardtr+stc+s=t;/覆盖其余方格 chessBoard(tr+s,tc+s,tr+s,tc+s,s);复杂度分析复杂度分析 T(n)=O(4k)渐进意义下的最优算法2.72.7合并排序合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。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 例如：复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法消除递归后的合并排序算法如下：Public static void mergesort(Comparable a)Comparable b=new Comparablea.length;int s=1;while(sa.length)mergePass(a,b,s);/将a数组中长度为s的相邻两子段合并到数组b /mergePass用于合并排好序的相邻数组段 s+=s;mergePass(b,a,s);/将b数组中长度为s的相邻两子段合并到数组a s+=s;消除递归后的合并排序算法mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97算法mergePassPublic static void mergePass(Comparable x,Comparable y,int s)/合并大小为s的相邻子数组段 int i=0;while(i=x.length-2*s)/合并大小为s的相邻2段子数组 merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;if(i+sx.length)/剩下的元素大于s小于2s merge(x,y,i,i+s-1,x.length-1)；else /剩下的元素=一个s for(int j=i;jx.length;j+)yj=xj;算法mergePublic static void merge(Comparable c,Comparable d,int l ,int m,int r)/合并合并cl:m和和cm+1:r到到dl:r int i=l;j=m+1;k=l;while(i=m)(j=r)if(pareTo(cj)m)/说明后子段中有元素，将其放入说明后子段中有元素，将其放入d中中 for(int q=j;q=r;q+)dk+=cq;else /说明前子段中有元素，将其放入说明前子段中有元素，将其放入d中中 for(int q=i;q=m;q+)dk+=cq;思考：自然合并排序算法思考：自然合并排序算法合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定思考题：思考题：给定给定有序表有序表A1:n，修，修改合并排序算法，求出该有序表改合并排序算法，求出该有序表的逆序对数。的逆序对数。2.8快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。private static void qSort(Comparable a,int p,int r)if(p=x的元素交换到右边区域 /将=x的元素交换到左边区域 while(true)while(a+pareTo(x)0);/j往左找较小元素 if(i=j)break;MyMath.swap(a,i,j);ap=aj;aj=x;return j;private static int randomizedPartition(Comparable a,int p,int r)int i=random(a,p,r);MyMath.swap(a,i,p);return partition(a,p,r);快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)&稳定性：不稳定稳定性：不稳定2.9线性时间选择给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素private static Comparable randomizedSelect(Comparable a，int p,int r,int k)if(p=r)return ap;int i=randomizedpartition(a,p,r)；j=i-p+1;/求出元素个数 if(k=j)return randomizedSelect(a,p,i,k);/说明第k小元出现在前半段 else return randomizedSelect(a,i+1,r,k-j);/说明第k小元出现在后半段，并且为第k-j元 在最坏情况下，算法randomizedSelect需要O(n2)计算时间，但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。思考：在最坏情况下能否找到O(n)时间的算法？如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下在最坏情况下用O(n)时间完成选择任务。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。l将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。l递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩1/4。private static Comparable select(int p,int r,int k)if(r-p5)/用某个简单排序算法对数组ap:r排序;bubbleSort(p,r);/冒泡排序 return ap+k-1;/直接返回第k小元 /将ap+5*i至ap+5*i+4的第3小元素 /与ap+i交换位置;/找中位数的中位数，r-p-4即上面所说的n-5 for(int i=0;i=(r-p-4)/5;i+)int s=p+5*i,t=s+4;for(int j=0;j3;j+)bubble(s,t-j);MyMath.swap(a,p+i,s+2);Comparable x=select(p,p+(r-p-4)/5,(r-p+6)/10);int i=partition(p,r,x),j=i-p+1;if(k=j)return select(p,i,k);else return select(i+1,r,k-j);复杂度分析复杂度分析 T(n)=O(n)上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。2.112.11循环赛日程表循环赛日程表设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。m=1,s=1,n=4m=2,s=2,n=2,t=1m=4,s=3,n=1 t=1,t=2,t=3,t=4 t=2 t=1结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings演讲人：XXXXXX 时 间：XX年XX月XX日