算法设计与分析第二章 递归与分治策略杨圣洪 学习要点学习要点:理解递归的概念掌握设计有效算法的分治策略通过下面的范例学习分治策略设计技巧1）二分搜索技术； （2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表2 2 第2章 递归与分治策略Ø本章主要知识点：§2.1 递归的概念§2.2 分治法的基本思想§2.3 二分搜索技术§2.4 大整数的乘法§2.5 Strassen矩阵乘法§2.6 棋盘覆盖§2.7 合并排序§2.8 快速排序§2.9 线性时间选择§2.10 最接近点对问题§2.11 循环赛日程表Ø计划授课时间：6～8课时3 3 2.1 递归的概念Ø直接或间接地调用自身的算法称为递归算法递归算法用函数自身给出定义的函数称为递归函数递归函数Ø在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解Ø下面来看几个实例4 4 2.1 递归的概念Ø例1 阶乘函数Ø可递归地定义为：高低Ø其中：Øn=0时，n!=1为边界条件Øn>0时，n!=n(n-1)!为递归方程Ø边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
ØT=1;for (i=2;i
§M=3时，类似的可以推出§M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数Ø无法找到循环函数-非递归方式8 8 2.1 递归的概念Ø例4 排列问题§递归算法生成n个元素{r1,r2,…,rn}的全排列§设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}去掉元素ri§集合X中元素的全排列记为perm(X)§(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列§R的全排列可归纳定义如下：•当n=1时，perm(R)=(r)，r是集合R中唯一的元素；•当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成9 9 2.1 递归的概念Ø例5 整数划分问题§将正整数n表示成一系列正整数之和：§n=n1+n2+…+nk，§其中n1≥n2≥…≥nk≥1，k≥1降序§正整数n的这种表示称为正整数n的划分§求正整数n的不同划分个数 §例如正整数6有如下11种不同的划分：•6；•5+1；•4+2，4+1+1；•3+3，3+2+1，3+1+1+1；•2+2+2，2+2+1+1，2+1+1+1+1；•1+1+1+1+1+1。
1010 2.1 递归的概念如果设p(n)为正整数n的划分数则难以找到递归关系换函数q(n,m) ：最大加数n1 m 时n的划分个数q(n,m)的如下递归关系：q(n,1)=1，n≥1；最大加数 1时，任何正整数n只有一种划分形式：n=1+1+...+1(共n个)q(n,m)=q(n,n)，m≥n；最大加数nq(1,m)=1q(n,n)=1+q(n,n-1)；n的划分={最大加数=n的划分}{最大加数≤n-1的划分}q(n,m)=q(n,m-1)+q(n-m,m),n>m>1；最大加数 m的划分={最大加数≤m-1 的划分}{最大加数n1=m的划分} = ={最大加数≤m-1 的划分}{最大加数n1+(n-n1)即(n-m)
§public static void hanoi(int n, int a, int b, int c){ if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); }}§思考：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案1313 2.1 递归的概念Ø5个盘子循环1号顺移号顺移B :2345 1 _2号到号到C: 345 1 2 1号顺移号顺移C :345 _ 123号到号到B: 45 3 121号顺移号顺移A : 145 3 2 2号到号到B: 145 23 _1号顺移号顺移B : 45 123 _ 4号到号到C: 5 123 4 1号顺移号顺移C : 5 23 142到到A:25 3 141号顺移号顺移A:125 3 4 3号到号到C:125 _ 341号顺移号顺移B:25 1 342号到号到C：：5 1 234 1号顺移号顺移C:5 _ 1234到到B：：_ 5 12341号顺移号顺移A:1 5 2342到到B：：1 25 341号顺移号顺移B:_ 125 343到到A：：3 125 41号顺移号顺移C:3 25 14 2到到A:23 5 141号顺移号顺移A:123 5 44到到B:123 45 __1号顺移号顺移B:23 145 _2到到C:3 145 21号顺移号顺移C:3 45 123到到B :_ 345 12 1414 2.1 递归的概念Ø递归小结递归小结§优点优点：结构清晰，可读性强，且用数学归纳法证明正确：结构清晰，可读性强，且用数学归纳法证明正确性，因此它为设计算法、调试程序带来很大方便。
性，因此它为设计算法、调试程序带来很大方便§缺点缺点：递归运行：递归运行效率较低效率较低，时间，时间,空间比非递归多空间比非递归多§解决方法：解决方法：消除递归调消除递归调用，使其转化为非递归算法用，使其转化为非递归算法1.采用一个用户定义的栈来采用一个用户定义的栈来模拟系统模拟系统的递归调用工作栈该方法的递归调用工作栈该方法通用性强，但本质上还通用性强，但本质上还是递归是递归，只不过人工做了本来由编译器，只不过人工做了本来由编译器做的事情，优化效果不明显做的事情，优化效果不明显自顶向下保存现场自顶向下保存现场2.用用递推递推来实现来实现递归递归函数3.通过通过Cooper变换、变换、反演反演变换能将一些递归转化为变换能将一些递归转化为尾递归尾递归，从而，从而迭代迭代求出求出结果后两种方法在后两种方法在时空时空复杂度上均有较大复杂度上均有较大改善改善，但其适用范围有限但其适用范围有限讨论题：递归的执行过程如何？讨论题：递归的执行过程如何？1515 2.2 分治法的基本思想Ø分治法的基本思想§将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同§对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止§将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解§将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之凡治众如治寡，分数是也——孙子兵法1616 练习Ø1,算法分析的基本原则有哪些？Ø2,试设计一算法，实现有31个网球运动员参加比赛的循环赛日程表且简要分析你设计算法的时间和空间复杂性Ø31*31矩阵,主对角线为0,每行中1-31只能出现一次,每列也是如此.Ø讨论题：什么时候可使用递归？程序中递归的执行过程如何？1717 分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：Ø1,该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；Ø2,该问题可以分解为若干个规模较小的相同问题，即该问题该问题可以分解为若干个规模较小的相同问题，即该问题具有具有最优子结构性质最优子结构性质Ø3,利用该问题分解出的子问题的解可以合并为该问题的解；利用该问题分解出的子问题的解可以合并为该问题的解；Ø4,该问题所分解出的各个子问题是相互独立的，即子问题之该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
间不包含公共的子问题 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，一般用动态规划动态规划.2.2 分治法的基本思想Ø分治法的适用条件1818 2.2 分治法的基本思想Ø分治法的基本步骤§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); //将各子问题的解合并为原问题的解将各子问题的解合并为原问题的解}Ø人们从人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。
即将一个问题分成大小相等的k个子问题的处理方法是行之有效的这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好云计算mapreduce1919 2.2 分治法的基本思想Ø分治法的复杂性分析一个分治法将规模为一个分治法将规模为n的问题分成的问题分成k个规模为个规模为n／／m的子问题去解的子问题去解分解阈值分解阈值n0=1，，adhoc解耗费解耗费1个单个单位时间将原问题分解为将原问题分解为k个子问题以及用个子问题以及用merge将将k个子问题的解合并为原个子问题的解合并为原问题的解需用问题的解需用f(n)个单位时间个单位时间分治法解规模为分治法解规模为|P|=n的问题所需的的问题所需的计算时间，则有（计算时间，则有（右上右上）通过通过迭代法迭代法求得其规模为求得其规模为右下右下 注意注意：：递归方程递归方程及其解只给出及其解只给出n等于等于m的方幂的方幂时时T(n)的值，但是如果认的值，但是如果认为为T(n)足够平滑，那么由足够平滑，那么由n等于等于m的方幂时的方幂时T(n)的值可以估计的值可以估计T(n)的的增长速度通常假定增长速度。
通常假定T(n)是单调是单调上升的，从而当上升的，从而当mi n a[middle]) left = middle + 1;else right = middle - 1;}return -1; // 未找到未找到x}Ø算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。
最坏情况任意二个相邻元素都要分划到，即2m=n,log2n=m因此，，while循环被执行了O(logn) 次循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 2222 Template (class Type)Int BinarySearch1(Type a[],const Type& x,int n) {Int left=0;int right=n-1;While (left<=right) { int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left = middle; else right=middle; } return -1; }Template (class Type)Int BinarySearch2(Type a[],const Type& x,int n) {Int left=0;int right=n-1;While (left=a[middle]) left = middle; else right=middle; } if (x==a[left]) return left; else return -1;}Template (class Type)Int BinarySearch4(Type a[],const Type& x,int n) {If (n>0 && x>=a[0]) {Int left=0;int right=n-1;While (left
2. 与主教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误3. 与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a[n-1]时返回错误4. 与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致陷入死循环2323 2.4 大整数的乘法Ø设计一个有效的算法，可以进行两个n位大整数的乘法运算分成二段再相乘，即分治也Ø小学的方法：O(n2) 效率太低Ø分治法: §X=a2n/2+b§Y=c2n/2+d§XY=ac2n+(ad+bc)2n/2+bdØ复杂度分析§ §T(n)=O(n2) 没有改进 n/2 n/2位位 n/2n/2位位 n/2 n/2位位 n/2n/2位位X=X= Y=Y=ABCD2424 算法改进Ø为了降低时间复杂度，必须减少乘法的次数为此，我们把XY写成另外的形式：§XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd 或§XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bdØ复杂性：§这两个算式看起来更复杂一些，但它们仅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是§ §T(n)=O(nlog3) =O(n1.59) 较大的改进Ø细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。
2525 更快的方法Ø小学的方法：O(n2)——效率太低Ø分治法: O(n1.59)——较大的改进Ø更快的方法？§如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法§最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决§是否能找到线性时间的算法？目前为止还没有结果FFT?2626 课堂练习Ø习题2-4 大整数乘法的O(nmlog3/2) 给定2个大整数u和v,他们分别有m位和n位数字，且m<=n1,用通常的乘法求uv的值需要O(nm)时间；2,用教材的分治法，可以将u和v都看作是有n位数字大整数，在O(nlog3)时间内计算uv的值 ；当m比n小得多的时候，这样分治法就不那么有效，试设计一算法，使得可以在O(nmlog3/2) 时间内求出uv的值2727 2.5 Strassen矩阵乘法Øn×n矩阵A和B的乘积矩阵C中的元素C[i,j]定义为：Ø若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。
因此，算出矩阵C的所有元素所需的计算时间为O(n3)2828 简单分治法求矩阵乘Ø首先假定n是2的幂使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵由此可将方程C=AB重写为：Ø由此可得：Ø复杂度分析ØT(n)=O(n3) 没有改进 n2=n*n个元素值加法得出个元素值加法得出2929 改进算法Ø为了降低时间复杂度，必须减少乘法的次数而其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）：M1=A11(B12-B22) M2=(A11+A12)B22M3=(A21+A22)B11 M4=A22(B21-B11)M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12) 提取公因式，先加减后乘，还有其他方法吗？Ø做了这7次乘法后，在做若干次加/减法就可以得到：C11=M5+M4-M2+M6 C12=M1+M2C21=M3+M4 C22=M5+M1-M3-M7Ø复杂度分析ØT(n)=O(nlog7) =O(n2.81) 较大的改进3030 更快的方法ØHopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。
因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了或许应当研究3×3或5×5矩阵的更好算法Ø在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性Ø目前最好的计算时间上界是 O(n2.376)Ø是否能找到O(n2)的算法？目前为止还没有结果3131 2.6 特殊棋盘覆盖Ø在一个2k×2k个方格组成的棋盘中，恰有1个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘Ø在特殊棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖Ø覆盖任意一个2k×2k的特殊棋盘，骨牌数恰好为(4K-1)/3总格数为(2k×2k)=2k+k=22k=(22)k=4k),去1特殊格, L占3格.Ø4k+1-1=4*4k-1=(3+1)4k-1=3*4k+(4k-1) 数归可证4K-1为3的倍数3333 2.6 特殊棋盘覆盖Ø1个格直接用特殊色盖Ø2*2时，无论特殊格在何处，只要4个L中1个Ø4*4时，分解成4块，特殊格位置可东西南北不同小块中，连接处用不同L，推广2k*2k.3434 分治策略求解 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一，其余3个无特殊方格 为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处， 如 (b)！！关键 从而将原问题转化为4个较小规模的特殊棋盘覆盖问题即4个同样的小问题,直至棋盘简化为棋盘1×1其他三种情况，其他三种情况，画在黑板上画在黑板上3535 分治策略求解CB(tr,tc,dr,dc,size):tr,tc是四小块中某块左上角在原始图中行号列号dr,dc是该小块中不能用L型砖覆盖的地方size:该小块宽目标除特殊块以外，其他位置用L型砖覆盖3636 算法描述void CB(int tr,tc,dr,dc,size){if (size == 1) return;int t = tile++; // L型骨牌号型骨牌号s = size/2; // 分割棋盘分割棋盘// 覆盖左上角子棋盘覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 此块左上角为此块左上角为(tr,tc)CB(tr, tc, dr, dc, s);else {// 无特殊方格无特殊方格// 用用 t 号号L型骨牌覆盖右下角型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 再处理再处理CB(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s)// 此块左上角为此块左上角为(tr,tc+s)CB(tr, tc+s, dr, dc, s);else {// 无特殊方格无特殊方格// 用用 t 号号L型骨牌覆盖左下角型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 再处理再处理CB(tr,tc+s,tr+s-1,tc+s, s);}// // 覆盖左下角子棋盘覆盖左下角子棋盘if (if (drdr >= >= trtr + s && dc < + s && dc < tctc + s) + s)////此块左上角为此块左上角为(tr+s,tc)CB(tr+sCB(tr+s, , tctc, , drdr, dc, s);, dc, s);else {// else {// 用用 t t 号号L L型骨牌覆盖右上角型骨牌覆盖右上角board[trboard[tr + + s][tcs][tc + s - 1] = t; + s - 1] = t;// // 再处理再处理CB(tr+sCB(tr+s, , tctc, , tr+str+s, tc+s-1, s);}, tc+s-1, s);}// // 覆盖右下角子棋盘覆盖右下角子棋盘if (if (drdr >= >= trtr + s && dc >= + s && dc >= tctc + s) + s)////此块左上角为此块左上角为(tr+s,tc+s) CB(tr+sCB(tr+s, , tc+stc+s, , drdr, dc, s);, dc, s);else {// else {// 用用 t t 号号L L型骨牌覆盖左上角型骨牌覆盖左上角board[trboard[tr + + s][tcs][tc + s] = t; + s] = t;// // 再处理再处理CB(tr+sCB(tr+s, , tc+stc+s, , tr+str+s, , tc+stc+s, s);}, s);}} }3737 复杂度分析Ø说明：§整形二维数组Board表示棋盘，Borad[0][0]是棋盘的左上角方格。
§tile是全局整形变量，表示L形骨牌的编号，初始值为0§tr:棋盘左上角方格的行号；tc:棋盘左上角方格的列号；§dr:特殊方格所在的行号；dc:特殊方格所在的列号；§size：size=2k，棋盘规格为2k×2kØ复杂度分析：§ §T(k)=4k-1=O(4k) 渐进意义下的最优算法3838 非递归求解-分治策略求解CB2(dr,dc,size):dr,dc是该小块中不能用L型砖覆盖的地方size:该小块宽基本思想：以8*8为例在黑板上演示 (1)分成4块，当每块格子数>4时，将每个4个格子的连接处用L型条子覆盖 (2)每块又分成4块当每块格子数>4时，将每个4个格子的连接处用L型条子覆盖 …… (3)当每块格子数为4后，不再细分，针对每4个格子用L型覆盖 3939 算法描述void CB2(dr,dc,size){var t=1; if (size<4) {return ;} var sizesub=size/2; //子块的大小子块的大小 var sumTmp=0; while (sizesub>=2) {for (i=0;i
直到子集中只有1个元素为止，然后再两两合并Ø递归算法描述：public static void mergeSort(Comparable a[], int left, int right){if (left
Ø自然合并排序?4747 Conti…Ø在一种极端情况：序列已排好序§自然合并排序： O(n)§合并排序：O(nlogn)Ø一般情况下，自然合并排序所需的合并次数较少4848 课堂练习Ø习题2-13：n1/2段合并排序算法§如果在合并排序算法的分段步骤中，将数组a[0,n-1]划分为[n1/2]个子数组，每个子数组有O(n1/2)个元素然后递归地对分段后的子数组进行排序，最后将所得到的[n1/2]个排好序的子数组合并成所要求的排好序的a[0,n-1]设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性Ø习题2-14：自然合并排序算法§对所给元素存储于数组中和存储于链表中2种情形，写出自然合并排序算法4949 2.8 快速排序Ø快速排序是基于分治策略的另一个排序算法，其基本思想是：§分解——以ap为基准元素将ap：r划分成3段ap：q-1、aq和aq+1：r，使得ap：q-1中任何元素小于aq ，aq+1：r中任何元素大于aq ；下标q在划分过程中确定；§递归求解——通过递归调用快速排序算法分别对ap：q-1和aq+1：r进行排序；§合并——由于对ap：q-1和aq+1：r的排序是就地进行的，所以在ap：q-1和aq+1：r都已排好序后不需要执行任何计算ap：r就已排好序。
Ø在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少Ø 左边左边比首元比首元小小右移右移，，直到直到大于大于首元首元，右边，右边比首元比首元大大左移左移直到小于首元直到小于首元Ø快速算法描述：templatevoid QuickSort (Type a[], int p, int r){if (pint Partition (Type a[], int p, int r){int i = p, j = r + 1; Type x=a[p];// 将< x的元素交换到左边区域// 将> x的元素交换到右边区域while (true) {while (a[++i] x);if (i >= j) break; Swap(a[i], a[j]);}a[p] = a[j];a[j] = x;return j;}{6, 7, 51, 2, 5, 8} 初始序列{6, 7, 51, 2, 5, 8} j--;↑i ↑j{5, 7, 51, 2, 6, 8} i++; ↑i ↑j{5, 6, 51, 2, 7, 8} j--; ↑i ↑j{5, 2, 51, 6, 7, 8} i++; ↑i ↑j{5, 2, 51}6{7, 8} 完成快速排序具有不稳定性！不稳定性！5151 复杂性分析及随机化的快速排序算法Ø算法复杂性分析：§最坏时间复杂度：O(n2)§平均时间复杂度：O(nlogn)§辅助空间：O(n)或O(logn)5252 Conti…Ø快速排序算法的性能取决于划分的对称性。
通过修改算法partition，可以设计出采用随机选择策略的快速排序算法在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的Ø算法描述：§template§int RandomizedPartition (Type a[], int p, int r)§{•int i = Random(p,r);•Swap(a[i], a[p]);•return Partition (a, p, r);§}5353 2.9 线性时间选择Ø元素选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素ØRandomizedSelect算法：模仿快速排序算法，首先对输入数组进行划分，然后对划分出的子数组之一进行递归处理算法描述如下：templateType RandomizedSelect(Type a[],int p,int r,int k){if (p==r) return a[p];int i=RandomizedPartition(a,p,r),j=i-p+1;if (k<=j) return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);}5454 时间复杂性分析RandomizedSelectRandomizedPartitionPartition快速排序算法中的随机化划分，T(n)?快速排序算法中的划分，O(nlogn)最坏情况下， Omega(n2)比如要找最小元素，但总是在最大元素处划分Ø算法复杂性：在最坏情况下，算法randomizedSelect需要O(n2)计算时间。
但可以证明，算法RandomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素5555 改进算法Ø基本思路：如果能性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务Ø例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 由此可得T(n)=O(n)T(εn)+O(n)5656 一个较好的基准划分步骤Ø步骤（如图所示）：§将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个§递归调用select来找出这n/5个元素的中位数如果n/5是偶数，就找它的2个中位数中较大的一个以这个元素作为划分基准Ø说明：§设所有元素互不相同在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x（如图）。
同理，基准x也至少比3(n-5)/10个元素小而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4图2-7 选择划分基准其中，n个元素用小圆点表示， 空心圆点为每组元素的中位数； x为中位数的中位数； 箭头由较大元素指向较小元素只要等于基准的元素不太多，利用这个基准来划分的两个数组的大小就不会相差太远ai3(n-5)/10ai>xn/5+(n/5-1)/2>3(n-5)/105757 算法描述及复杂性分析private static Comparable select (int p, int r, int k){//用某个简单排序算法对数组a[p:r]排序; if (r-p<75) {bubbleSort(p,r);return a[p+k-1];}//将ap+5*i至ap+5*i+4的第3小元素与ap+i交换;//找中位数的中位数，r-p-4即前述n-5;for ( int i = 0; i<=(r-p-4)/5; i++ ){int s=p+5*i,t=s+4;for (int j=0;j<3;j++) bubble(s,t-j);MyMath.swap(a, p+i, s+2);}Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10);int i=partition(p,r,x),j=i-p+1;if (k<=j) return select(p,i,k);else return select(i+1,r,k-j);}Ø复杂度分析§ §C1为直接简单排序时间§C2n为执行for循环的时间§解递归方程得T(n)=O(n)Ø说明：§上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。
这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，，0<ε<1这是使T(n)=O(n)的关键之处当然，除了5和75之外，还有其他选择§上述算法中我们假设元素互不相等已保证划分后子数组不超过3n/4当元素可能相等时，设有m个（将他们集中起来），若j≤k≤j+m-1时返回ai；否则调用select(i+m+1, r, k-j-m)5858 课堂练习Ø习题2-11 O(1)空间子数组换位算法§设a[0,n-1]是一个有n个元素的数组，k是一个非负整数试设计一个算法将子数组a[0,k-1]与a[k,n-1]换位要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间Ø习题2-12 O(1)空间合并算法§设a[0,k-1]和a[k,n-1)已排好序试设计一个算法将这两个子数组合并为排好序的数组a[0,n-1)要求算法在最坏情况下所用的计算时间为O(n)，且只用到O(1)的辅助空间5959 2.10 最接近点对问题Ø问题描述：给定平面上n个点，找其中的一对点，使得在n个点所组成的所有点对中，该点对间的距离最小Ø说明：§严格来讲，最接近点对可能多于一对，为简便起见，我们只找其中的一对作为问题的解。
§一个简单的做法是将每一个点与其他n-1个点的距离算出，找出最小距离的点对即可该方法的时间复杂性是T(n)=n(n-1)/2+n=O(n2)，效率较低§已经证明，该算法的计算时间下界是Ω(nlogn)6060 一维空间中的情形Ø为了使问题易于理解和分析，先来考虑一维的情形此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn最接近点对即为这n个实数中相差最小的2个实数Ø一个简单的办法是先把x1,x2,…,xn排好序，再进行一次线性扫描就可以找出最接近点对，T(n)=O(nlogn)然而这种方法无法推广到二维情形Ø假设我们用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}，其中p3∈S1且q3∈S2Ø能否性时间内找到p3,q3？6161 算法描述及复杂性Ø如果S的最接近点对是{p3,q3}，即|p3-q3|
Ø由于在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的解Ø分割点m的选取不当，会造成|Si|=1，|Sj|=n-1(i+j=1)的情形，使得T(n) =T(n-1)+O(n)=O(n2)这种情形可以通过“平衡子问题”方法加以解决：选取各点坐标的中位数作分割点Ø算法描述：bool CPair1(S, d){n=|S|;if (n<2){d=∞; return false;}m=Blum(S); //S各点坐标中位数S=>S1+S2;//S1={x|x<=m} S2={x|x>m}CPair1(S1, d1);CPair1(S2, d2);p=max(S1);q=min(S2);d=min(d1, d2, q-p);return ture;}Ø复杂性分析：§ §T(n)=O(nlogn)§该算法可推广到二维的情形中去。
6262 二维空间的最接近点对问题Ø下面来考虑二维的情形§选取一垂直线l:x=m来作为分割直线其中m为S中各点x坐标的中位数由此将S分割为S1和S2§递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2 ，如图2-9所示Ø能否性时间内找到p,q？§考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图2-10所示§由d的意义可知，P2中任何2个S中的点的距离都不小于d由此可以推出矩形R中最多只有6个S中的点图2-9距离直线l小于d的所有点图2-10包含q的d×2d矩形R6363 R中至多包含6个S中的点的证明Ø证明：§将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形（如图(a)所示 ）§若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点§设u，v是位于同一小矩形中的2个点，则§因此，distance(u,v)
这与d的意义相矛盾§也就是说，矩形R中最多有6个S中的点Ø极端情形：图(b)是矩形R中恰有6个S中的点的极端情形6464 鸽舍原理?鸽舍原理鸽舍原理，也称“抽屉原理”或利克雷原则，它是一个重要而又基本的数学原理，应用它可以解决各种有趣的问题，并且常常能够得到令人惊奇的结果，许多看起来相当复杂，甚至无从下手的问题，利用它能很容易得到解决 •原理（一）：把多于几个的元素按任一确定的方式分成几个集合，那么一定至少有一个集合中，至少含有两个元素 •原理（二）： 把多于m×n个物体放到n个抽屉里，那么一定有一个抽屉里有m＋1个或者m＋1个以上的物体6565 说明Ø因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者Ø为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d由上面的分析可知，这种投影点最多只有6个Ø因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者对P1中每一点最多只要检查P2中排好序的相继6个点。
6666 算法描述及复杂性分析Ø算法描述：§public static double CPair2(S)§{•n=|S|;•if (n < 2) return ;•m=S中各点x间坐标的中位数;•构造S1和S2；•//S1={p∈S|x(p)<=m}, •S2={p∈S|x(p)>m}•d1=cpair2(S1);•d2=cpair2(S2);•dm=min(d1,d2);•设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；•P2是S2中距分割线l的距离在dm之内所有点组成的集合；•将P1和P2中点依其y坐标值排序；•并设X和Y是相应的已排好序的点列；•通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；•当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；•设dl是按这种扫描方式找到的点对间的最小距离；•d=min(dm,dl);•return d;§}Ø复杂度分析：§ §T(n)=O(nlogn)Ø算法的具体实现：略6767 2.11 循环赛日程表Ø分治法不仅可以用来设计算法，而且再其他方面也有广泛应用：利用分治法设计电路、构造数学证明等。
Ø循环赛日程标问题，设有n=2k个选手要进行循环赛，设计一个满足以下要求的比赛日程表：§每个选手必须与其他n-1个选手各赛一次；§每个选手一天只能赛一次；§循环赛一共进行n-1天Ø按此要求，可以将比赛日程表设计成n行n-1列的表格，i行j列表示第i个选手在第j天所遇到的选手Ø基本思路：按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单这时只要让这2个选手进行比赛就可以了6868 算法描述及示例Ø算法描述：略Ø思考题：§递归形式的算法描述12345678214365873412785643218765567812346587214378563412876543216969 课堂思考Ø为什么必须是2k个运动员的循环赛？Ø设有n个运动员要进行网球循环赛设计一个满足下面要求的比赛日程表：§1，每个选手必须和其他n-1个选手各赛一次；§2，每个选手一天只能赛一次；§3，当n=2k时，循环赛进行n-1天；当n=2k+1时，循环赛进行n天7070 小结Ø递归的概念Ø分治策略的基本思想和相关实例Ø1. 算法分析题§2-1、2-3、2-7、2-14、§2-18、2-19、2-32、2-33。
Ø2. 算法实现题§2-2、2-3、2-4、2-9、2-12、2-147171 。