算法分析设计递归与分治策略精.ppt
算法分析设计递归与分治策略第1页，本讲稿共20页算法总体思想分治法的设计思想是，将一个难以直接解决的大问题，分分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的问题，以便各个击破，分而治之。割成一些规模较小的问题，以便各个击破，分而治之。如果由分治法产生的子问题是原问题的较小规模，如果由分治法产生的子问题是原问题的较小规模，则可以用递归技术解决。则可以用递归技术解决。第2页，本讲稿共20页将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。第3页，本讲稿共20页算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)第4页，本讲稿共20页算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)第5页，本讲稿共20页2.1 递归的概念直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。第6页，本讲稿共20页2.1 递归的概念例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为：边界条件边界条件递归方程递归方程边界条件（非递归定义）与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。第7页，本讲稿共20页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)构成。第8页，本讲稿共20页2.2 分治法的基本思想分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最最优子结构性质优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心贪心算法算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。分治法的适用条件：分治法的适用条件：第9页，本讲稿共20页分治法的复杂性分析：分治法的复杂性分析：一个分治法将规模为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)。第10页，本讲稿共20页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。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。第11页，本讲稿共20页2.3 二分搜索技术给定已按升序排好序的给定已按升序排好序的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)。思考题：给定思考题：给定思考题：给定思考题：给定a a，用二分法设计出求，用二分法设计出求，用二分法设计出求，用二分法设计出求a an n的算法。的算法。的算法。的算法。第12页，本讲稿共20页2.4 合并排序基本思想：基本思想：将待排序元素分成大小大致相同的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)渐进意义下的最优算法第13页，本讲稿共20页算法分析：2.4 合并排序算法mergeSort的递归过程只是将待排序集合一分为二，直至待排序的集合只剩下1个元素为止。然后不断合并2个排好序的数组段。消去递归：首先将数组中的相邻元素两两配对，用合并算法将其排序，构成n/2组长度为2的排好序的子数组段，然后将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。第14页，本讲稿共20页2.4 合并排序例如：初始序列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第15页，本讲稿共20页2.4 合并排序按此思想消去递归后的合并排序算法可描述如下：public static void mergeSort(Comparable a)Comparable b=new Comparablea.length;int s=1;while(sa.length)mergePass(a,b,s);/合并到数组b s=s+1;mergePass(b,a,s);/合并到数组a s=s+1;第16页，本讲稿共20页2.4 合并排序其中，算法mergePass用于合并排好序的相邻数组：public static void mergePass(Comparable x，Comparable y,int s)/合并大小为s的相邻子数组 int i;while(i=x.length-2*s)/合并大小为s的相邻2段子数组 merge(x,y,I,i+s-1,i+2*s-1);i=i+2*s;/剩下的元素个数少于2s if(i+sx.length)merge(x,y,I,i+s-1,x.length-1);else/复制到y for(int j=i;jx.length;j+)yj=xj;第17页，本讲稿共20页 public static void merge(Comparable c，Comparable d,int l,int m,int r)/合并c1:m和cm+1:r到d1:r int i=l,j=m+1,k=l;while(i=m)&(j=r)if(pareTo(cj)=0)/如果cim)for(int q=j;q=r;q+)dk+=cq;/cm+1:r的元素个数多 else for(int q=i;q=m;q+)dk+=cq;2.4 合并排序第18页，本讲稿共20页2.4 合并排序算法改进-自然合并排序自然合并排序如果初始数组中，存在多个长度大于1且已经排好序的子数组段。则通过1次线性扫描就可以找出所有这些排好序的子数组段。然后将相邻的排好序的子数组段两两合并。如：初始序列4 8 3 7 1 5 6 2 4 8 3 7 1 5 6 2第一步第二步3 4 7 8 1 2 5 6第三步1 2 3 4 5 6 7 8 第19页，本讲稿共20页算法分析：通常情况下，自然合并排序所需要的合并次数较少。例如：对所给的例如：对所给的n元素数组已经排好序的极端情况，自然合元素数组已经排好序的极端情况，自然合并排序的时间复杂度为并排序的时间复杂度为O(n)，而算法，而算法mergeSort的时间复杂的时间复杂度是度是O(nlogn)。2.4 合并排序第20页，本讲稿共20页
