企业战略管理第2章 递归与分治策略

1、第2章 递归与分治策略Recursion ,divide and conquer method学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。1二分搜索技术；2合并排序3快速排序；4最接近点对问题；递归(recursion)是数学与计算机科学中的根本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归程序不能无限制地自我调用，否那么就会永不终止，递归程序必须有终止条件。尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用递归过程来描述它们不仅非常自然， 而且

2、证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。2.1 递归构成递归需具备的条件:1.不能无限制地调用本身，须有个出口，化简为非递归状况处理(边界条件);2.子问题与原问题为同一类型,且更为简单(递归模式).递归程序的书写方式:Procedure(parameter list) if return(initial value); else return(parameter exchange); end例1 阶乘函数 阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。i

3、nt 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) 递归程序结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性

4、，因此它为设计算法、调试程序带来很大方便。递归算法的运行效率较低，无论是消耗的计算时间还是占用的存储空间都比非递归算法要多。求斐波那齐数列的非递归程序：void fibonacci (int n) int prev,now,next,j; if (n=1) return(1); else prev=1; now=1; for(j=2;j=1122naanaannn如果如果分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为假设干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该

5、问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大局部问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，那么可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，那么分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。divide-and-conquer(P) if ( | P | = n0) adhoc(P);

6、 /解决小规模的问题 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)

7、if ( |P|=n0) Adhoc(P); divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i 1O(1)分治法的复杂性分析 T(n) = kT(n / m) + f(n) = k(kT(n / m2) + f(n / m) + f(n) = k2T(n / m2) + kf(n / m) + f(n) = k3T(n / m3) + k2f(n / m2) +kf(n / m) + f(n) = 这里ma = n，所以a = log m n。于是：ka = k = n = np，这里p = log m k。 log m

8、 nlog m k由此可知，T(n)的首项是n的常数幂。 T(n)= T(1)=O(1) n=1T(n)=kT(n/m)+f(n) n1a1 j=0 = kaT(1) + kj f(n / mj)= ka + kj f(n / mj)a1 i=0解得:二分搜索技术问题描述 一个排好次序的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，假设是，那么返回该元素在表中的位置，否那么，返回-1。一般解决方法从头到尾查找一遍a1a2a3a4anx最坏情况下，顺序搜索算法需要O(n)次比较。分析：如果n=1即只有一个元素，那么只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的

9、第一个适用条件分析：比较x和a的中间元素amid，假设x=amid，那么x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为假设干个规模较小的相同问题;分解出的子问题的解可以合

10、并为原问题的解；分解出的各个子问题是相互独立的。 二分搜索有序表的递归式算法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 )

11、 ; 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,

12、21,37,56,64,75,80,88,92T=21的查找过程：05 13 19 21 37 56 64 75 80 88 92 leftrightmid05 13 19 21 37 56 64 75 80 88 92 leftrightmid05 13 19 21 37 56 64 75 80 88 92 leftrightmidT=85的查找过程：05 13 19 21 37 56 64 75 80 88 92 leftrightmidmid T , left=mid +1 leftrightmidmid T , right=mid -1 leftright二分搜索有序表的算法分析nn/

13、2n/2n/4n/4n/4n/41111log 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) 。归并排

14、序1划分：将待排序序列r1, r2, , rn划分为两个长度相等的子序列r1, , rn/2和rn/21, , rn；2求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；3合并：将这两个有序子序列合并成一个有序序列。 二路归并排序是成功应用分治法的一个完美例子，其分治策略是：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 r1 rn/2 rn/21 rn 划分r1 rn/2 rn/21 rn 递归处理r1rn/2rn/21 r n 合并解 2-路归并排序的分治思想初始序列a 8 4 5 6 2 1 7 3 归并到b 4 8 5 6 1 2 3

15、 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 Merge

16、Sort(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辅助数组

17、B比较大小小值A(1)比较大小小值A(n/2+1)数组A剩余已分类元素A(1)A(n/2+1)算法如下 templatevoid 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=2k时，可得T(n)=2(2T(n/4)+cn/2)+c

18、n = 22T(n/22)+2cn =4(2T(n/8)+cn/4)+2cn = 23T(n/23)+3cn =2kT(n/2k)+kcn =2kT(1)+kcn =an+cnlognT(n)=O(nlogn)归并排序时间复杂度最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n)T(n)=O(nlogn) 渐进意义下的最优算法算法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消去递归后的合

19、并排序算法 temlplate voidmergesort( typea,intn) type *b=new typen; ints; s=1; while(sn) mergepass(a,b,n,s); s+=s; mergepass(b,a,n,l); s+=s; C+描述快速排序 1划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 ri-1和 ri+1 rn ，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；2求解子问题：分别对划分后的每一个子序列递归处理；3合并：由于对子序列r1 ri-1和ri+1 rn的排序是就地进行的，所以合并

20、不需要执行任何操作。 快速排序也是基于分治技术的重要排序算法，和归并排序不同的是：归并排序是按照记录在序列中的位置对序列进行划分的，而快速排序是按照记录的值对序列进行划分的。快速排序的分治策略是： r1 ri-1 ri ri+1 rn 均ri 轴值 均ri 位于最终位置 快速排序是冒泡排序的一种改进方法，是由C.A.R. Hoare于1962年提出的。在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，而总的比较和移动次数较少。快速排序的分治思想13652750384955jijj13652

21、750384955jiii13652750384955ijjj一次划分例如 以轴值为基准将待排序序列划分为两个子序列后，对每一个子序列分别递归进行排序。132750384955jiij1365275038495565算法一次划分 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; /将较大记录交

22、换到后面 j-; retutn i; / i为轴值记录的最终位置 C+描述以第一个记录作为轴值，对待排序序列进行划分的过程为：1初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；2右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，那么j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小即反序，假设ij，那么将基准记录与j指向的记录进行交换；3左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，那么i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大即反序，假设i

23、j，那么将基准记录与i指向的记录交换；4重复23步，直到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(2T(n/4)n/2)n4T(n/4)2n

24、 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n) 因此，时间复杂度为O(nlog2n)。 在最好情况下，每次划分对一个记录定位后，该记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，那么所需时间为O(n)。设T(n)是对n个记录的序列进行排序的时间，每次划分后，正好把待划分区间划分为长度相等的两个子序列，那么有：因此，时间复杂度为O(n2)。 在最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列另一个子序列为空。此时，必须经过n-1次递归调用才能把所有记录定位，而

25、且第i趟划分需要经过n-i次关键码的比较才能找到第i个记录的基准位置，因此，总的比较次数为：在平均情况下，设基准记录的关键码第k小1kn，那么有： 这是快速排序的平均时间性能，可以用归纳法证明，其数量级也为O(nlog2n)。 最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。

26、递归地在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中最大点。因此，我

27、们用线性时间就能找到区间(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中

28、的点一定落在一个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中，所以它们