算法与计算复杂性课程(3)分治

《算法与计算复杂性课程(3)分治》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、顺序算法的设计技术•分治策略•动态规划算法•回溯法与分支估界•贪心算法•概率算法1分治策略（DivideandConquer）•分治策略的基本思想¢实例、主要思想、算法描述、注意问题•递归算法与递推方程¢两类递推方程的求解•降低递归算法复杂性的途径¢代数变换减少子问题个数¢预处理减少递归的操作•典型实例分析2分治策略的基本思想分治策略的实例----二分检索、归并排序主要思想----划分、求解子问题、综合解算法描述Divide-and-Conquer(P)1.if

2、P

3、≤cthenS(P).2.dividePintoP,P,…,P.12k3.fori=1tok4.y=Divide-and-C

4、onquer(P)ii5．ReturnMerge(y,y,…,y)12k注意问题----连续划分平衡原则3递归算法与递推方程•分治策略的算法分析工具----递推方程•两类递推方程kf(n)=∑aif(n−i)+g(n)i=1nf(n)=af()+d(n)b•求解方法迭代法、递归树、Master定理4典型的递推方程nf(n)=af()+d(n)b当d(n)为常数时⎧logbaO(n)a≠1f(n)=⎨⎩O(logn)a=1当d(n)=cn时⎧O(n)ab⎩5实例例1芯片测试A报告B报告结论B是好的A是好的A,B都好或A,B都坏B

5、是好的A是坏的至少一片是坏的B是坏的A是好的至少一片是坏的B是坏的A是坏的至少一片是坏的条件：有n片芯片，(好芯片至少比坏芯片多1片),问题：使用最少测试次数，从中挑出1片好芯片要求：说明测试算法，进行复杂性分析6算法1．k←n2．whilek>3do3．将芯片分成⎣k/2⎦组4．fori=1to⎣k/2⎦do5.if2片好，则任取1片留下6.else2片同时丢掉7．k←剩下的芯片数8．ifk=39.then任取2片芯片测试10.if1好1坏，取没测的芯片11.else任取1片被测芯片12．ifk=2or1then任取1片7分析•说明上述算法只是一个概要说明，对于n为奇数的情况需要进一步处

6、理,处理时间为O(n).•复杂性分析设W(n)表示n片芯片测试的次数，则W(n)=W(n/2)+O(n)W(1)=0由Master定理，W(n)=O(n)8实例例2求一个数的幂问题：计算an,n为自然数传统算法:Θ(n)分治法an/2×an/2n为偶数an=a(n–1)/2×a(n–1)/2×an为奇数T(n)=T(n/2)+Θ(1)⇒T(n)=Θ(logn).9计算Fibonacci数Fibonacci数的定义⎧0ifn=0⎪Fn=⎨1ifn=1⎪F+Fifn>1⎩n−1n−201123581321…通常算法：从F,F,…,根据定义陆续相加01时间为Θ(n)10利用数幂乘法的分治算法定理

7、1设{F}为Fibonacci数构成的数列，那么n.n⎡Fn+1Fn⎤⎡11⎤⎢⎥=⎢⎥⎣FnFn−1⎦⎣10⎦证明:对n进行归纳算法：令矩阵⎡11⎤，用分治法计算MnM=⎢⎥⎣10⎦T(n)=Θ(logn)..11提高算法效率的途径1方法一：代数变换减少子问题个数例3位乘问题设X,Y是两个n位二进制数，n=2k,求XY.传统算法W(n)=O(n2)分治法令X＝A2n/2+B,Y=C2n/2+D.XY=AC2n+(AD+BC)2n/2+BDW(n)=4W(n/2)+cn,W(1)=1解得W(n)=O(nlog4)=O(n2)12代数变换AD+BC=(A－B)(D－C)+AC+BD递推方程W

8、(n)=3W(n/2)+cnW(1)=1解W(n)=O(nlog3)=O(n1.59)13矩阵乘法例4A,B为两个n阶矩阵，n=2k,计算C=AB.传统算法W(n)=O(n3)分治法将矩阵分块，得⎛A11A12⎞⎛B11B12⎞⎛C11C12⎞⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎜⎟⎝A21A22⎠⎝B21B22⎠⎝C21C22⎠其中C=AB+ABC=AB+AB11111112211211121222C=AB+ABC=AB+AB21211122212221122222递推方程W(n)=8W(n/2)+cn2W(1)=1解W(n)=O(n3).14变换方法M=A(B－B)1111222M=(A+A)B21

9、11222M=(A+A)B3212211M=A(B－B)4222111M=(A+A)(B+B)511221122M=(A－A)(B+B)612222122M=(A－A)(B+B)711211112C=M+M－M+M115426C=M+M1212C=M+M2134C=M+M－M－M22513715Strassen矩阵乘法递推方程是W(n)=7W(n)+18(n)222W(1)=1由Master定理得W(n)=O(nlog2