(XXXX0518版第二讲_分治策略-不可更改

1、1第2讲分治与递归策略2.1 分治算法的基本思想2.2 递归概念 2.3 典型分治算法举例12算法总体思想 将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。n/16 n n/4 n/4 n/4 n/4n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/1623 将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的解。 最顶层问题a 为分解的子问题数量；n/b 为每个子问题的数据规模；f(n) 为合并子问题解所消耗的时间。342.1 分治算法的基本思想 分治算法的基本思想

2、是将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。45分治算法所能解决问题一般具有以下几个特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。56分治算法的算法框架divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决规模小的问题 /将问题P 分解为子问题P1,P2,.,Pa； for (i=1,i1是常数，f(n)是一个渐进函 数，描述划分问题与合并解的时间复杂

3、性。 n/b可以是 ，也可以是 公式法上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并子问题的解所需要的时间由f(n)决定1617定理：上述递归方程含有三种情形的渐进界：（1）对于某个常数 如果 则（2）如果 则 （3）对某个常数 如果 且对某个常数 c 1时，perm(R)的全排列为：(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)方法1：固定位置找元素2627递归公式27282829将每个元素交换到固定位置上，并求解其余位置元素

4、的全排列。举例，03共4个数值的全排列思路？2930假设: 要求Pm 、Pm+1 、 Pn的全排列:值得注意的是，将Pm和某个Pk交换，求出剩余元素的所有排列后，为 了避免重复，发生混乱，必须将Pm 和Pk交换回去，然后才能继续Pm 和PK+1的交换。当问题规模降为求一个元素Pm的全排列时，问题就极为简单，可作为 递归出口。3.然后依次考虑Pm+3，,Pn。2.然后考虑Pm+1，通过交换Pm和Pm+1，这样我们仍然只要考虑求剩 余元素Pm+1 、Pm+2, Pn的所有排列即可。 1.需要先考虑Pm，如果能够求出剩余元Pm+1 、Pm+2 、，Pn 的所有排列，我们只需将Pm放到每个排列的开头。

5、30313132void perm(int r, int i, int n) / r存放R集合元素，r0rn / i,n 表示目前求解的全排列起始与终止位置 if （只有一个元素） /递归边界条件 显示当前排列； else 依次将i n 之间的每个元素交换 /递归到第i 个位置，并用同样的方法 （递归）求解i+1n 之间的全排列 3233void perm(int r, int i, int n) if ( i = n ) / 只有一个数值 for (int j = 0; j = n; j+) / 输出结果 coutrj; coutendl; else for (int j = i; j =

6、n; j+) swap(r, i, j); / 交换ri与rj perm(r, i + 1, n); / 计算i+1 n 全排列 swap(r, i, j); / 交换ri与rj 3334 将n放在p3位置上，并用p1.2和p4.n产生n-1个元素的全排列；方法2：固定元素找位置 元素放置位置：p1pn 直到将n放在pn位置上，并用p1.n-1产生n-1个 元素的全排列。 . 将n放在p1位置上，并用p2.n产生n-1个元素的全排列； 基本过程： 在n-1 个元素的全排列基础上，将某个元素插入到每个位置上，进而得出n 个元素的全排列。 将n放在p2位置上，并用p1和p3.n产生n-1个元素的全

7、排列；3435321, 312, 231, 132, 213, 1233536void perm2(int p, int n) / n = NUM-1 / p1pn放置元素，初始为0， / n为当前参与排列的元素数量, 1,2,3, n if (参与排列的数据数量为0) 输出结果 else 依次将n放在每个位置， 并采用同样的方法求解另外n-1元素的全排列； 3637void perm2(int p, int n) if (n = 0) / 元素集合为空 for (int i = 1; i = NUM ; i+) / 输出结果 coutpi; coutendl; else for (int i

8、 = 1; i = NUM; i+) if (pi = 0) pi = n; perm2(p, n-1); pi = 0; 初始：p1.n=0;perm(p,n);NUM为n+1例如：n = 3，NUM = 43738实现过程注意：在n放定一个位置pK，找到剩下n-1个元素的所有 排列后，在找n的下一个可放置位置时，即把n放到位置 Pk+1前，原来放n的位置pK一定要置0。否则，将有某 些元素找不到位置。 依次递归下去，直到数组没有为0 的元素为止。我们初始化数组p1.n的值为0，对于元素n，可以依次把它 放到数组的p1,p2,.,pn位置，在n放定一个位置后pK 后，剩下的n-1个元素可以放

9、在那些值为0的数组元素p1.k-1 和pk+1.n上。3839递归小结递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。优点：缺点：3940给定已按升序排列的n个元素a0:n-1，现要在这n个元素中找出一个特定元素x。分析：搜索范围越小，越容易确定解；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解就是原问题的解；分解出的各个子问题是相互独立的。2.3节 分治算法举例1：二分搜索技术分析： 此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立

10、的子问题，因此满足分治算法的基本条件。4041templat int binarySearch(T a, int x, int n) int left = 0;int right = n - 1;while (left amiddle) left = middle + 1;else right = middle - 1;return -1; / 未找到x算法复杂性分析：每执行一次while循环，搜索范围缩小一半。因此，在最坏情况下，while循环被执行了O(lgn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(lgn)41两个n位二进制大整数乘法运算的基本

11、方法:(1)小学的方法：时间复杂性 效率太低42分治算法举例2：大整数的乘法4243X = A 2n/2 + BY = C 2n/2 + D A B C DX = Y = (2)分治算法:注意：乘以2n表示向左位移n位，这个运算耗时复杂性分析XY = (A 2n/2 + B)(C 2n/2 + D) = AC 2n + (AD + BC) 2n/2 + BD乘法4次，加法3次，位移2次4344将公式：XY = AC 2n + (AD+BC) 2n/2 + BD变换为：XY = AC 2n + (A-B)(D-C)+AC+BD) 2n/2 + BD乘法：3次；加减法：6次；位移：2次4445fo

12、r ( int i = 0; i n; i+)for (int j = 0; j n; j+) Cij = 0;for (int k = 0; k 0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘,即k=0,11。5354棋盘覆盖分治算法伪语言if(size=0)return ;/ 覆盖左上角子棋盘if ( 特殊方块在左上角)

13、 覆盖左上角;else 在右下角放一小方块;覆盖左上角;/ 覆盖右上角子棋盘if ( 特殊方块在右上角)覆盖右上角;else 在左下角放一小方块;覆盖右上角;/ 覆盖左下角子棋盘if ( 特殊方块在左下角)覆盖左下角;else 在右上角放一小方块;覆盖左下角;/ 覆盖右下角子棋盘if ( 特殊方块在右下角)覆盖右下角;else 在左上角放一小方块;覆盖右下角;void chessBoard(int tr, int tc,int dr, int dc,int size) 5455void chessBoard(int tr, int tc, int dr, int dc, int size) i

14、f (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

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

16、s);55565657void chessBoard(int boardNN,int tr,int tc,int dr,int dc,int size,int& tile) if (size = 1) return;int s = size/2;int t = tile+;/ 左上角if (dr tr + s & dc tc + s) chessBoard(board,tr,tc,dr,dc,s,tile);else boardtr+s-1tc+s-1 = t; chessBoard(board,tr,tc,tr+s-1,tc+s-1,s,tile); / 右上角if (dr = tc + s

17、) chessBoard(board,tr,tc+s,dr,dc,s,tile);else boardtr+s-1tc+s = t; chessBoard(board,tr,tc+s,tr+s-1,tc+s,s,tile); / 左下角if (dr = tr + s & dc = tr+s & dc = tc + s) chessBoard(board,tr+s,tc+s,dr,dc,s,tile);else boardtr+stc+s = t; chessBoard(board,tr+s,tc+s,tr+s,tc+s,s,tile); 57585859分治算法举例5： 归并排序void me

18、rgeSort(T a,int left, int right) if ( 含有2个以上元素) 计算中点位置；归并排序前半部分； / 分解归并排序后半部分； / 分解将两个有序段合并到b； / 合并结果将b中的结果复制回a； 基本思想:将待排序元素分成大小大致相同的两个子集合， 分别对两个子集合进行排序，然后将两个排好序的子集合 归并成一个有序的集合。 5960template void mergeSort(T a,int left, int right) if (left right) mid = (left + right) / 2; / 计算中点mergeSort(a,left, mid

19、); / 归并排序前后两部分mergeSort(a,mid + 1, right);merge(a,b,left, mid, right); / 将两个有序段合并到bcopy(a,b,left,right); / 将结果复制到数组a606161626263（2）成对处理输入值，用其中较小者与当前最小值比较，用较大值与当前最大值比较，每对数据比较3次，共比较 次。分治算法举例6：线性时间选择在有n个元素的集合中找最小值或最大值需比较n-1次。如果利用锦标赛树，其他元素需要比较 次。（1）分别找出最大值和最小值，比较次数为2（n-1）同时找到最大值和最小值方法：6364T randomizedSe

20、lect(T a, int p, int r, int k) 如果只有一个元素，将其返回；int i = 随机将线性序列分解为两部分(前小后大）；j = 计算前段元素个数;if ( 第k个小的元素位于前段)采用同样的方法在前段找第k 个小元素；else采用同样的方法在后段找k-j 个小元素;pirja问题：给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。6465Template T randomizedSelect(T a, int p, int r, int k)if (p = r) return ap;int i = randomizedPartition(a

21、, p, r);j = i p + 1;if ( k = j) return randomizedSelect(a, p, i, k);else return randomizedSelect(a, i+1, r, k-j);pirja6566 一种选择支点元素的方法是使用“中间的中间（median-of-median）”首先将数组a中的n 个元素分成n/r 组，r 为某一整常数，除了最后一组外，每组都有r个元素。然后通过在每组中对r 个元素进行排序来寻找每组中位于中间位置的元素。最后对所得到的n/r 个中间元素，递归使用选择算法，求得”中间之中间”作为支点元素。规则：6667如果能在线性时间

22、内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至多为原数组长度的倍(01是某个正常数)，就可以在最坏情况下用O(n)时间完成选择任务。在最坏情况下，算法randomizedSelect需要O(n2)计算时间。可以证明，算法randomizedSelect可以在O(n)时间内找出n个输入元素中的第k小元素。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。6768P=8,17,4,11, 3,13,6,19,16,5,7,23,22Q=25

23、R=31,60,33,51,57,49,35,43,37,52,32,54,41,46,29按递增顺序，找出下面29个元素的第18个元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.举例(1) 把前面25个元素分为5(=floor(29/5)组： (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32), (54,16,5,41,7).(2) 提取每一组的中值元素，构成集合31,49,13,25,16；(3)

24、 递归地使用算法求取该集合的中值，得到m=25；(4) 根据m=25, 把29个元素划分为3个子数组：6869(7) 求取这3组元素的中值元素分别为：51,43,41， 这个集合的中值元素是43;例子（续）(5) 由于|P|=13,|Q|=1,k=18，所以放弃P,Q，使 k=18-13-1=4，对R递归地执行本算法；(6) 将R划分成3(floor(15/5)组： 31,60,33,51,57,49,35,43,37,52,32,54,41,46,29(8) 根据43将R划分成3组： 31, 33, 35,37,32, 41, 29,43,60, 51,57, 49, 52,54, 4669

25、70(12) 因为k=4,而第一、第二个子数组的元素个数为3，所以33即为所求取的第18个小元素。例子（续）(9) 因为k=4，第一个子数组的元素个数大于k，所以放弃后面两个子数组，以k=4对第一个子数组递归调用本算法；(10)将这个子数组分成5个元素的一组：31,33,35,37,32，取其中值元素为33；(11)根据33，把第一个子数组划分成31,32,29,33,35,37,41;7071 找出这 个元素的中位数。如果 是偶数，就找它的2个中 位数中较大的一个。以这个元素作为划分基准。 将n个输入元素划分成 个组，每组5个元素， 只可能有一个组不是5个元素。用任意一种排序算法，将每组中的

26、元素排好序，并取出每组的中位数，共 个。设所有元素不相同。在这种情况下，基准x至少比3 个元素大，因为在每一组中有2个元素小于本组的中位数，而 个中位数中又有 个小于基准x。同理，基准x也至少比3 个元素小。当n75时，3(n-5)/10n/4。所以按此基准划分所得的2个子数组的长度都至少缩短1/4。7172T select (T a, int p, int r, int k) if (少于或等于5个数值) 直接排序;return ap+k-1;分组排序，并将中位数交换到前面;int x = 确定中位数的中位数;int i = partition(p,r,x), j=计算前半区个数;if (k

27、=j) return select(a, p , i , k);else return select(a, i+1, r, k-j);if (r-p5) bubbleSort(p,r);return ap+k-1;for ( int i = 0; i(r-p+1)/5; i+ ) int s=p+5*i,int t=s+4;bubbleSort(s,t);swap(a, p+i, s+2);int x = select(a, p, p+(r-p+1)/5-1, (r-p)/10);int i=partition(p,r,x);j=i-p+1;if (k=j) return select(a,

28、p , i , k);else return select(a, i+1, r, k-j);7273T(n/5)：在n/5个组中找中位数的中位数。T(3n/4)：划分的子序列最多为3n/4。结论：在这里，将75作为递归界限条件，5作为分组大小，可以保证：n/5+3n/4=19n/20=n，01,这是关键。7374 给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 解决方法：将每个点与其余n-1个点的距离计算出来，最小距离者即为最接近点对。时间复杂性O(n2)。(1)一维情形:S中的n个点退化为x轴上的n个实数x1,x2,xn。最接近点对为其中相差最小

29、的2个实数。分治算法举例7：最接近点对问题7475优化最接近点对问题算法问题：无法应用于二维点对。解决方法：对所有点进行排序，需要O(nn)。再扫描一遍即可以得出最接近点对。证明得知，该问题的时间下界为(nn)7576优化最接近点对问题算法假设用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？7677

30、如果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的解。7778一维点集S的最接近点对的算法double cpair1(S) /排序, (n n)n = |S|;if (

31、n2) return ;m=S中各点坐标的中位数；/线性时间构造S1和S2; /线性时间d1=cpair1(S1); /计算左侧的最接近距离d2=cpair1(S2); /计算右侧的最接近距离p=max(S1); / 左侧最大值,线性时间q=min(S2); /右侧最小值,线性时间d=min(d1,d2,q-p); /最接近距离,常量时间return d;7879(2) 二维情形选取一垂直线l，x=m来作为分割 直线。其中m为S中各点x坐标的中 位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距 离d1和d2，并设d=mind1,d2，S 中的最接近点对或者是d，或者是 某个p,q，其中pP1且q