递归、分治和减治

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第4章 递归、分治和减治,1. 递归及其性质,2. 分治法的设计原理,3. 分治法的复杂度推导示例,4. 分治法的复杂度性质,5. 快速排序,6. 平面最接近点对,7. 选择问题,8. 最大子块和,9. 二进制方程,10. 减治,1,1. 递归及其性质,递归算法是一种自身直接或间接调用自身的算法,使用递归技术使得算法简单明了、易于理解、容易编程和验证。使用递归的程序往往很简单,系统对所有的子程序调用一视同仁，并不区分是不是调用了自身。也就是说，系统并不刻意发现递归成分。这是由子程序调用机制决定的,系统用栈实现子程序调用，也就是用栈实现递归。对比不使用递归，栈结构的操作和维护是额外的时空开销,2,2. 分治法的设计原理,分治法是把一个问题分解成多个子问题进行处理，然后把子问题的解综合处理，得到原问题的解,划分所得的子问题与原问题结构上等价,如果子问题太大，可以把子问题继续划分，直至划分得到的子问题能够直接求解,分治法的两个重要操作是：分解和综合。其时间复杂度也全部由这二者决定，确切的时间复杂度由二者的对比关系决定,3,3. 分治法的复杂度推导示例,divide_and_conquer(p(n),if (n=n0),return adhoc(p(n); /,基础项,else,divide p into p1, p2, ., pk; /,分,for (i=1; ic,是真正意义上的分治；,ac,是减治,6,5. 快速排序,理想的快速排序算法的复杂度递归方程如下，因为,a=c=2，,所以其复杂度为,O(nlogn)：,快速排序的时间复杂度最好情况下是,O(,nlogn,)，,最坏情况下是,O(n,2,)，,平均情况是,O(,nlogn,),可以使用辅助技术选取合理的中轴,当问题规模较小的时候，可以采用其他排序手法,n,用于分，2,f(n/2),用于治,7,6. 平面最接近点对,6.1 问题描述,6.2 分治法示意,6.3 分治法求解最近点对问题复杂度分析,8,6.1 问题描述,给定平面上的,n,个点的坐标，求出两两距离的最小值及其对应的点对,两点间的距离可以用勾股定理求得,最直观的解法是点之间循环两两求距离，记录其最小值和点对,9,6.2 分治法示意,a,b,c,d,e,f,g,h,i,a,c,b,e,d,f,i,h,g,f,g,a,d,b,h,c,e,i,a,c,b,e,f,i,h,g,d,a,d,b,c,e,f,g,h,i,这两个数组逻辑上产生，没有物理上产生,这两个数组物理上产生了,10,a,b,c,d,e,f,g,h,i,把问题分解为左右两部分，左右分别求得解，左右最小值中取较小的一个,d，,作为中间部分最小值的参考,中间部分按照纵坐标序列，每个点只需要比较它上面的7个点即可,如果中间部分得到的最小值更小，则取这个值，否则取,d。,d,d,d,左边的4个格中不可能超过4个点，右边也是,11,6.3 分治法求解最近点对问题复杂度分析,复杂度函数递归方程：,用分治法求解平面最近点对问题的时间复杂度是,O(,nlogn,) ,因为,a=c=2,用分治法求解平面最近点对问题的最大空间使用是,O(,nlogn,) ,但因为调用左右两部分有先后之分，因此空间复杂度为,O(n),上式中，,n,用于分，2,f(n/2),用于治，7,n,用于合,12,7. 选择问题,7.1 解法示例,7.2 算法中剩余部分序列大小估计,7.3 分治法求解选择问题复杂度分析,13,7.1 解法示例,求21个元素中的第8小元素：51, 57, 49, 35, 11, 43, 37, 3, 13, 52, 6, 9, 25, 32, 54, 16, 5,41 ,7, 23, 18,把前面的20个元素划分为5组，最后一个元素不处理，得到4组：(51, 57, 49, 35, 11), (43, 37, 3, 13, 52), (6, 9, 25, 32, 54), (16, 5,41 ,7, 23)，取各自的中值：49, 37, 25, 16。在这些中值中取中值25（或者37）,以25为中心，把原数组划分为3部分：小于25的、等于25的、大于25的：(11, 3, 13, 6, 9, 16, 5, 7, 23, 18), (25), (51, 57, 49, 35, 43, 37, 52, 32, 54, 41),原序列中第8小的数就是小于25的序列中第8小的值,14,舍弃等于25的序列和大于25的序列，仅对小于25的序列(11, 3, 13, 6, 9, 16, 5, 7, 23, 18)进行处理，也就是求这个序列第8小的元素,把它分成2组， (11, 3, 13, 6, 9), (16, 5, 7, 23, 18)它们的中值分别是9和16，取这两个数的中值9,以9为中心，把小于25的序列分为3部分：(3, 6, 5, 7), (9), (11, 13, 16, 23, 18)，求原序列第8小的元素等价于求第三个序列第3小的元素,对序列(11, 13, 16, 23, 18)排序得到(11, 13, 16, 18, 23)，这个序列第3小的元素是16，这就是原问题的解,15,7.2 算法中剩余部分序列大小估计,递增,递增,舍弃部分：,剩余部分：,16,7.3 分治法求解选择问题复杂度分析,复杂度函数的递归方程：,由于上式中7,n/10+n/5,小于,n，,因此，用分治法求解选择问题的时间复杂度是,O(n),算法的空间复杂度估计与时间复杂度估计类似，也是,O(n),17,8. 最大子块和,8.1 解法示例,8.2 分治法求最大子块的复杂度分析,18,8.1 解法示例,8-3-46-89-57,8-3-46,-89-57,10,8-3,-46,7,-89,-57,11,8,9,6,7,8,11,最大子块来源有3个：要么在左块，要么在右块，要么横跨左右两块,19,8.2 分治法求最大子块的复杂度分析,复杂度函数递归方程：,用分治法求解最大子块问题的时间复杂度是,O(,nlogn,)，,因为,a=c=2,用分治法求解最大子块问题的空间复杂度是,O(,logn,)，,额外空间用于调用间的参数传递，是调用的深度。空间复杂度不是,O(n)，,因为递归调用有先后之分,20,9. 二进制方程,9.1 问题描述,9.2 穷举法求解,9.3 问题分析,9.4 递归方程,9.5 该问题对应用分治法的启示,9.6 复杂度分析,21,9.1 问题描述,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+,a,N,x,n,x,n,-1,.x,1,= 0,给定上述方程（也就是给定了自变量个数,n,和各个位置上的系数,a,i,），,求其根向量中1的个数为,k,的根的总数,上述的加减乘和相等都是在模2的意义上进行的。,n26,例如，对于方程1+1,x,1,+0x,2,+1x,2,x,1,=0，,其根向量中1的个数为1的数量是1，对应的向量是(1,0),22,9.2 穷举法求解,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+,a,N,x,n,x,n,-1,.x,1,= 0,N,和,n,之间存在关系：,N = 2,n,含有,k,个1的解共有,C(n, k),个，每个需要用,O(k),的时间获得。对每个可能的解，要进行验证，需要进行乘和加的运算，需要计算,N*n,次,穷举法解决此问题的复杂度为,O(,knNC,(n,k),23,9.3 问题分析,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+,a,N,x,n,x,n,-1,.x,1,可以改写成：,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+,a,N,/2,x,n-1,.x,1,+,x,n,(,a,N,/2+1,+,a,N,/2+2,x,1,+,a,N,/2+3,x,2,+,a,N,/2+4,x,2,x,1,+ +,a,N,x,n,-1,.x,1,),把,x,n,分为2种情况：值是0与值是1,当,x,n,的值确定之后，就会构造出规模更小的方程,24,9.4 递归方程,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+a,N/2,x,n-1,.x,1,+,x,n,(a,N/2+1,+ a,N/2+2,x,1,+ a,N/2+3,x,2,+ a,N/2+4,x,2,x,1,+ + a,N,x,n-1,.x,1,),当,x,n,为0时，原方程化为：,a,0,+a,1,x,1,+a,2,x,2,+a,3,x,2,x,1,+a,4,x,3,+a,5,x,3,x,1,+a,6,x,3,x,2,+a,7,x,3,x,2,x,1,+. . .+,a,N,/2,x,n-1,.x,1,= 0,当,x,n,为1时，原方程化为：,b,0,+b,1,x,1,+b,2,x,2,+b,3,x,2,x,1,+b,4,x,3,+b,5,x,3,x,1,+b,6,x,3,x,2,+b,7,x,3,x,2,x,1,+. . .+,b,N,/2,x,n-1,.x,1,= 0，,其中,b,0,=,a,0,+,a,N,/2+1,b,1,=,a,1,+,a,N,/2+2, ,于是原问题的解,T(f, n, k) = T(g, n-1, k) + T(h, n-1, k-1),25,9.5 该问题对应用分治法的启示,注意终止项：该问题的终止项为,T(0=0, 0, 0),和,T(1=0, 0, 0),显然前者的值为1，后者的值为0,要注意观察可以采用递归、分治的条件：大规模的问题和小规模的问题同构或类似,26,9.6 复杂度分析,复杂度函数递归方程：,用分治法求解二进制方程的时间复杂度是,O(,nlogn,) ,因为,a=c=2,用分治法求解二进制方程的最大空间使用是,O(,logn,) ,因为两个新方程所占空间恰好可以被原方程的空间容纳,上式中，,n/2,用于分，2,f(n/2),用于治,27,10. 减治,减治是分治的特殊情况，即：原问题分成若干个子问题后，原问题的解与某个子问题的解等价。问题的规模变小,二分查找就是典型的减治算法,单峰连续一维函数优化问题也是典型的减治：区间,a, b,上的连续函数,f(x),是单峰的，给定,a, b,上的任意值,x,可以迅速计算,f(x)，,求,t，,使得,f(t),最大（最小）,28,a,b,某个点的一侧有更高或者相等的点，则这个点另一侧的区间肯定不包含最大值点,给出4个点，则中间的两个点肯定至少有其一满足上面的条件,可以用黄金分割的方式减少求,f(x),的次数,c,d,29,