资源描述：
《北大屈婉玲算法分析课件 2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章分治策略（DivideandConquer）212.1分治策略的基本思想2.1.1两个熟悉的例子2122.1.2分治算法的一般性描述2.2分治算法的分析技术2.3改进分治算法的途径2.3.1通过代数变换减少子问题个数2.3.2利用预处理减少递归内部的计算量2.4典型实例2.4.1快速排序算法2.4.2选择问题2.4.3n－1次多项式在全体2n次方根上的求值12.1.1两个熟悉的例子二分检索算法212.1BinarySearch(TlT,l,r,x)输入：数组T，下标从l到r；数x输出：j//如果x在T中，j为下标；否则为01.l←1;r←n2h2.wh
2、ililel≤rdo3.m←⎣(l+r)/2⎦4i4.iffT[m]=xthenreturnm//x恰好等于中位元素5.elseifT[m]>mthenr←m−16l6.elsel←m+17.return0二分归并排序MergeSort（见第1章）2时间复杂度分析二分检索最坏情况下时间复杂度W(n)满足⎧⎢n⎥⎪W(n)=W()+1⎢⎥⎨⎣2⎦⎪⎩W(1)=1可以解出W(n)=⎣logn⎦＋1.二分归并排序最坏情况下时间复杂度W(n)满足⎧n⎪W(n)=2W()+n−1⎨2⎪⎩W(1)=0可以解出W(n)=nlogn−n＋1.2.1.2分治算法的一般性描述分
3、治算法Divide-and-Conquer(P)1.if
4、P
5、≤cthenS(P).2.dividePintoP,P,…,P.12k3.fori=1tok4.y=Divide-and-Conquer(P)ii5．ReturnMerge(y,y,…,y)12k算法时间复杂度的递推方程⎧W(n)=W(
6、P1
7、)+W(
8、P2
9、)+...+W(
10、Pk
11、)+f(n)⎨⎩W(c)=C一般原则：子问题均匀划分、递归处理42.2分治算法的分析技术分治策略的算法分析工具：递推方程两类递推方程kf(n)=∑aif(n−i)+g(n)i=1nf(n)=af()+d(n)b求解方法
12、第一类方程：迭代法、换元法、递归树、尝试法第二类方程：迭代法、递归树、主定理5递推方程的解方程T(n)=aT(n/b)+d(n)d(n)为常数⎧logbaO(n)a≠1T(n)=⎨⎩O((glogn)a=1d(n)=cn⎧O(n)ab例2.1芯片测试条件：有n片芯片，(好芯片至少比坏芯片多1片).问题：使用最少测试次数，从中挑出1片好芯片.对芯片A与B测试，结果分析如下：A报告B报告结论B是好的A是好的A,B都好或A,B都坏B是好的A是坏的至少一片是坏的B是坏的A是好的至少一片是坏的B是坏的A
13、是坏的至少一片是坏的算法思想：两两一组测试，淘汰后芯片进入下一轮.如果测试结果是情况1，那么A、B中留1片，丢1片；如果是后三种情况，则把A和B全部丢掉.7分治算法命题2.1当n是偶数时，在上述规则下，经过一轮淘汰，剩下的好芯片比坏芯片至少多1片.证设A与B都是好芯片有i组，A与B一好一坏有j组，A与B都坏有k组，淘汰后，好芯片数i，坏芯片数k2i+2j+2k=n2i+j>2k+j⇒i>k注：当n是奇数时，用其他芯片测试轮空芯片，如果轮空芯片是好的，算法结束；否则淘汰轮空芯片.每轮淘汰后，芯片数至少减半，时间复杂度是：⎧n⎪W(n)=W()+O(n)⎨2⇒W
14、(n)=O(n)⎪⎩W(3)=18伪码描述算法2.3Test(n)1．k←n2．whilek>3do3．将芯片分成⎣k/2⎦组//如有轮空芯片，特殊处理4．fori=1to⎣k/2⎦doif2片好then，则任取1片留下el2lse2片同时丢掉5．k←剩下的芯片数6．ifk=3then任取2片芯片测试if1if1好1坏then取没测的芯片else任取1片被测芯片7．ifk=2or1then2or1then任取1片9例2.2幂幂算乘计算问题：设a是给定实数，计算an,n为自然数传统算法:Θ(n)分治法an/2×an/2n为偶数an=a(n–1)/2×a(n–1
15、)/2×an为奇数W(n)=W(n/2)+Θ(1)⇒W(n)=Θ(logn).10计算Fibonacci数Fibonacci数11235813211,1,2,3,5,8,13,21,…满足F=F+Fnn-1n-2增加F=0，得到数列0,1,1,2,3,5,8,13,21,…0通常算法：从F,F,…,根据定义陆续相加，时间为Θ(n)01定理2.1设{F}为Fibonacci数构成的数列，那么nn⎡Fn+1Fn⎤⎡11⎤⎢⎥=⎢⎥⎣FnFn−1⎦⎣10⎦⎡11⎤算法：令矩阵M=⎢⎥，用分治法计算Mn⎣10⎦时间T(n)=Θ(logn).112.3改进分治算法的途
16、径2.3.1通过代数变换减少子问题个数例232.3位
