递归与分治策略讲义课件

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,2,章 递归与分治策略,Recursion ,divide and conquer method,学习要点:,理解递归的概念。,掌握设计有效算法的分治策略。,通过下面的范例学习分治策略设计技巧。,（1）二分搜索技术；,（2）合并排序,（,3,）快速排序；,（,4,）最接近点对问题；,递归,(recursion),是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。,递归程序不能无限制地自我调用，否则就会永不终止，递归程序必须有终止条件。,尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用递归过程来描述它们不仅非常自然， 而且证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。,2.1,递归,构成递归需具备的条件,:,1.,不能无限制地调用本身，须有个出口，化简为非递归状况处理,(,边界条件,);,2.,子问题与原问题为同一类型,且更为简单,(,递归模式,).,递归程序的书写方式,:,Procedure(,parameter list,),if,return(initial value);,else,return(,parameter exchange,);,end,例,1,阶乘函数,阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,int,factorial,(int n),if,(n= 0),return,1;,return,n*,factorial,( n-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,=5),递归程序结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,求斐波那齐数列的,非递归程序：,void,fibonacci,(,int,n),int prev,now,next,j;,if,(n=1),return(,1,);,else,prev=,1,;,now,=,1,;,for(j=2;j,=,=,1,1,2,2,n,a,a,n,a,a,n,n,n,如果,如果,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题，即该问题具有,最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解；,该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑,贪心算法,或,动态规划,。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用,动态规划,较好。,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);,/,将各子问题的解合并为原问题的解,分治法的算法设计模式,问,题,的,规,模,阀值,设问题,P(n),分解成,k,个规模为,n/m,的子问题,阀值,n0=1,求解,P(1),的,时间耗费为,O(1).,将,P(n),分解及合并成,P(n),的解的时间为,f(n),则,分治法解规模为,n,的问题的,最坏时间,复杂性函数,T(n),满足,:,Divide-and-Conquer,(P),if ( |P|=n0) Adhoc(P);,divide P into smaller subinstances P1 ,P2,. ,Pk;,for (i = 1;i 1,O(1),分治法的复杂性分析,T(n) =,kT(n / m) + f(n),= k(kT(n / m,2,) + f(n / m) + f(n),= k,2,T(n / m,2,) + kf(n / m) + f(n),= k,3,T(n / m,3,) + k,2,f(n / m,2,) +kf(n / m),+ f(n) =,这里,m,a,= n，,所以,a = log,m,n。,于是：,k,a,= k = n = n,p,，,这里,p = log,m,k。,log,m,n,log,m,k,由此可知，,T(n),的首项是,n,的常数幂。,T(n)=,T(1)=O(1) n=1,T(n)=kT(n/m)+f(n) n1,a1,j=0,= k,a,T(1) + k,j,f(n / m,j,),= k,a,+ k,j,f(n / m,j,),a1,i=0,解得,:,二分搜索技术,问题描述,已知一个,排好次序,的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，若是，则,返回,该元素在表中的位置，否则，,返回,-1,。,一般解决方法（从头到尾查找一遍）,a,1,a,2,a,3,a,4,a,n,x,最坏情况下，顺序搜索算法需要,O(,n,),次比较。,分析：,如果,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,。,分析：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题,;,分解出的子问题的解可以合并为原问题的解；,分解出的各个子问题是相互独立的。,二分搜索有序表的递归式算法,int,recursive_binary_search,( int a , int left , int right , int T ) int k , mid; if ( left right ) k = -1 ;,/*,数组中不存在,T,，返回,-1,else,mid = ( left + right ) / 2 ;,/*,取中点下标,if ( amid = T ) k = mid ;,else if (amid T ) k =,recursive_binary_search,( a , mid+1 , right , T ) ; else k =,recursive_binary_search,( a , left , mid-1 ,T ) ; return ( k ) ;,/*,返回,T,在数组,a,中位置的下标值,二分搜索有序表的非递归式算法,int,binary_search,( int a , int n , int T ) int left , right , mid , k ; left = 0 ; right = n - 1 ; k = -1 ; while ( left T ) right = mid-1; else left = mid+1 ; return ( k ) ;,对于有序数组：,（,05,13,19,21,37,56,64,75,80,88,92,）,T=21,的查找过程：,05 13 19 21 37 56 64 75 80 88 92,left,right,mid,05 13 19 21 37 56 64 75 80 88 92,left,right,mid,05 13 19 21 37 56 64 75 80 88 92,left,right,mid,T=85,的查找过程：,05 13 19 21 37 56 64 75 80 88 92,left,right,mid,mid T , left=mid +1,left,right,mid,mid T , right=mid -1,left,right,二分搜索有序表的算法分析,n,n/2,n/2,n/4,n/4,n/4,n/4,1,1,1,1,log n,+ 1,二分搜索的每次循环查找区间减半，查找区间构成一棵二叉树，最坏的情况是一直走到二叉树的叶子。因此算法的复杂度为,log n + 1,。,二分搜索有序表的算法分析,我们也可以根据递归算法列出如下的递归方程：,T(n) =,T(,n/2) + 1 n 1,1 n = 1,由前面所学的求解递归方程的一般结论,有：时间,复杂度为,O(log n),。,每执行一次算法的,while,循环， 待搜索数组的大小减少一半。因此，在最坏情况下，,while,循环被执行了,O(logn),次。循环体内运算需要,O(1),时间，因此整个算法在最坏情况下的计算时间复杂性为,O(logn),。,归并排序,（,1,）,划分,：将待排序序列,r,1,r,2, ,r,n,划分为两个长度相等的子序列,r,1, ,r,n,/2,和,r,n,/2,1, ,r,n,；,（,2,）,求解子问题,：分别对这两个子序列进行排序，得到两个有序子序列；,（,3,）,合并,：将这两个有序子序列合并成一个有序序列。,二路归并排序是成功应用分治法的一个完美例子，其分治策略是：,所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。,r,1, ,r,n,/2,r,n,/2,1, ,r,n,划分,r,1, ,r,n,/2,r,n,/2,1, ,r,n,递归处理,r,1,r,n,/2,r,n,/2,1,r ,n,合并解,（,2-,路）归并排序的分治思想,初始序列,a 8 4 5 6 2 1 7 3,归并到,b 4 8 5 6 1 2 3 7,复制到,a 4 8 5 6 1 2 3 7,归并到,b 4 5 6 8 1 2 3 7,复制到,a 4 5 6 8 1 2 3 7,归并到,b 1 2 3 4 5 6 7 8,复制到,a 1 2 3 4 5 6 7 8,归并 4,5,6,8 1,2,3,7 从两个序列的头部开始归并：,4与1比较，1被移到结果序列；4与2比较，2被移入结果序列,4与3比较，3被放入结果序列；4和7比较，4被放入结果序列,5和7比较.，,例,:,归并过程,MergeSort,的递归过程是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。,算法,归并排序,temlplate ,void,MergeSort,(Type a, int left, int right), if (1eft right),/,至少有,2,个元素,int i = (left + right ) /2;,/,取中点,MergeSort,(a, 1eft, i),；,/,归并排序前半个子序列,MergeSort,(a, i+1, right),；,/,归并排序后半个子序列,Merge(a, b, 1eft, i, right),；,/,从,a,合并到数组,b,copy(a, b, left, right);/,复制回数组,a,C+描述,合并函数,MERGE,的实现,A(1),A(2),A(3),A(n/2),A(n/2+1),A(n),数组,A,已分类序列,A,已分类序列,B,辅助,数组,B,比较大小,小值,A(1),比较大小,小值,A(n/2+1),数组,A,剩余已分类元素,A(1),A(n/2+1),算法如下,template,void merge(T,c, T d ,int l, int m , int r),/把cl:m,cm,+1,r归并到dl,r,int: i=,l,/第段的游标,j=m+1,/第二段的游标,k=,l,;,/结果的游标,/只要段中存在i和j,则不断进行归并,while (i=m)&(j=r),if cim) for (int q=j; q=r;q+),dk+=cq；,else for(int q=i ;q1 , c,是常数,当n=2,k,时，可得,T(n)=2(2T(n/4)+cn/2)+cn,= 2,2,T(n/,2,2,)+2cn,=4(2T(n/8)+cn/4)+2cn,= 2,3,T(n/,2,3,)+3cn,=2,k,T(n/2,k,)+kcn,=2,k,T(1)+kcn,=an+cnlogn,T(n)=O(nlogn),归并排序,时间复杂度,最坏时间复杂度：,O(nlogn,),平均时间复杂度：,O(nlogn,),辅助空间：,O(n,),T(n)=O(nlogn),渐进意义下的最优算法,算法,mergeSort,的递归过程可以消去。,初始序列,49 38 65 97 76 13 27,38 49 65 97 13 76 27,第一步,第二步,38 49 65 97 13 27 76,第三步,13 27 38 49 65 76 97,消去递归后的合并排序算法,temlplate ,voidmergesort( typea,intn),type,*b=new,type,n,;,int,s,;,s,=1;,while(,s,n),mergepass(a,b,n,s,);,s+,=,s,;,mergepass(b,a,n,l);,s,+,=,s,;,C+描述,快速排序,（,1,）,划分,：选定一个记录作为,轴值,，以轴值为基准将整个序列划分为两个子序列,r,1,r,i,-1,和,r,i,+1,r,n,，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；,（,2,）,求解子问题,：分别对划分后的每一个子序列递归处理；,（,3,）,合并,：由于对子序列,r,1,r,i,-1,和,r,i,+1,r,n,的排序是就地进行的，所以合并不需要执行任何操作。,快速排序也是基于分治技术的重要排序算法，和归并排序不同的是：,归并排序是按照记录在序列中的位置对序列进行划分的，而快速排序是按照记录的值对序列进行划分的。,快速排序的分治策略是：,r,1, ,r,i,-,1,r,i,r,i,+1, ,r,n,均,r,i,轴值 均,r,i,位于最终位置,快速排序是,冒,泡排序的一种改进方法,，,是由C.A.R. Hoare于,1962,年提出的,。,在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，而总的比较和移动次数较少。,快速排序的分治思想,13,65,27,50,38,49,55,j,i,j,j,13,65,27,50,38,49,55,j,i,i,i,13,65,27,50,38,49,55,i,j,j,j,一次划分示例,以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。,13,27,50,38,49,55,j,i,i,j,13,65,27,50,38,49,55,65,算法,一次划分,int Partition,(,int r , int first, int end,),i=first; j=end; /,初始化,while,(,ij,),while,(,ij & ri= rj,),j,-,；,/,右侧扫描,if,(,ij,),rirj; /,将较小记录交换到前面,i+;,while,(,ij & ri= rj,),i+,；,/,左侧扫描,if,(,ij,),rjri; /,将较大记录交换到后面,j,-,;,retutn i; / i,为轴值记录的最终位置,C+描述,以第一个记录作为轴值，对待排序序列进行划分的过程为：,（,1,）,初始化,：取第一个记录作为基准，设置两个参数,i,，,j,分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；,（,2,）,右侧扫描过程,：将基准记录与,j,指向的记录进行比较，如果,j,指向记录的关键码大，则,j,前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序），若,i,j,，则将基准记录与,j,指向的记录进行交换；,（,3,）,左侧扫描过程,：将基准记录与,i,指向的记录进行比较，如果,i,指向记录的关键码小，则,i,后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序），若,i,j,，则将基准记录与,i,指向的记录交换；,（,4,）,重复,（,2,）（,3,）步，直到,i,与,j,指向同一位置，即基准记录最终的位置。,算法,快速排序,void,QuickSort,(,int r , int first, int end,),if,(,firstend,),pivot=Partition,(,r, first, end,),;,/,问题分解，,pivot,是轴值在序列中的位置,QuickSort,(,r, first, pivot,-,1,),;,/,递归地对左侧子序列进行快速排序,QuickSort,(,r, pivot+1, end,),;,/,递归地对右侧子序列进行快速排序,C+描述,T,(,n,),2,T,(,n,/2,),n,2,(,2,T,(,n,/4,),n,/2,),n,4,T,(,n,/4,),2,n,4,(,2,T,(,n,/8,),n,/4,),2,n,8,T,(,n,/8,),3,n, ,nT,(,1,),n,log,2,n,O,(,n,log,2,n,),因此，时间复杂度为,O,(,n,log,2,n,),。,在,最好情况,下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有,n,个记录的序列中，一次划分需要对整个待划分序列扫描一遍，则所需时间为,O,(,n,),。设,T,(,n,),是对,n,个记录的序列进行排序的时间，每次划分后，正好把待划分区间划分为长度相等的两个子序列，则有：,因此，时间复杂度为,O,(,n,2,),。,在,最坏情况,下，待排序记录序列,正序或逆序,，每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空）。此时，必须经过,n,-1,次递归调用才能把所有记录定位，而且第,i,趟划分需要经过,n,-,i,次关键码的比较才能找到第,i,个记录的基准位置，因此，总的比较次数为：,在,平均情况,下，设基准记录的关键码第,k,小（,1,kn,），则有：,这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为,O,(,n,log,2,n,),。,最接近点对问题,给定平面上,n,个点的集合,S,，找其中的一对点，使得在,n,个点组成的所有点对中，该点对间的距离最小。,为了使问题易于理解和分析，先来考虑一维的情形。此时，,S,中的,n,个点退化为,x,轴上的,n,个实数,x1,x2,xn,。最接近点对即为这,n,个实数中相差最小的,2,个实数。,假设我们用,x,轴上某个点,m,将,S,划分为,2,个子集,S1,和,S2,，基于,平衡子问题,的思想，用,S,中各点坐标的中位数来作分割点。,递归地在,S1,和,S2,上找出其最接近点对,p1,p2,和,q1,q2,，并设,d=min|p1-p2|,|q1-q2|,，,S,中的最接近点对或者是,p1,p2,，或者是,q1,q2,，或者是某个,p3,q3,，其中,p3S1,且,q3S2,。,能否在线性时间内找到,p3,q3,？,最接近点对问题,如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，,即,p3(m-d,m，q3(m,m+d,。,由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，,如果(m-d,m中有S中的点，则此点就是S1中最大点。,因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。,从而我们用线性时间就可以将S1的解和S2的解合并成为S的解,。,能否在线性时间内找到,p3,q3,？,最接近点对问题,下面来考虑二维的情形。,选取一垂直线,l:x,=m,来作为分割直线。其中,m,为,S,中各点,x,坐标的中位数。由此将,S,分割为,S1,和,S2,。,递归地在,S1,和,S2,上找出其最小距离,d1,和,d2,，并设,d=mind1,d2,，,S,中的最接近点对或者是,d,，或者是某个,p,q,，其中,pP1,且,qP2,。,能否在线性时间内找到,p,q,？,最接近点对问题,考虑,P1,中任意一点,p,，它若与,P2,中的点,q,构成最接近点对的候选者，则必有,distance(p,，,q),d,。,满足这个条件的,P2,中的点一定落在一个,d2d,的矩形,R,中,由,d,的意义可知，,P2,中任何,2,个,S,中的点的距离都不小于,d,。由此可以推出,矩形,R,中最多只有,6,个,S,中的点,。,因此，在分治法的合并步骤中,最多只需要检查,6n/2=3n,个候选者,能否在线性时间内找到,p3,q3,？,证明,:,将矩形,R,的长为,2d,的边,3,等分，将它的长为,d,的边,2,等分，由此导出,6,个,(d/2)(2d/3),的矩形。若矩形,R,中有多于,6,个,S,中的点，则由鸽舍原理易知至少有一个,(d/2)(2d/3),的小矩形中有,2,个以上,S,中的点。设,u,，,v,是位于同一小矩形中的,2,个点，则,distance(u,v)d,。这与,d,的意义相矛盾。,为了确切地知道要检查哪,6,个点，可以将,p,和,P2,中所有,S2,的点投影到垂直线,l,上。由于能与,p,点一起构成最接近点对候选者的,S2,中点一定在矩形,R,中，所以它们在直线,l,上的投影点距,p,在,l,上投影点的距离小于,d,。由上面的分析可知，这种投影点最多只有,6,个。,因此，若将,P1,和,P2,中所有,S,中点按其,y,坐标排好序，则对,P1,中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对,P1,中每一点最多只要检查,P2,中排好序的相继,6,个点。,最接近点对问题,最接近点对问题,double,cpair2,(S),n=|S|;,if,(n 2),return,;,1,、,m=S,中各点,x,间坐标的中位数,;,构造,S1,和,S2,；,/S1=pS|x(p)m,2,、,d1=,cpair2,(S1);,d2=,cpair2,(S2);,3,、,dm=,min,(d1,d2);,4,、设,P1,是,S1,中距垂直分割线,l,的距离在,dm,之内的所有点组成的集合；,P2,是,S2,中距分割线,l,的距离在,dm,之内所有点组成的集合；,将,P1,和,P2,中点依其,y,坐标值排序；,并设,X,和,Y,是相应的已排好序的点列；,5,、通过扫描,X,以及对于,X,中每个点检查,Y,中与其距离在,dm,之内的所有点,(,最多,6,个,),可以完成合并；,当,X,中的扫描指针逐次向上移动时，,Y,中的扫描指针可在宽为,2dm,的区间内移动；,设,dl,是按这种扫描方式找到的点对间的最小距离；,6,、,d=,min,(dm,dl);,return,d;,复杂度分析,T(n)=O(nlogn),迭代求解过程如下：,T(n)=T(n-2)+O(1)+O(1),=T(n-3)+O(1)+O(1)+O(1),=O(1)+O(1)+O(1)+O(1),=n*O(1),=O(n),求解递归方程举例：,例,1,：,+,=,=,1,5,),2,(,2,1,7,),(,2,n,n,n,T,n,n,T,2,2,2,1,1,2,2,2,2,2,2,5,),2,(,5,2,),2,(,5,2,),1,(,2,5,),),2,(,5,),),4,(,5,),8,(,2,(,2,(,2,5,),),2,(,5,),4,(,2,(,2,5,),2,(,2,),(,n,n,n,T,n,n,n,n,T,n,n,n,T,n,n,T,n,T,k,k,k,+,+,+,+,=,+,+,+,=,+,+,=,+,=,-,-,L,),(,10,3,10,),2,1,2,(,5,7,2,5,7,),(,2,2,2,1,2,1,0,2,n,O,n,n,n,n,n,n,n,n,T,k,k,i,i,=,-,=,-,+,=,+,=,-,-,=,例,2,：,分析下面递推式的时间复杂度。设，,n=2,k,大小为,n,的原问题分成若干个大小为,n,/,b,的子问题，其中,a,个子问题需要求解，而,cn,k,是合并各个子问题的解需要的工作量。,+,=,=,1,),(,1,),(,n,cn,b,n,aT,n,c,n,T,k,=,k,k,k,b,k,k,a,b,a,n,O,b,a,n,n,O,b,a,n,O,n,T,b,),(,),log,(,),(,),(,log,例,3,：,