第4章 分治法

算法设计与分析计算机与信息学院使用教材★使用教材作者：（美）AnanyLevitin译者：潘彦出版社：清华大学丛书名：国外经典教材·计算机科学与技术第4章分治法★概述：算法概要、算法效率★合并排序★快速排序★折半查找★大整数乘法★Strassen矩阵乘法概述★概述（算法概要、算法效率）分治法是著名的通用算法设计技术，很多非常有效的算法实际上是这个通用算法的特殊实现。基本思想符合人们在解决复杂问题时，常常将其从大到小逐步分解，进而将较易求解的小问题解合并得到原问题的解。这即是“分治法”的分而治之的思想。算法概要1.分解原问题规模为较小的子问题，子问题最好有相同规模；2.求解子问题；(1、2步“分解－求解”过程通常是递归的，直到子问题可简单求解为止)3.合并子问题的解，得到原问题的解（必要的话）。原问题S子问题S1子问题S2……子问题SkS1的解S2的解……Sk的解问题S的解分治算法概要描述分治算法概要描述：1212(){(||)();{,,;1{;(}(,,)}})////////kkiiDivideandConquersstadhocerysdivideintosmallersubsetsssiskyDivideandConquersifthenelsefortodormergeketuyyyrn子集求解个子集递归分解合并算法集合的模|s|：问题s的规模，即s集合的元素个数；分解尺度t：可求解最小子问题的规模。（不需继续分解）分治法应用的一个简例分治法应用的一个简例：——查找最大元素已知S有n个元素，求S的最大元素。不妨设的整数。本问题可设计多种算法，这里用分治法求解：每次将S一分为二，直到分解到仅有2个元素的求解子集为止；求解算法是返回两元素之较大者。2,0mnm1211121222(){2;(||)(,);{,||||||/2;();(/;/)DivideandConquerSearchMaxStStmaxssdivideintotwosmallersubsetSSSmaxDivideandConquerSearchMaxmaxDivifthenreturneidelseranSSandConquerSearchMxStadSSe子集求解算法12(,);/}/}maxmaxmaxurn合并算法分治法应用简例的过程图解分治法应用简例的过程图解已知：S={30,11,42,22,1,55,21,43}有n=23个元素；求：S的最大元素。30,11,42,22{,1,55,21,43}S(1)130,{,4212}1,2S(1)21,5{,251,43}S(2)1{30,11}S(2)2{42,22}S(2)1{1,55}S(2)2{21,43}S(2)130max(2)242max(2)155max(2)243max(1)142max(1)255max55max分治法时间效率（例）分治法时间效率上例的时间效率：——查找最大值输入规模：元素个数n；基本操作：比较操作；效率类别：无最佳、最差、平均效率之分；建立递归算法的递推式并求解得到增长函数的增长率类型：本例求解子集仅2个元素，需比较一次。下面用归纳法分析：①n=2=21：T(n)=T(2)=1。——比较一次②n=4=22：T(n)=2T(4/2)+1。2T(4/2)：求解子集个数为2，求解子集规模4/2。+1：两个子集解需合并一次即比较一次。③n=8=23：T(n)=2T(8/2)+1=2T(4)+1。④n=2k：T(n)=2T(2k/2)+1=2T(2k-1)+1。本例归纳结果：()(/)b1whilen2Tn2Tn21whilen2通用分治递推式及其效率分治法运算时间的通用分治递推式：一个规模n的问题，每次被分为a个子问题，每个子问题规模n/b（上例：a=2,b=2）。为简化分析，假定n是b的乘方即n=bk，k=1,2,3,...,通用分治递推式如下：c：子集(规模为tr)求解时间(常量)；（时间：基本操作数）f(n)：子集分解和子集解合并的时间。（本例比较1次即f(n)=1）解递推式，得到时间效率(主定理)：若：则：()(/),(),rrntTnaTnbtcnnflog(),()(log),(),bddddadnabTnnnabnab()(),dfnnd0,,a1b2c0合并排序★合并排序（非降序）把需要排序的元素集一分为二，对每个子集递归拆分，直到分解到仅有一个元素为止。然后，两两组合为一个有序集。过程示例如下：83267154832683268338262623687154715471175445145712345678合并排序算法合并排序算法(分解+合并)0...//////([0...1]){(1){[][0.../21];[][/21/2...10.../21];(////cop(,,));()}};y;MergeSortAnifncopyAtoBncopyAtoCnMergeSortBMergeSorMergeBCAtnnnC新生成两个临时数组B、C递归拆分递归拆分合并函数分解过程没有额外的基本操作，仅合并排序算法（续）合并排序算法（续）([0...],[0...],[0...]){0;0;0;{(){[][];1;}{[][]//,,////1[][];,,11()()1;}1;}(ijkpqpqipandjMergeBCAijkwijkijkhiledoifAkBiiielseAkCjjjkBiCjqikifp指向第一个元素考虑此处等号的作用？均指向下一个元素)[][...1];[][...1...1];}...1copyCtoApqelskkecjqiopyBtApopq合并排序算法的时间效率分析合并排序算法的时间效率分析输入规模：排序元素的个数n；基本操作：键值的比较操作效率类别：考虑while(ip)and(jq)循环次数决定于循环变量i或j的增加速度：若每次循环都是其中之一如i增值，那么这个循环变量较快达到上限，结束循环，这就是最佳情况。如果两个循环变量轮流交替增加，就有最多的循环次数，这就是最差情况。最佳情况对应的是待排序元素已经排好序了，即B或者C数组其中之一很快合并完成。最差情况对应的是：较小元素轮流来自于两个数组。键值比较次数的递推式：（通用分治递推式）为简化分析，假定n=2k,k=1,2,3,...，即B和C数组元素数相同。也就是说，每次拆分为两个大小相同的子集。(a=b=2)[][]BiCj1()2(()/210)MergefwhilenTnTnwhilenn()(),dfnnd0若。不用解递推式，用定理即得效率类型。合并排序算法的时间效率分析（续）合并排序算法的时间效率分析（续）worst现在分析——本问题分解过程中没有基本操作该函数为合并子集解的比较次数。考虑最差情况，两个循环变量轮流增加，即较小元素轮流来自于两个数组B或C。每次合并时B、C两数组元素个数都是n/2个，需比较n–1次。因此：根据分治法效率主定理：精确解：()Mergefn1()1(),1Mergefnnnd1:()2(/2)(1)worstworstnTnTnn2()1logworstnTnnn用替换法可解递推方程。较复杂,略。快速排序★快速排序（非降序）算法策略对给定的待排序数组进行拆分，与合并排序对数组的拆分不同。合并排序是按照元素位置拆分（数组中间位置），而快速排序是按照元素值拆分，得到排序分区(Partition)，拆分处称为分裂点(Splitposition)。递归拆分下去，直到分区仅有一个元素为止。该法在建立分区时就完成了对元素的重新排列，因此拆分结束，即排序结束。分区的特点如下：A[0]…A[s-1]A[s]A[s+1]…A[n-1]都≤A[s]都≥A[s]无序的分裂点无序的快速排序算法([]){()([...]);([...]);//:.////([...])/...1;///1}QuickSortAifLRQfalseLRonlyoneelementsisasplitpositionleftpartiuickSortALQuickSortARtionrightpartitionLsPartitionLRRssA关键是分区Partition函数分区的确定两次扫描法确定分区（Partition）A[L...R]中轴：为了确定分区，首先要初选一个元素即中轴，其他元素与中轴比较以确定分裂点。中轴，即分裂点的初值。选择中轴有多种方法，这里采用简单策略：选数组第一个元素p=A[L]。两次扫描法：(从左向右扫描一次，从右向左扫描一次)左→右：从第2个元素开始，把它与中轴比较，直到遇到一个大于等于中轴的元素为止。（i→）左←右：从最后元素开始，把它与中轴比较，直到遇到一个小于等于中轴的元素为止。（←j）根据两次扫描的i、j指针是否相交，分三种情况：p...≤p≥p......≤p≥p...A[L...R]ij两次扫描法确定分区(续)p...≤p≤p≥p≥p...A[L...R]ijp...≤p=p≥p≥p...A[L...R]ij将ij和i=j两种情况相结合即i≥j，就交换swapA[L]andA[j]，得到分裂点s=j，生成了分区。（生成两个或一个分区）两次扫描法确定分区的算法伪码两次扫描法确定分区的算法伪码Partition(A[L...R]){p←A[L];//选择中轴i←L+1;j←R;//左右扫描位置指针。左扫描没找到时，i停在L+1位置while(true){while(A[i]p)and(i≤R)doi←i+1;//左扫描（限位）while(A[j]p)and(j≥L)doj←j-1;//右扫描（限位）if(i≥j)thenbreak;//左右扫描已交叉，退出循环swap(A[i],A[j]);//左右扫描未交叉}swap(A[L],A[j]);return(j);//返回分裂点j}快速排序算法的时间效率分析快速排序算法的时间效率分析输入规模：排序元素个数n；基本操作：键值比较A[i]p和A[j]p。说明：这里选两个操作，因为这两个操作几乎同样耗费时间，所以把它们都作为基本操作。效率类别：由于每次分裂点的位置不同，分裂后所得到的两个子分区大小（元素个数）就不同，即子排序问题规模不同，这将导致不同的时间效率（子分区排序的基本操作次数不同）。因此，快速排序存在最佳、最差、平均效率。最佳时间效率：每次分裂点都在本区域的中点，将本区域一分为二，得到大小相同的两个子区域。左右扫描指针交叉时满足：i=j。左右扫描键值比较总次数n=(n-1)/2+(n-1)/2+1。最佳情况下每次分裂为原问题规模一半的子问题。由通用分治递推式和主定理可得：T(1)=0;whilen1:T(n)=2T(n/2)+f(n)=nlog2n,n=2k偶数注意：这里f(n)函数与合并子问题解无关，因本算法没有合并过程。而是建立分区需n次键值比较（n为偶数也是n次），故f(n)=n。奇数:n=2k+1,k0最差时间效率最差时间效率：每次的分裂点都在极端位置即区域两端，分裂所得的两子区域其一为空，另一子区只比原区域少一个元素(分裂点在外)。此种情况发生在：输入序列已被排序了。如：A[0...n-1]为严格递增，中轴选p=A[0]，左扫描i停在A[1]，右扫描j停在A[0]，左右扫描交叉，分裂点在0位置处。分裂后左子区为空；右子区为A[1...n-1]。为建立分区，需作1+n次键值比较（基本操作）。在建立分区后，算法继续对右子区A[1...n-1]排序，直到右子区为A[n-2,n-1]时止。总的键值比较次数为：T(n)=(n+1)+n+(n–1)+...