算法第2章分治的策略ppt课件

1、1 第2章 分治策略（Divide and Conquer）2.1 分治策略的基本思想分治策略的基本思想 2.1.1 两个熟悉的例子两个熟悉的例子 2.1.2 分治算法的一般性描述分治算法的一般性描述2.2 分治算法的分析技术分治算法的分析技术2.3 改进分治算法的途径改进分治算法的途径 2.3.1 通过代数变换减少子问题个数通过代数变换减少子问题个数 2.3.2 利用预处理减少递归内部的计算量利用预处理减少递归内部的计算量2.4 典型实例典型实例 2.4.1 快速排序算法快速排序算法 2.4.2 选择问题选择问题 2.4.3 n1次多项式在全体次多项式在全体2n次方根上的求值次方根上的求值2

2、2.1.1 两个熟悉的例子两个熟悉的例子二分检索二分检索算法算法2.1 BinarySearch(T, l, r, x) 2.1 BinarySearch(T, l, r, x) 输入：数组输入：数组T T，下标从，下标从 l l 到到 r r；数；数 x x输出：输出：j / j / 假如假如 x x 在在 T T 中，中，j j为下标；否则为下标；否则为为0 01. l1. l1; r1; rn n2. while l2. while l r do r do3. m3. m(l+r)/2(l+r)/2 4. if Tm=x then return m 4. if Tm=x then ret

3、urn m / x / x恰恰好等于中位元素好等于中位元素5. else if Tmm then r 5. else if Tmm then r m m1 16. else l6. else lm+1m+1return 0return 0二分归并排序二分归并排序 MergeSort MergeSort （见第（见第1 1章）章）时间复杂度分析时间复杂度分析二分检索最坏情况下时间复杂度二分检索最坏情况下时间复杂度W(n)满足满足二分归并排序最坏情况下时间复杂度二分归并排序最坏情况下时间复杂度W(n)满足满足 1)1(1)2()(WnWnW 0)1(1)2(2)(WnnWnW可以解出可以解出W(n

4、)=nlognn1. 可以解出可以解出W(n)=logn1. 42.1.2 分治算法的一般性描述分治算法的一般性描述分治算法分治算法 Divide-and-Conquer(P) 1. if |P| c then S(P). 2. divide P into P1, P2, , Pk. 3. for i = 1 to k 4. yi = Divide-and-Conquer(Pi) 5Return Merge(y1, y2, , yk) 算法时间复杂度的递推方程算法时间复杂度的递推方程一般原则：子问题均匀划分、递归处理一般原则：子问题均匀划分、递归处理 CcWnfPWPWPWnWk)()(|)(

5、|.|)(|)(|)(215分治策略的算法分析工具：递推方程分治策略的算法分析工具：递推方程两类递推方程两类递推方程求解方法求解方法第一类方程：迭代法、换元法、递归树、尝试法第一类方程：迭代法、换元法、递归树、尝试法第二类方程：迭代法、递归树、主定理第二类方程：迭代法、递归树、主定理)()()()()()(1ndbnafnfnginfanfkii 2.2 分治算法的分析技术分治算法的分析技术递推方程的解递推方程的解方程方程d(n)为常数为常数 d(n) = cn 1)(log1)()(loganOanOnTab banObannObanOnTab)()log()()(log)()/()(ndb

6、naTnT 7A 报告报告B 报告报告结论结论B是好的是好的A是好的是好的A,B 都好或都好或 A,B 都坏都坏B是好的是好的A是坏的是坏的至少一片是坏的至少一片是坏的B是坏的是坏的A是好的是好的至少一片是坏的至少一片是坏的B是坏的是坏的A是坏的是坏的至少一片是坏的至少一片是坏的条件：有条件：有n n 片芯片，片芯片，( (好芯片至少比坏芯片多好芯片至少比坏芯片多1 1片片). ). 问题：使用最少测试次数，从中挑出问题：使用最少测试次数，从中挑出1 1片好芯片片好芯片. . 对芯片对芯片A A与与B B测试，结果分析如下：测试，结果分析如下：例例2.1 芯片测试芯片测试算法思想：两两一组测试

7、，淘汰后芯片进入下一轮算法思想：两两一组测试，淘汰后芯片进入下一轮. 如果测试结果是情况如果测试结果是情况1，那么，那么A、B中留中留1片，丢片，丢1片；片；如果是后三种情况，则把如果是后三种情况，则把A和和B全部丢掉全部丢掉. 8分治算法分治算法命题命题2.1 当当n是偶数时，在上述规则下，经过一轮淘汰，是偶数时，在上述规则下，经过一轮淘汰，剩下的好芯片比坏芯片至少多剩下的好芯片比坏芯片至少多1片片. 证证 设设A与与B都是好芯片有都是好芯片有 i 组，组，A与与B一好一坏有一好一坏有 j 组，组，A与与B都坏有都坏有 k 组，淘汰后，好芯片数组，淘汰后，好芯片数 i，坏芯片数，坏芯片数 k

8、 2i + 2j + 2k = n 2i+j 2k+j i k注：当注：当n是奇数时，用其他芯片测试轮空芯片，如果轮空是奇数时，用其他芯片测试轮空芯片，如果轮空芯片是好的，算法结束；否则淘汰轮空芯片芯片是好的，算法结束；否则淘汰轮空芯片. 每轮淘汰后，芯片数至少减半，时间复杂度是：每轮淘汰后，芯片数至少减半，时间复杂度是： )()(31)(3)()2()(nOnWnnWnnOnWnW 9伪码描述伪码描述算法算法2.3 Test(n)1k n 2while k 3 do 3 将芯片分成将芯片分成 k/2 组组 / 如有轮空芯片，特殊处理如有轮空芯片，特殊处理4 for i =1 to k/2 d

9、o if 2片好，则任取片好，则任取1片留下片留下 else 2片同时丢掉片同时丢掉5 k 剩下的芯片数剩下的芯片数6if k =3 then 任取任取2片芯片测试片芯片测试 if 1好好1坏坏 then 取没测的芯片取没测的芯片 else 任取任取1片被测芯片片被测芯片7if k =2 or 1 then 任取任取1片片 10例例2.2 2.2 幂乘计算幂乘计算问题：设问题：设a是给定实数，计算是给定实数，计算 a n, n为自然数为自然数传统算法传统算法: Q(n)a n =a n/2 a n/2 n 为偶为偶数数a (n1)/2 a (n1)/2 a n 为奇为奇数数分治法分治法W(n)

10、 = W(n/2) + Q(1) W(n) = Q(log n) . 11计算计算 Fibonacci 数数增加增加F0=0F0=0，得到数列，得到数列 0,1, 1, 2, 3, 5, 8, 13, 21, 0,1, 1, 2, 3, 5, 8, 13, 21, 通常算法：从通常算法：从 F0, F1, , F0, F1, , 根据定义陆续相加，时间为根据定义陆续相加，时间为(n)(n)定理定理2.1 2.1 设设 Fn Fn为为 Fibonacci Fibonacci 数构成的数列，那么数构成的数列，那么 Fibonacci 数数 1, 1, 2, 3, 5, 8, 13, 21, 满足满

11、足 Fn=Fn-1+Fn-2 nnnnnFFFF 011111 算法：令矩阵算法：令矩阵 ，用分治法计算，用分治法计算 M n M n 时间时间 T(n)= Q (log n) . T(n)= Q (log n) . 0111M122.3 改进分治算法的途径改进分治算法的途径2.3.1 通过代数变换通过代数变换 减少子问题个数减少子问题个数例例2. 3 位乘问题位乘问题 设设X ,Y 是是 n 位二进制数，位二进制数， n = 2k, 求求 XY.一般分治法一般分治法 令令X A2n/2 +B, Y= C2n/2 +D. XY= AC 2n + (AD + BC) 2 n/2 + BD W(n

12、) = 4W(n/2) + cn，W(1) = 1 W(n) =O(n2)代数变换代数变换 AD + BC = (AB) (DC) + AC + BD W(n) = 3 W(n/2) + cn，W(1) = 1 W(n) =O(nlog3) =(n1.59) 13例例2.4 A,B 为两个为两个n 阶矩阵，阶矩阵，n =2k, 计算计算 C = AB.传统算法传统算法 W(n)= O(n3)分治法分治法 将矩阵分块，得将矩阵分块，得 其中其中递推方程递推方程 W(n) = 8 W(n/2) + cn2 W(1) = 1解解 W(n) = O(n3). 222112112221121122211

13、211CCCCBBBBAAAA2222122122212211212122121211122112111111BABACBABACBABACBABAC 矩阵乘法矩阵乘法14Strassen 矩阵乘法矩阵乘法14变换方法：变换方法： M1 = A11 ( B12B22 ) M2 = ( A11 + A12 ) B22M3 = ( A21 + A22 ) B11 M4 = A22 ( B21 B11)M5 = ( A11 + A22 ) ( B11 + B22 )M6 = (A12A22) ( B21 + B22 )M7 = (A11A21) ( B11 + B12 )C11 = M5 + M4M

14、2 + M6 C12 = M1 + M2C21 = M3 + M4C22 = M5+ M1M3M71)1()(18)(7)(222 WWnWnn)()()(8075. 27log2nOnOnW 时间复杂度：时间复杂度：15算法中的处理尽可能提到递归外面作为预处理算法中的处理尽可能提到递归外面作为预处理例例2.5 2.5 平面点对问题平面点对问题输入：集合输入：集合S S 中有中有n n 个点，个点，n 1n 1，输出：所有的点对之间的最小距离输出：所有的点对之间的最小距离. .通常算法：通常算法：C(n,2)C(n,2)个点对计算距离，比较最少需个点对计算距离，比较最少需O(n2)O(n2)时

15、间时间分治策略：子集分治策略：子集P P 中的点划分成两个子中的点划分成两个子 集集 PL PL和和 PRPR 2|2|PPPPRL2.3.2 利用预处理减少递归内部操作利用预处理减少递归内部操作16平面最邻近点对算法平面最邻近点对算法MinDistance(P,X,Y)输入：输入：n 个点的集合个点的集合P, X 和和Y 分别为横、纵坐标数组分别为横、纵坐标数组输出：最近的两个点及距离输出：最近的两个点及距离 1. 如果如果P 中点数小于等于中点数小于等于3，则直接计算其中的最小距离，则直接计算其中的最小距离 2. 排序排序X,Y 3做垂直线做垂直线 l 将将P划分为划分为PL和和PR，PL

16、的点在的点在 l 左边，左边，PR的的点点 在在 l 右边右边 4MinDidtance(PL,XL,YL); L = PL中的最小距离中的最小距离 5MinDistance(PR,XR,YR); R = PR中的最小距离中的最小距离 6 = min (L,R ) 7对于在对于在l 线左边距离线左边距离内每个点，内每个点， 检查右边是否有与之检查右边是否有与之 距离小于距离小于的点，如果存在则将的点，如果存在则将修改为新值修改为新值176/536/259/44/)3/2()2/(22222 d右边每个小方格至多右边每个小方格至多1 1个点，每个点至多比较对面的个点，每个点至多比较对面的6 6个

17、点，个点，间隔间隔的的2 2个点个点( (左右各左右各1 1个个) )其纵坐标位置相差不超过其纵坐标位置相差不超过1212，检查检查1 1个点是常数时间，个点是常数时间，O(n) O(n) 个点需要个点需要O(n)O(n)时间时间2 d跨边界的最邻近点跨边界的最邻近点l18 3)1()()log()2(2)( nOnTnnOnTnT由递归树估计由递归树估计T(n) = O(nlog2n)算法分析算法分析分析：步分析：步1 O(1) 1 O(1) 步步2 O(nlogn)2 O(nlogn) 步步3 O(1) 3 O(1) 步步4-5 2T(n/2)4-5 2T(n/2) 步步6 O(1)6 O

18、(1) 步步7 O(n)7 O(n)19预排序的处理方法预排序的处理方法 3)1()()()(2)()log()()(2 nOnTnOTnTnnOnTnWn 解得 T(n)=O(nlogn) W(n) = O(nlogn) 在每次调用时将已经排好的数组分成两个排序的子集，在每次调用时将已经排好的数组分成两个排序的子集， 每次调用这个过程的时间为每次调用这个过程的时间为O(n) O(n) W(n)W(n)总时间，总时间，T(n)T(n)算法递归过程，算法递归过程，O(nlogn)O(nlogn)预处理排序预处理排序20实例：递归中的拆分实例：递归中的拆分X-2(3)0.5(1)1(4)2(2)Y

19、-1(4)2(1)3(2)4(3)P1234X0.52-21Y234-1p1p2p3p4XL-2(3)0.5(1)XR1(4)2(2)YL2(1)4(3)YR-1(4)3(2)l21典型实例分析典型实例分析2.4.1 快速排序快速排序算法算法 Quicksort(A,p,r)输入：数组输入：数组Ap.r输出：排好序的数组输出：排好序的数组A 1. if p x 9. if i j 10. then A i A j 11. if i=j 1 then return j 12. else return j 划分过程划分过程23划分实例划分实例 27 99 0 8 13 64 86 16 7 10

20、88 25 90 i j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 24最坏情况最坏情况 )()1(21)(0)1(1)1()(2nnnnWWnnWnW 最好划分 )log()(0)1(1)(2)(2nnnTTnTnTn 均衡划分均衡划分 )log()(0)1()()()(10109nnnTTnTTnTnn 最坏情况下的时间复杂

21、度最坏情况下的时间复杂度25均衡划分均衡划分O(n)O(n)O(n)O(n)O(nlogn)110n100081n109nn1000729n100n1009n10081n1009n1 nk910log 26假设输入数组首元素排好序后的正确位置处在假设输入数组首元素排好序后的正确位置处在1,2,n 各种各种情况是等可能的，概率为情况是等可能的，概率为1/n. 利用差消法求得利用差消法求得 T(n)=O(nlogn)0)1()()(2)()()()(1)(1111 TnOkTnnTnOknTkTnnTnknk平均情况下时间复杂度平均情况下时间复杂度27 问题：从给定的集合 L 中选择第 i 小的元

22、素 不妨设 L 为 n 个不等的实数 i=1, 称为最小元素； i=n，称为最大元素； i=n-1，称为第二大元素； 位置处在中间的元素，称为中位元素 当n为奇数时，中位数只有1个，i=(n+1)/2； 当n为偶数时，中位数有2个，i=n/2, n/2+1. 也可以规 定其中的一个2.4.2 选择问题选择问题28算法算法 Findmax Findmax输入：输入：n n 个数的数组个数的数组 L L输出：输出：max, kmax, k 1. max 1. maxL1L1；k k1 1 2. for i 2. for i2 to n do2 to n do 3. if max Li 3. if

23、max 1 then goto 2 8max 最大数最大数 9Second max 的链表中的最大的链表中的最大锦标赛算法锦标赛算法32命题命题2.2 max在第一阶段的分组比较中总计进行了在第一阶段的分组比较中总计进行了logn次比较次比较. 证证 设本轮参与比较的有设本轮参与比较的有 t 个元素，经过分组淘汰后进入个元素，经过分组淘汰后进入下一轮的元素数至多是下一轮的元素数至多是 t/2 . 假设假设 k 轮淘汰后只剩下轮淘汰后只剩下一个元素一个元素 max，利用，利用 t/2 /2 = t/22的结果并对的结果并对 k 归纳，可得到归纳，可得到 n/2k=1. 假设假设 n=2d，那么有，那么有 k=dlogn=logn假设假设 2dnm*m*m*rr36复杂度估计复杂度估计 W(n)=O(n) 不妨设不妨设 n=5(2r+1), |A|=|D|=2r, 算法工作量算法工作量 行行2： O(n) 行行3： W(n/5) 行行4： O(n) 行行8-9： W(7r +2)用递归树做复杂度估计用递归树做复杂度估计)107()23107()2)2110(7()27(nWnWnWrW 2110215 nrn)(.10081109)107()5()(nOtntntntnnWnWnw tntntntntntntntntntn81.010049507507259 .010