资源描述：
《算法设计与分析lecture3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、顺序算法的设计技术分治策略动态规划算法贪心算法回溯法与分支估界概率算法1分治策略（DivideandConquer）分治策略的基本思想实例、主要思想、算法描述、注意问题、适用条件递归算法与递推方程两类递推方程的求解降低递归算法复杂性的途径代数变换减少子问题个数预处理减少递归的操作典型实例分析2分治策略的基本思想分治策略的实例----二分检索、归并排序主要思想----划分、求解子问题、综合解算法描述Divide-and-Conquer(P)1.if
2、P
3、≤cthenS(P).2.dividePin
4、toP,P,…,P.12k3.fori=1tok4.y=Divide-and-Conquer(P)ii5．ReturnMerge(y,y,…,y)12k注意问题----连续划分平衡原则适用条件3划分均匀效率较高例1排序算法的比较插入排序----子问题不均衡W(n)=W(n−1)+n−1W(1)=0解得W(n)=O(n2).归并排序----子问题均衡不妨设n=2k.W(n)=2W(n/2)+n－1W(1)=0解得W(n)=O(nlogn).4分治法的适用条件分治法的适用条件分治法能解决的问题一般具
5、有以下特征：分治法能解决的问题一般具有以下特征：问题的规模小到一定程度可以直接求解问题可以归约为若干个相同类型的子问题利用子问题的解可以组合为原问题的解各子问题之间是相互独立的5递归算法与递推方程分治策略的算法分析工具----递推方程两类递推方程kf(n)=∑aif(n−i)+g(n)i=1nf(n)=af()+d(n)b求解方法第一类递推方程:公式法第二类递推方程:迭代法、递归树、Master定理6nf(n)=af()+d(n)b当d(n)为常数时⎧logbaO(n)a≠1f(n)=⎨⎩O(l
6、ogn)a=1当d(n)=cn时⎧O(n)ab⎩7例2芯片测试A报告B报告结论B是好的A是好的A,B都好或A,B都坏B是好的A是坏的至少一片是坏的B是坏的A是好的至少一片是坏的B是坏的A是坏的至少一片是坏的条件：有n=2k块芯片，(好芯片至少比坏芯片多1片),从中挑出一片好芯片问题：说明测试算法，进行复杂性分析8算法1testing1．k←n;2．whilek>3do3．将芯片分成⎣k/2⎦组；4．fori=1to⎣k/2⎦doif
7、2片好，则任取1片留下；else2片同时丢掉；5．k←剩下的芯片数;6．ifk=3then任取2片芯片测试；if1好1坏，取没测的芯片；else任取1片被测芯片；7．ifk=2or1then任取1片9说明：上述算法只是一个概要说明，对于n为奇数的情况需要进一步处理,处理时间为O(n).复杂性分析：设W(n)表示n片芯片测试的次数，则W(n)=W(n/2)+O(n)W(1)=0由Master定理，W(n)=O(n)10例3求一个数的幂问题：计算an,n为自然数传统算法:Θ(n).分治：an/2×a
8、n/2n为偶数an=a(n–1)/2×a(n–1)/2×an为奇数T(n)=T(n/2)+Θ(1)⇒T(n)=Θ(logn).11计算Fibonacci数定义0ifn=0;F=1ifn=1;nF+Fifn≥2.n–1n–20112358132134L通常算法：从F,F,…,根据定义陆续计算01时间为Θ(n)12利用数幂乘法的分治算法.定理n⎡FF⎤⎡11⎤n+1n⎢⎥=⎢⎥FF10⎣nn−1⎦⎣⎦算法T(n)=Θ(logn)..13定理归纳证明Basen=11⎡FF⎤⎡11⎤21⎢⎥=⎢⎥FF1
9、0⎣10⎦⎣⎦Inductivestep(n≥2):⎡FF⎤⎡FF⎤⎡11⎤n+1nnn−1⎢⎥=⎢⎥⋅⎢⎥FFFF10⎣nn−1⎦⎣n−1n−2⎦⎣⎦n−1n⎡11⎤⎡11⎤⎡11⎤=⎢⎥⋅⎢⎥=⎢⎥⎣10⎦⎣10⎦⎣10⎦14降低递归算法复杂性的途径1.代数变换减少子问题个数例4位乘问题设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)=
10、1解得W(n)=O(nlog4)=O(n2)15代数变换AD+BC=(A－B)(D－C)+AC+BD递推方程W(n)=3W(n/2)+cnW(1)=1解W(n)=O(nlog3)=O(n1.59)16位乘问题的其他结果如果将整数分成更多段，用更复杂的方式把它们组合起来，有可能得到更优的算法根据这个思想，最终导致快速傅利叶变换(FastFourierTransform)的产生.该方法也可以看作是一个复杂的分治算法，它能在O(nlogn)时间内求解位乘问题是否存在线性时间算法，目前还没有结果.17例
