算法课课件3

座位分布图1-4计科1301-13045-8通信1301-13049-10物联1301-130210872165讲台9Lecture5-递归与分治策略姜文君[e-mail]湖南大学-算法设计与分析课程办公室：信息科学与工程学院院楼3262014-2015第二学期算法设计与分析B【CS06081】2015-10-123回顾算法、案例、前沿三条线，三线并抓效果好。递归分治案例多，二分搜索为经典，大整数分解做乘法，分解变换巧解题。算法设计与分析B【CS06081】2015-10-124主要内容二分搜索技术、大整数乘法并行文件系统ACM竞赛培训算法设计与分析B【CS06081】2015-10-125递归与分治策略•递归的概念•分治法的基本思想•案例分析–棋盘覆盖(通3:王鑫淼,游韵埼,孔淼)–归并排序(通4:魏佑安,张翰霖,徐明)–快速排序（科3：朱元坤，赵桔，郑金榜）–线性时间选择（科4：吴文俊孔斌彦马伟郗茜）–最接近点对问题(物1:刘悦,卢华丽,李超)–循环赛日程表(物2:王泓力,韩雨薇,赵娣)算法设计与分析B【CS06081】2015-10-126在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。案例分析3-棋盘覆盖算法设计与分析B【CS06081】2015-10-127当k0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。案例分析3-棋盘覆盖算法设计与分析B【CS06081】2015-10-128voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(drtr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(drtr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr=tr+s&&dctc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr=tr+s&&dc=tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}复杂度分析T(n)=O(4k)渐进意义下的最优算法00)1()1(4)1()(kkOkTOkT案例分析3-棋盘覆盖算法设计与分析B【CS06081】2015-10-129基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){if(leftright){//至少有2个元素inti=(left+right)/2;//取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合并到数组bcopy(a,b,left,right);//复制回数组a}}复杂度分析T(n)=O(nlogn)渐进意义下的最优算法11)()2/(2)1()(nnnOnTOnT案例分析4-合并排序算法设计与分析B【CS06081】2015-10-1210算法mergeSort的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]案例分析4-合并排序算法设计与分析B【CS06081】2015-10-1211最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n)案例分析4-合并排序算法设计与分析B【CS06081】2015-10-1212在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}案例分析5-快速排序算法设计与分析B【CS06081】2015-10-1213templateclassTypeintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到左边区域//将x的元素交换到右边区域while(true){while(a[++i]x);while(a[--j]x);if(i=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}初始序列{6,7,5,2,5,8}j--;ji{5,7,5,2,6,8}i++;ji{5,6,5,2,7,8}j--;ji{5,2,5,6,7,8}i++;ji完成{6,7,5,2,5,8}{5,2,5}6{7,8}案例分析5-快速排序算法设计与分析B【CS06081】2015-10-1214templateclassTypeintRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)案例分析5-快速排序算法设计与分析B【CS06081】2015-10-1215给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素应用实例：网页排序（Topk/n）案例分析6-线性时间元素选择算法设计与分析B【CS06081】2015-10-1216•基本思路–分解问题、缩小规模–利用快速排序思想、每次递归处理部分子数组–利用中位数，构造线性时间复杂度的算法案例分析6-线性时间元素选择算法设计与分析B【CS06081】2015-10-1217仿快速排序的randomizedSelect算法。templateclassTypeTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。案例分析6-线性时间元素选择与快排不同：只对子数组之一递归处理。基本思想：对输入数组进行递归划分算法设计与分析B【CS06081】2015-10-1218如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0ε1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。案例分析6-线性时间选择构造一个看看！算法设计与分析B【CS06081】2015-10-1219将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素（忽略该组）。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。案例分析6-线性时间选择利用中位数构造一个线性时间方案！算法设计与分析B【CS06081】2015-10-1220设所有元素互不相同。在这种情况下，因为在每一组中有2个元素小于本组的中位数，有⌊(n/5-1)*1/2*2⌋=⌊n/5-1⌋个小于基准x;基准x位于1/2*⌊n/5-1⌋，即n/5个中位数中又有⌊(n-5)/10⌋个小于基准x。因此，找出的基准x至少比⌊3(n-5)/10⌋个元素大；同理，基准x也至少比⌊3(n-5)/10⌋个元素小。而当n≥75时，⌊3(n-5)/10⌋≥n/4。所以按此基准划分所得的2个子数组的长度都至少缩短1/4。案例分析6-线性时间选择例如，对于包含341个元素的序列，可分为⌈341/5⌉=69组，忽略只含一个元素的组。剩余68组每组中至少2个元素该组中位数，且至少一半的中位数基准x，则68组中x的元素个数为68*2*1/2=68；中位数中x的个数为68*1/2=34。共68+34=102,102341/4。算法设计与分析B【CS06081】2015-10-1221TypeSelect(Typea[],intp,intr,intk){if(r-p75){用某个简单排序算法对数组a[p:r]排序;returna[p+k-1];};for(inti=0;i=(r-p-4)/5;i++)将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;//找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}案例分析6-线性时