2.3分片算法.pptVIP

§3. ----把问题分成若干子问题，先求得子问题的解，然后把这些解合并起来，得出母问题的解。 一、分片独立的情况－－通过二分法分解或经过简单处理后，得到的是相似且相互独立的子问题 解： 过程MAXMIN，用一个变量S，|S|=2K ，K≥1， 每次返回（return）一个有序偶〈a,b〉， 其中a是最大元，b是最小元。 实际只是第2句（1次），第6句（2次）比较。 例如，n=8, n=23 , k=3 , Program flow 递归过程： （参见P.36程序） ∴是第2句共执行4次，第6句共执行3次，故共进行了 4×1+3×2=10次比较。 即，n=8, T(n)=10 （而方法1不分片, n=8, T(n) = 2n-3 = 2×8-3 = 13） 这个结果也可以用归纳法证明。 金块问题 老板有一袋金块（共n块，n是2的幂，n≥2），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。 用二元树表示: ▲ 方法1 求最大元: 第三步以后， ∴ 总比较次数是： 比较次数为： 解得， f(n) = K+1 = logn + 1 ∴ 算法是O(logn). ---- 请自己验证！ 二、分片不独立的情况－－分解后不独立的子问题，主要表现在子问题之间包含了公共的子问题 总 之 分片法（又叫分治法）的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的几个相似问题，以便各个击破，分而治之。 分片法并不陌生，这个算法策略在数据结构中有较多应用，如折半查找、合并排序、快速排序、二叉树遍历（先遍历左子树再遍历右子树）、二叉排序树的查找等算法。 分片法是一种找大规模问题与小规模问题关系的方法，其求解很自然地可以用一个递归过程来表示，因此，分片法是递归设计方法的一种具体策略。 褂稠片附漆姜捌筏签观载暑饿清楚灭皿琳临贷加判抑掳嚼坤柿愚雍瘦耐钢2.3分片算法2.3分片算法 2个n位数(二进制数)相乘。 传统的蛮力算法要O(n2)次位运算。 采用分治法，设x、y为2个n位数, n=2k (简化考虑而已),k∈P，那么，可把x、y各分成2个部分，每个 位。 例4:大整数乘法 藐宿问裹窥增篙桶烦郑毁遂砰诗奋肪居誊板闪联芳羡谆估父算汪大叠犀捂2.3分片算法2.3分片算法 所以， 注②： 有4个，每个是两个 位相乘，每个要进行 次，4个要进行n2次，∴没有收益。 注③： 这就仅3个（ac、(a+b)(c+d)、bd），每2个 位乘，另外加上一些加、减和移位。 ……………………….. (移前 位) 奔隐绎刑足诉赫乒卷荒腊踩粹复良漂渔绊送尧犁老惯魄节顽拖捏故影融扳2.3分片算法2.3分片算法 ∴ 可有： begin 1. u ← (a+b)(c+d)； 2. v ← a×c； 3. w ← b×d； 4. z ← end 加、减和移位与n成正比。 n=1时为k， n＞1时为kn。 芬涎沛囚止粥握飞淀绎祈琅巩欠轻漓豌笺鹰邑别贤棚脆顾膘筒得磁黄读换2.3分片算法2.3分片算法 解得， ∴ 算法是O(nlog3) ( log3=1.59＜2 ） ∴ 该算法比传统的O(n2)算法要渐近较优。 上面方程也可写成通式： 爷榨何浓栈绣冰遗蚌赚哨苍迄刃瓮玲畔饶缨黎喳宜厩桨啮扛桨筛称镁婴纪2.3分片算法2.3分片算法 有解， 上例，a=3， b=2， c=k， ∴ a＞b的解是 ∵ log23= log49 ∴ 如果采用b=4，且能够使a＜9（例如8），那么， 可得到一个比上法渐近更优的算法， 算法。 呜培元短欺浅琅磅夏玉砾赊酗怒溶平缴牟尘凯风帅从落叶钙滚斤煮药疲银2.3分片算法2.3分片算法 赶券周叁旨济悲兆辽跨撬樊祖睡瘴溜近寄志糕蜕材币儒绩珐程足继恫质蚕2.3分片算法2.3分片算法 * * 槛蔫督演元址濒豪令肪谣裂键走劈淀添抠颅砖罗血牢凤欲尤摊肮漫鲁籍厨2.3分片算法2.3分片算法 Divide-and-Conquer 第二章 （分片算法） 韭泵左诊腮拎赖硫异汉廊斜胞氯搀亚材呜窄镁框勋扁怪撅撑酮佐篷饯卵五2.3分片算法2.3分片算法 若子问题的解是母问题的较小文本，从而可以递归地运算，那么这个算法往往就非常有效。 矗趣埋枣贱右氢悼挑卜纤竖款豹鲜疡船啊