算法设计与分析 课件 许瑾晨 第四章 分治法

算法设计与分析算法设计-分治信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版一二三算法引例算法基本思想分治法解题步骤分治法适用条件分治法代码框架典型应用二分搜索快速排序归并排序棋盘覆盖大整数乘寻找假币寻找金块重点掌握：1.算法的基本思想2.平衡划分原则

3.分治法的优化方法算法设计与分析分治引例-寻找假币信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版已知条件：一个装有16枚硬币的袋子，其中有一枚硬币是伪造的，并且伪造的硬币比真的硬币要轻一些。工具：一台天枰，可用来比较两组硬币的重量。问题：找出这枚伪造的硬币。方法一任意取1枚硬币，与其它硬币进行比较，若发现轻者，则轻者为假币。最多可能有15次比较。123456789101112131415方法二将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为假币。最多可能有8次比较。12345678方法三第1组第2组1次比较第1组第2组1次比较第1组第2组1次比较第1组第2组1次比较共4次比较每次将待比较硬币分为相等两组，共4轮比较。算法分析与比较上述三种方法，分别需要比较15次，8次，4次。比较次数差异的根本原因是什么?方法1：每枚硬币都至少进行了一次比较，而有一枚硬币进行了15次比较。方法2：每一枚硬币只进行了一次比较。方法3：一次比较可以将硬币的范围缩小到原来的一半，充分利用了只有1枚假币的基本性质。方法四第1组第2组1次比较第1组第2组1次比较第3组共3次比较不等相等1次比较1次比较首轮采取平分，第二轮采取三分法。测试选择题：现有24个硬币，其中有1个硬币是假币（重量更轻），利用一个天枰，在最坏情况下，最少需要（）次比较。A：3B：4C：5D：6方法二8方法三4方法四3分治法的主要内容之一：如何实现更好的问题划分比较次数算法设计与分析分治引例-寻找金块信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版已知条件：某老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。工具：一台天枰，可用来比较金块的重量。问题：用最少的比较次数找出最轻和最重的金块。方法一假设袋中有n个金块：

先找最重的金块：n-1次比较

再找最轻的金块：n-2次比较方法一算法描述：max:=a[1];fori:=2tondo//n-1次比较，找n个元素中最大ifa[i]>maxthenbegin max:=a[i];j:=i;end;fori:=j+1tondoa[i-1]:=a[i];//去掉最大的数a[j]min:=a[1];fori:=2ton-1do//n-2次比较，找剩下元素中最小ifa[i]<minthenbegin min:=a[i];方法二n≤2，找出最重和最轻的金块，一次比较；n＞2step1:把金块平分成两个小袋A和B；step2:分别找出在A和B中最重和最轻的金块（HA与LA、HB和LB分别表示A和B中最重和最轻的金块）；step3:比较HA和HB找到最重的金块；比较LA和LB找到最轻的金块。

step2中，若n>2，则递归的继续平分为两部分。方法二10，8，2，4，5，3，9，110，8，2，45，3，9，110，82，45，39，1方法二10，82，45，39，1第一轮比较4次比较10，42，85，93，1第二轮比较4次比较10，29，110，92，1第三轮比较10，12次比较共10次比较算法分析当有8个金块的时候，方法1需要比较15次，方法2只需要比较10次。比较次数差异的根本原因是什么?方法2：对金块实行了分组比较。对于n(n是2的次幂)枚金块，比较次数c(n)：

方法1：c(n)=(n-1)+(n-2)=2n-3

方法2：c(n)=2c(n/2)+2,c(2)=1,=3n/2-2淘汰赛法思想：先按淘汰赛法找出最大项；再在首轮败者中（包括首轮未参加比较的项）找出最小项。方法三1.找出最大项需要n-1次比较2.参加找“最小”的项数至多有

n/2

个，故可用

n/2-1次比较找到最小项。共：n-1+n/2-1=3n/2-2次比较。【定理】：用比较算法类中的任一算法，找出n项表中的最大项和最小项，在最坏情况下，至少要比较3n/2-2次。结论：解决该问题的淘汰赛法、分治法，在最坏情况下的比较次数都是3n/2-2

。故它们在最坏情况下都是最优的。

测试

算法设计与分析分治法-基本思想信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版寻找假币和金块问题的共同点把问题分解为规模更小的问题求解小规模问题得到原问题的解

算法策略：分而治之总体思想适用条件代码框架一二三T(n)将要求解的较大规模的问题分割成k个更小规模的子问题。对k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。T(n/m)T(n/m)T(n/m)T(n/m)………………………………边界和递归式T(n)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。T(n/m)T(n/m)T(n/m)T(n/m)………………………………分治法的思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治就是“分而治之”，实质是将原问题分成n个规模较小而结构与原问题相似的子问题，然后递归地解这些子问题，最后合并其结果就得到原问题的解。子问题求解(conquer)问题S问题S1……问题S2问题Sn问题SiS1的解……S2的解Sn的解Si的解S的解问题的分解(divide)子问题解的合并(combine)选择题分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解，要求原问题和子问题的问题规模

，问题性质

。A：相同，相同B：相同，不同C：不同，相同D：不同，不同测试分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//递归求解各子问题

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

//将子问题的解合并为原问题的解

returnmerge(y1,...,yk);}分治法设计的平衡原则：使子问题的规模大致相同测试：博彩诈骗为什么可以成功背景设定你是一位足球迷，当前正在进行某个足球赛事，你在看球的同时想娱乐一下，参与一下博彩事业，当前正在进行16进8的比赛，你想买张彩票，正在你准备下注时，收到了一个信息。选择题：1信息中说：A队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑无论你信不信，你买了A队胜，此后，当A和C比赛时，你又收到了信息2信息中说：C队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑无论你信不信，你买了C队胜，此后，当C和E比赛时，你又收到了信息3信息中说：C队肯定会在这场比赛中获胜，此时你会相信吗？A：不信 B：信 C：半信半疑你买了C队胜，决赛时，你又收到了信息4要想知道比赛结果，需要付费查看，此时你会付费吗?A：会

B：不会选择：ACB

A学以致用才是学习的最终目的，日常中的各种现象，都可能被解释，主要看大家的思维方式，做任何事我们都要用正确的思维方式。算法设计与分析分治—二分搜索信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版问题描述：给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。算法思想：比较x和a[mid]，若x==a[mid]，则x在L中的位置就是mid；若x<a[mid]，在a[mid]的前面查找x；若x>a[mid]，在a[mid]的后面查找x。算法思想：x与中间位置的元素进行比较，相等则查找成功；否则，如果x较小，继续在左边的有序区中二分搜索；如果x较大，则继续在右边的有序区中二分搜索，直到有序区中没有元素。代码4-2：二分搜索的递归实现defBinarySearch(a,x,h,r):#在数组a[h]到a[r]中搜索元素xifr>=h:m=(h+r)//2#将数列二分，并向下取整

ifx==a[m]:#递归出口

returnmifx<a[m]:r=m-1#如果右边一半第一个元素比x大，只搜索左边一半，更新右端点

else:h=m+1#如果左边一半最后一个元素比x大，只搜索右边一半，更新左端点

returnBinarySearch(a,x,h,r)#递归

else:return-1if__name__=='__main__':n=int(input())x=int(input())a=list(map(int,list(input().split())))#将list中空格去掉并将str类型转为int类型

print(BinarySearch(a,x,0,n-1))以比较操作为基本操作的算法类中，搜索有序表给定元素的问题。二分搜索算法在平均、最坏情况下都是最优算法。时间复杂度分析最好情况

x在中间位置出现，只需要1次比较。最坏情况平均情况

按比较次数为1、2、3…、1+logn，把2n+1种输入分类。求解得A(n)=Θ(logn)。W(n)=1+W(n/2)W(1)=1利用主定理第二条，求解得W(n)=Θ(logn)测试选择题：在二分搜索的递归实现中，最坏情况下的递推式为（）A：W(n)=1+W(n/2)B：W(n)=1+W(n-1)C：W(n)=n+W(n/2)D：W(n)=n+W(n-1)算法设计与分析分治—二分搜索—平均时间复杂度分析信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版平均时间复杂度分析分析输入种类n+(n+1)=2n+1In+1In+2In+3In+n+1In+n确定每种输入出现的概率假定每种输入出现的概率相等（这是平均时间复杂度分析的通常做法）I1I2I3I4I5InIn-1……平均时间复杂度分析确定不同输入需要的基本操作次数1次比较2次比较3次比较4次比较5次比较

5次比较平均时间复杂度分析确定不同输入需要的基本操作次数

令St为需要比较t次的输入种类，有S1=1，S2=2，S3=4，S4=8，S5=48

平均时间复杂度分析根据公式计算并化简

测试

算法设计与分析分治—快速排序信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版基本思想：在数组中任选一个元素作为基准元素，用它和其他每

个元素比较，小于基准的放在它左边，大于等于基准

的放在它右边。分别对基准的左右两个无序区进行快速排序，直到无

序区只有一个元素。分治defQuickSort(a,p,r):#对a[p]到a[r]的快速排序

ifp<r:q=Partition(a,p,r)#划分函数，划分位置

QuickSort(a,p,q-1)#对左半端快速排序

QuickSort(a,q+1,r)#对右半段快速排序代码4-5：快速排序的一次划分过程defPartition(a,p,r):i=p#左端的哨兵j=r+1#右端的哨兵x=a[p]#选择最左端元素为基准元素whileTrue:i+=1whilea[i]<xandi<=r:i+=1j-=1whilea[j]>x:j-=1ifi>=j:breaka[i],a[j]=a[j],a[i]

a[p]=a[j]a[j]=xreturnj代码4-5：快速排序的一次划分过程defPartition(a,p,r):i=p#左端的哨兵j=r+1#右端的哨兵x=a[p]#选择最左端元素为基准元素whileTrue:i+=1whilea[i]<xandi<=r:i+=1j-=1whilea[j]>x:j-=1ifi>=j:breaka[i],a[j]=a[j],a[i]

a[p]=a[j]a[j]=xreturnj时间复杂度分析最好情况

T(n)=2T(n/2)+n-1T(2)=1

应用主定理第二条，T(n)=Θ(nlogn)最坏情况

W(n)=W(n-1)+n-1W(1)=1W(n)=O(n2)时间复杂度分析平均情况

问题的n!个输入被分成了n个子类：

一类是基准项x在位置1；

一类是基准项x在位置2； ……

一类是基准项x在位置n。假定：i取1,2,…,n的可能性相等

时间复杂度分析平均情况

差消迭代法

直接迭代法

lnn=ln2lognA(n)=O(nlogn)以比较操作为基本操作的算法类中，求解排序问题。快速排序算法在平均情况下是最优算法。时间复杂度分析最好情况

T(n)=2T(n/2)+n-1T(2)=1T(n)=Θ(nlogn)最坏情况平均情况

W(n)=W(n-1)+n-1W(1)=1W(n)=Θ(n2)A(n)=O(nlogn)最好情况

T(n)=2T(n/2)+n-1T(2)=1T(n)=Θ(nlogn)最坏情况平均情况

测试

算法设计与分析分治—归并排序信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。voidMergeSort(int*a,intleft,intright){if(left<right){//至少有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)渐近意义下的最优算法算法mergeSort的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]基本思想：基本思想：将待排序元素R[0]到R[n-1]看成n个长度为1的数组，把这些数组两两归并，得到

n/2

个有序的数组。然后，再把这

n/2

个数组两两归并，如此重复，直到最后得到一个长度为n的数组为止。defMergeSort(R,n):#对长度为n的数组R进行排序

length=1R1=[None]R1=R1*nwhilelength<n:MergePass(R,R1,length,n)length*=2MergePass(R1,R,length,n)length*=2#一趟两两归并defMergePass(R,R1,length,n):#length是本趟归并有序数组长度，

i=0whilei+2*length-1<n:#循环条件为右端点不越界

Merge(R,R1,i,i+length-1,i+2*length-1)i=i+2*length#更新iifi+length-1<n-1:#当右端点越界，但是右半段仍有数需要合并

Merge(R,R1,i,i+length-1,n-1)else:#其他情况

forjinrange(i,n):R1[j]=R[j]MergePass对数组元素做一趟合并归并排序：治、合。Merge:时间复杂度分析最坏情况平均情况

W(n)=A(n)=O(nlogn)归并排序比较操作算法类中的最优算法测试

判断题：对于归并排序算法，算法的平均时间复杂度A(n)和最坏时间复杂度W(n)的关系是（）A:A(n)>W(n)B:W(n)>A(n)C:A(n)=W(n)算法设计与分析分治—棋盘覆盖信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版问题描述解题思路算法设计一二三问题描述：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为特殊方格（蓝色），且称该棋盘为特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘。特殊方格位于某个较小子棋盘中，其余3个子棋盘中无特殊方格。为了统一子问题，将3个无特殊方格的子棋盘转化为特殊棋盘，用一个L型骨牌覆盖这3个较小棋盘的会合处，将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1数据结构：棋盘：2k×2k,大小用size(初始为k)表示特殊方格：左上角所在坐标(dr,dc)，棋盘左上角坐标为(0,0)L型骨牌：每个L型骨牌有一个唯一编号，从1开始2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1算法思路：判断特殊方格所在位置，如果1）在左上区域，直接递归求解；否则，覆盖右下角方格，再递归求解2）在右上区域，直接递归求解；否则，覆盖左下角方格，再递归求解3）在左下区域，直接递归求解；否则，覆盖右上角方格，再递归求解4）在右下区域，直接递归求解；否则，覆盖左上角方格，再递归求解defchessBoard(tr,tc,dr,dc,size):ifsize==1:returnglobaltile,boardt=tile#L型骨牌号

tile+=1s=size//2#分割棋盘

#覆盖左上角子棋盘

ifdr<tr+sanddc<tc+s:#特殊方格在此棋盘中

chessBoard(tr,tc,dr,dc,s)else:#此棋盘中无特殊方格

board[tr+s-1][tc+s-1]=t#用t号L型骨牌覆盖右下角

chessBoard(tr,tc,tr+s-1,tc+s-1,s)#覆盖其余方格

#覆盖右上角子棋盘

ifdr<tr+sanddc>=tc+s:chessBoard(tr,tc+s,dr,dc,s)else:board[tr+s-1][tc+s]=t#用t号L型骨牌覆盖左下角

chessBoard(tr,tc+s,tr+s-1,tc+s,s)#覆盖左下角子棋盘

ifdr>=tr+sanddc<tc+s:chessBoard(tr+s,tc,dr,dc,s)else:board[tr+s][tc+s-1]=t#用t号L型骨牌覆盖右上角

chessBoard(tr+s,tc,tr+s,tc+s-1,s)#覆盖右下角子棋盘

ifdr>=tr+sanddc>=tc+s:chessBoard(tr+s,tc+s,dr,dc,s)else:board[tr+s][tc+s]=t#用t号L型骨牌覆盖左上角

chessBoard(tr+s,tc+s,tr+s,tc+s,s)复杂度分析T(n)=O(4k)渐进意义下的最优算法测试选择题：对于一个4*4的特殊棋盘而言，利用分治法进行棋盘覆盖，第2个被覆盖的方格的坐标为（）。（坐标用方格最坐上角的位置表示，(0,0)则表示最左上角的方格）A:(0,0)B:(1,2)C:(1,0)D:(1,1)不同角度看问题棋盘覆盖问题展现出两个方面的信息：一方面说明了并