分治算法（Divide & Conquer Algorithm）

《分治算法（Divide & Conquer Algorithm）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分治算法(Divide&ConquerAlgorithm)宫秀军天津大学计算机科学与技术学院gongxj@tju.edu.cn提纲分治法基本原理应用归并排序快速排序选择问题复杂性的下限最大最小问题的下限排序算法的下限14.1分治法思想分治法设计算法的思想将问题分成(divide)多个子问题；递归地(conquer)解决每个子问题；将子问题的解合并(combine)成原问题的解。分治法常常得到递归算法Merge-Sort,QuickSortDiscreteFouriertransform(FFT).算法复杂性分析MastermethodSubstitutionmetho

2、d例14-1[找出伪币]现有16个硬币,其中有一个是伪币，并且伪币重量比真币轻。试用一台天平找出这枚伪币。两两比较,最坏情形需8次比较找出伪币。分治法仅需4次比较找出伪币。ComputeanProblem:Computean,wheren∈N.Naivealgorithm:Θ(n).Divide-and-conqueralgorithm:an=an/2∙an/2ifniseven;an=a(n–1)/2⋅a(n–1)/2⋅aifnisodd.ComplexityT(n)=T(n/2)+Θ(1)Master方法,a=1b=2Case2:logba=0,k＝0T(n)=Θ

3、(lgn)例14-2[金块问题]问题有若干金块试用一台天平找出其中最轻和最重的金块.等价于n个数中找出最大和最小的数.直接求解1：先找出最大值,然后在剩下的n-1个数中再找出最小值.需2n-3次比较.例14-2直接求解2：最大最小值同时进行查找funcminmax(Ta[],n,T&max,T&min){min←a[0];max←a[0];Fori←1ton-1doifa[i]maxmax←a[i]}当输入数组为顺序时,算法要做2(n-1)次比较当输入数组为逆序时,算法要做n-1次比较例14-2分治法求解intminmax

4、-dc(TA[0,n-1],T&max,T&min)ifn<1max←min←a[0],return;elsem←n/2minmax-dc(A[0,m-1],max1,min1),minmax-dc(A[m,n-1],max2,min2),max←max(max1,max2),min←min(min1,min2),return.例14-2（解续）设c(n)为使用分治法所需要的比较次数,假设n=2k则有:c(n)=1,n=2;c(n)=2c(n/2)+2,n≥2.复杂性分析Master方法给出c(n)=Θ(n).迭代展开可得:c(n)=(3n/2)-2。程序14-1找出

5、最小值和最大值的非递归程序程序14-1找出最小值和最大值的非递归程序程序14-1找出最小值和最大值的非递归程序算法14.1分析当n为奇数时,n=2m+1,比较m对相邻元素,比较次数为3*m=3*(n-1)/2=3n/2-3/2=[3n/2]-1/2-3/2=[3n/2]-2[]表示向上取整.当n为偶数时,n=2m,比较m-1对相邻元素比较次数为1+3*(m-1)=1+3*(n-2)/2=1+3n/2-3=[3n/2]-2该算法所用比较次数最少例14-3[矩阵乘法]两个n×n阶的矩阵A与B的乘积是另一个n×n阶矩阵C，C的元素为:C(i,j)=∑kA(i,k)B(k,j

6、)template;voidMatrixMulti(T**A,T**B,T**C,intn){for(inti=0;i

7、×2matrixof(n/2)×(n/2)submatrices8multsof(n/2)×(n/2)submatrices4addsof(n/2)×(n/2)submatricesrecursive复杂性分析T(n)=8T(n/2)+Θ(n2)（Θ(n2)－4个(n/2)阶矩阵加法的计算时间）nloga=nlog8=n3⇒CASE1⇒T(n)=Θ(n3)从分治法没得到好处！算法基本观点合并分块矩阵以减少乘法次数2×2矩阵相乘可用7次乘法.所以仅需7次递归调用.T(n)=7T(n/2)+Θ(n2)Master方法:logba=log27,case1: