文档介绍：分治算法(Divide&ConquerAlgorithm)宫秀军天津大学计算机科学与技术学院******@(divide)多个子问题;递归地(conquer)解决每个子问题;bine)成原问题的解。分治法常常得到递归算法Merge-Sort,QuickSortDiscreteFouriertransform(FFT).算法复杂性分析MastermethodSubstitutionmethod例14-1[找出伪币]现有16个硬币,其中有一个是伪币,并且伪币重量比真币轻。试用一台天平找出这枚伪币。两两比较,最坏情形需8次比较找出伪币。putean,wheren∈:Θ(n).Divide-and-conqueralgorithm:an=an/2∙an/2ifniseven;an=a(n–1)/2⋅a(n–1)/2⋅plexityT(n)=T(n/2)+Θ(1)Master方法,a=1b=2Case2:logba=0,k=0T(n)=Θ(lgn)例14-2[金块问题]:先找出最大值,然后在剩下的n---2直接求解2:最大最小值同时进行查找funcminmax(Ta[],n,T&max,T&min){min←a[0];max←a[0];Fori←1ton-1doifa[i]<minmin←a[i]elseifa[i]>maxmax←a[i]}当输入数组为顺序时,算法要做2(n-1)次比较当输入数组为逆序时,算法要做n-1次比较例14-2分治法求解intminmax-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),-2(解续)设c(n)为使用分治法所需要的比较次数,假设n=2k则有:c(n)=1,n=2;c(n)=2c(n/2)+2,n≥(n)=Θ(n).迭代展开可得:c(n)=(3n/2)-2。程序14-1找出最小值和最大值的非递归程序