计算机算法设计与分析：4第四章分治法

1、第四章分治法24.1 一般方法4.2 二分检索4.3 找最大和最小元素(略)4.4 归并分类4.5 快速分类(略)4.6 选择问题(略)4.7 斯特拉森矩阵乘法主要内容34.1 一般方法分治法适用的问题分治法的求解思想分治策略DANDC的抽象化控制分治策略DANDC的计算时间4问题(n个输入)n取值相当大，直接求解往往非常困难，甚至无法求出。子问题1子问题2子问题k解1解2解k整个问题的解将n个输入分解成k个不同子集，得到k个不同的可独立求解的子问题。在求出子问题的解之后，能找到适当的方法把它们合并成整个问题的解。分治法适用的问题5分治法的求解思想思想：将整个问题分成若干个小问题后分而治之。通

2、常，由分治法所得到的子问题与原问题具有相同的类型。可以反复使用分治策略，直到可以直接求解子问题为止。适合采用递归过程来表示。分（divide）治（conquer）合（combine）6子问题的个数K显然有K1, K越大越好么?蚯蚓的故事蚯蚓一家这天很无聊，小蚯蚓想了想，把自己切成两段，打羽毛球去了。蚯蚓妈妈觉得这方法法不错，就把自己切成四段，打麻将去了。没过一会，蚯蚓爸爸就把自己切成了肉末。蚯蚓妈妈哭着说：你怎么那么傻，切得那么碎会死的。蚯蚓爸爸弱弱地说：突然想踢足球 7分治策略DANDC的抽象化控制procedure DANDC(p,q)global n, A(1 n); integer m

3、, p, q; /1pqn/if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) return(COMBINE (DANDC(p,m), DANDC(m1,q)endifend DANDC判断输入规模qp1是否足够小,可直接求解G是直接求解该规模问题的函数分割函数, pmq, 原问题被分为A(p m)和A(m1 q)两个子问题合并函数,将两个子问题的解合并为原问题的解原问题为A(1n) , 最初调用函数应该是DANDC(1, n).8分治策略DANDC的计算时间 假设所分成的两个子问题的输入规模大致相等，则分治策略DANDC的计算时间可表示为：

4、T(n)是输入规模为n的分治策略的计算时间g(n)是对足够小的输入规模能直接计算出答案的时间f(n)是COMBINE函数合成原问题解的计算时间g(n)n足够小2T(n/2)f(n)否则T(n)=94.2 二分检索二分检索问题描述二分检索求解原理二分检索算法二分检索实例二分检索算法正确性证明二分检索算法所需的空间和时间二元比较树算法BINSRCH的计算时间以比较为基础检索的时间下界10二分检索问题描述已知一个按非降序排列的元素表a1, a2, , an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并将此下标赋给变量j，否则，将j置成0。11二分检索求解原理将检索问题表示为

5、：I(n, a1, , an, x)， 选取一个下标k，可得到三个子问题：I1 (k1, a1, , ak1, x)I2 (1, ak, x)I3 (nk, ak1, , an, x)二分检索通常对所求解的问题（或子问题）选择中间元素的下标，k (n1)/212procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid (lowhigh)/2 /*取中间值*/ case :xA(mid): highmid1 /*在前一半寻找*/ :xA(mid): lowmid1 /*

6、在后一半寻找*/ : else: jmid; return; /*检索成功, 结束*/ endcase repeat j0 /*检索失败*/end BINSRCH二分检索算法13检索x9, 9A(5), 一次比较, 成功, 最好情况156079235482101A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9)检索x15, 15A(5), 15A(2), 15A(1), 3次比较, 成功检索x101, 101A(9), 4次比较, 成功检索x8, 8A(5), 8A(2), 8A(3), 8A(4), 4次比较, 不成功检索二分检索实例设在A(1:9)中顺

7、序放了以下9个元素：14二分检索算法正确性证明程序的正确性证明至今还是一个尚未解决的课题。这里仅给出BINSRCH的非形式证明。如果n0，则不进入循环，j0，算法终止。否则就会进入循环与数组A中的元素进行比较。成功情况：若xAmid，则jmid，检索成功，算法终止。不成功情况：按下述方式缩小检索区总可以在有限步内使lowhigh，说明x不在A中，j0，算法终止。若xA(mid)，则缩小到A(low)和A(mid1)之间检索。若xA(mid)，则缩小到A(mid1)和A(n)之间检索。15二分检索算法所需的空间和时间所需空间: 用n个位置存放数组A，还有low, high, mid, x, j五

8、个变量需要存储，共需空间 n5。所需时间： 需要分别考虑以下几种情况：成功检索的最好情况、平均情况、最坏情况不成功检索的最好情况、平均情况、最坏情况16-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A93334433344成功比较次数：失败比较次数：成功检索有n种情况，不成 功检索有n1种情况。集中考虑x和A中元素比较。可以用一棵二元比较树来描 述算法的执行过程。122333344最好最坏平均成功1425/9失败3434/1017二元比较树内结点表示一次元素的比较,存放一个mid值外结点表示不成功检索的一种情况592-61-15307544762388291

9、01一条路径表示一个元素的比较序列算法执行过程实质上就是x与一系列中间元素A(mid)的比较过程。18算法BINSRCH的计算时间定理4.2：若n在区域2k1, 2k)中，则对于一次成功的检索，二分检索算法至多作k次比较，而对于一次不成功的检索，或者作k1次比较或者作k次比较。证明：P75(logn)(logn)(logn)(logn)(logn)(1)不成功的检索成功的检索最坏情况平均情况最好情况计算时间19求成功检索的平均比较数内部路径长度I：由根到所有内部节点的距离之和；外部路径长度E：由根到所有外部节点的距离之和；容易证明EI2n；S(n)是成功比较的平均比较次数，S(n)In1;U(

10、n)是不成功比较的平均比较次数，U(n)E(n1);S(n)(11/n)U(n)1(U(n)(logn)思路：利用外部节点与内部节点到根的距离和之间的一种简单关系，由不成功检索的平均数求出成功检索的平均比较数。20算法BINSRCH的变型将BINSRCH的case语句用if语句来替换。procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid(lowhigh)2 case :xA(mid): highmid1 :xA(mid): lowmid1 : else: jmid

11、; return; endcase repeat j0 end BINSRCHif xA(mid) then highmid-1 else if xA(mid) then lowmid1 else jmid; return; endifendif 最坏情况下，x总是比较两次。21将BINSRCH的case语句用if语句来替换。procedure BINSRCH1(A, n, x, j) integer low, high, mid, j, n; low1; highn1 /high总比可能的取值大1 while lowhigh1 do mid(lowhigh)2 if xA(mid) /在循环

12、中只比较一次 then highmid else lowmid /xA(mid) endif repeat if xA(low) then jlow /x出现 else j0 /x不出现 end BINSRCH1最好、最坏和平均情况时间对于成功和不成功的检索都是(logn) 。算法BINSRCH的变型procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn while lowhigh do mid(lowhigh)2 case :xA(mid): highmid1 :xA(mid): lowmid1 : el

13、se: jmid; return; endcase repeat j0 end BINSRCH22以比较为基础检索的时间下界思考：对于已排序的n个元素，检索某元素x是否出现时，是否存在以比较为基础的检索算法，在最坏情况下该算法的计算时间比二分检索算法的计算时间更低。对于以比较为基础的检索算法的分析，采取构建二元比较树的方式。只进行元素间的比较而不实施其他运算。23二元比较树-顺序检索n个元素存在如下关系：A(1)A(2)A(n)，检索某一给定元素x是否在A中出现x:A(1)x:A(2)x:A(n)不成功不成功不成功不成功线性检索24二元比较树-二分检索x:A(n1)2)x:A(3(n1)4)x

14、:A(n1)4)x:A(n)x:A(n1)21)x:A(n1)21)x:A(1)不成功不成功不成功不成功不成功不成功不成功不成功25以比较为基础检索的时间下界定理4.3: 设A(1:n)含有n(n1)个不同的元素，排序为A(1)A(2)A(n)；又设用以比较为基础去判断是否xA(1:n)的任何算法在最坏情况下所需的最小比较次数是FIND(n)，那么FIND(n)log(n1) .证明P77结论：二分检索是解决检索问题的最优的最坏情况算法。定理表明: 任何一种以比较为基础的算法，其最坏情况下的计算时间都不可能低于O(logn)，也就是不可能存在其最坏情况下计算时间比二分检索算法的计算时间数量级还

15、低的算法。26思考题证明EI2n。证明BINSRCH1的最好、最坏和平均情况时间对于成功和不成功的检索都是(logn)。三分（多分）检索会得到更优的结果吗？274.3 找最大和最小元素问题描述：在含有n个不同元素的集合中同时找出 它的最大和最小元素procedure STRAITMAXMIN(A, n, max, min)int i, n;maxmin A1;for i 2 to n do if Aimax then maxAi;endif; if Aimin then minAi;endif; end STRAITMAXMIN直接算法：依次比较n1个元素，同时记录下最大、最小的元素if Ai

16、max then maxAi;else if Aimin then minAi;endif直接算法的时间复杂度在最好、最坏、平均情况下均为2(n1)改进后的计算时间:(元素升序)最好情况为(n1)(元素降序)最坏情况为2(n1)平均情况为32(n1)改进28采用分治策略求最大最小元素I(n,A(1),A(n)划分为I1=(n2 ,A(1),A( n 2 ) )I2=( n n2 ,A(n2 +1 ),A(n) )结果的合并29procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case ij: fmaxfminAi i j

17、1: if AiAj then fmaxAj; fminAi; else fmaxAi; fminAj; else: mid(ij)2; call MAXMIN( i, mid, gmax, gmin) call MAXMIN(mid1, j, hmax, hmin) fmax max(gmax, hmax); fmin min(gmin, hmin); endcaseend MAXMIN分治法求最大和最小元素只有一个或两个元素时递归调用部分两个子问题的答案进行合并4.3 找最大和最小元素30A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素2213-5-815601731471,9

18、,1,3,4,5,3,3,1,2,1,5,6,9,8,9,6,7, 22,13 -5,-5 22,-515,-8 22,-8 60,-860,1760,17 47,31实例: A(1:n)，n9，元素具体如下表所示：4.3 找最大和最小元素31过程MAXMIN的时间复杂度MAXMIN的元素比较次数当n2k (k是某个正整数)时，有T(n)3n22T(n)= 2T(n/2)2 = 2(2T(n/4)2)2 = 4T(n/4)42 = 2k1T(2)( 2k1 2k2222 ) =2k12k2 =3n/22与直接算法的比较次数2(n1)相比，比较次数减少了25 %。0 n11 n2T(n)T( n

19、2 ) T(n2 )2 n24.3 找最大和最小元素32可以证明：任何一种以比较为基础的找最大和最小元素的算法，其元素比较次数的下界为 3n2 2但是不代表该算法最优，理由如下：MAXMIN算法分析MAXMIN所需的存储空间比直接算法多4.3 找最大和最小元素给出n个元素，则MAXMIN算法有 logn 1级的递归，每次递归都需要保存i、j、fmax、fmin和返回地址5个值。直接算法需要空间为：n3，用n个位置存放数组A，还有i、max、min三个变量需要存储33元素A(i)和A(j)的比较与i和j的比较时间相差不大时，过程MAXMIN不可取。 设MAXMIN的频率计数为C(n)，n2k ,

20、 k为整数, 当n2时, 有: C(n)5n23 4.3 找最大和最小元素C(n) 2C(n2)3 2(2C(n4)3)3 4C(n4)63 2k1C(2)3( 2k22k3222120 ) 2k3(2k11) 2k32k13 5n232 n2C(n)=2C( n2 )3 n234直接算法的比较次数为2(n1)，加上实现for循环需要的比较次数，则为3(n1)，虽然3(n1)略大于 5n23，但MAXMIN算法还有递归所带来的时间开 销， 这种情况下直接算法要快一些。结论：如果数组A的元素之间的比较远比整型变量的比较代价昂贵，则分治法产生效率较高的算法；反之则得到一个效率较低的程序。4.3 找

21、最大和最小元素354.4 归并分类问题描述及一般方法思想(直接插入法)直接插入算法描述及实例归并分类算法思想、描述及实例合并算法思想、描述及实例归并分类算法的计算时间归并分类算法的缺点及改进方法以比较为基础分类的时间下界36一般方法(直接插入法)for j2 to n do将A(j)放入已分类集合A(1:j1)repeat问题描述及一般方法思想问题描述：给定一个含有n个元素的集合，把它们按一定的次序分类(如非降次序)最坏情况下，为了插入A(j)，有可能移动A(1:j1)中的所有元素。37procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item

22、 A(j); i j1; while ( itemA(i) do A(i1)A(i); ii1; repeat A(i1) item;repeat end INSERTIONSORT数组元素的比较和移动将本次考虑的元素插入相应位置可能执行0j次(j2,3n)最好情况 (n)最坏情况的计算时间：2n(n(n1)/2)1(n2)用item保存当前元素值算法4.7 插入分类算法描述38A0A1A2A3A4A5639413639449, A4A3; 936, A2A1; 6496, 不用移动119, A5A4; 964313, A1346, A3A2;43, A2416, A4A3;14, A3A2;

23、13, A2A1;1, A11注：加一个元素A0从元素A2开始比较插入分类的一个实例procedure INSERTIONSORT(A, n)A(0) for j 2 to n do item A(j); i j1; while ( itemA(i) do A(i1)A(i); ii1; repeat A(i1) item;repeat end INSERTIONSORT39可能执行0j次(j2,3n)最好情况 (n)最坏情况的计算时间：2n=(n(n1)/2)1(n2)算法4.7 插入分类算法描述有没有其他算法？它的最坏情况的计算时间要好于插入分类算法。40分治策略设计归并分类算法分：将A(

24、1),A(n)平均分为2个子集合： A(1),A(n2 )和A(n21),A(n)治：递归调用分类算法，将2个子集合分类合：将2个分类的子集合并为一个分类集合41递归调用，分别对分解出来的两个子问题排序合并两个已排好的序列，得到原问题的解Procedure MERGESORT(low, high)int low, high, mid;if (lowhigh) then mid (lowhigh)2 call MERGESORT(low, mid) call MERGESORT(mid1,high) call MERGE(low, mid, high) end MERGESORT算法4.8归并分

25、类算法描述42归并分类实例A1A2A3A4A563941A1A2A3639A4A541A1A263A393636914A16A23A44A5113469431,54,51,35,54,43,31,21,12,2表示一次调用时的low和high的值只含单个元素的子集合1，1，24，4，51，2，31，3，5表示MERGE调用时low, mid, high 的值MERGESORT(low, high)MERGE(low,mid,high)44合并函数MERGE算法思想 A(low) A(mid)A(mid1) A(high) B(low) B(high)jhi 如果h mid 且 j high，那

26、么B(i) min(A(h), A(j)(2) 如果hmid 且 j high，那么B(i) A(j)(3) 如果hmid 且 j high，那么B(i) A(h)45procedure MERGE(low, mid, high)int h,i,j, k, low, mid, high; global A(low : high); local B(low : high);hlow; ilow; jmid1;while (hmid and jhigh) do if (A(h) A(j) then B(i) A(h); hh1; else B(i) A(j); jj1; ；endif ii1;re

27、peat if (hmid) then for kj to high do B(i)A(k);ii1 else for kh to mid do B(i)A(k);ii1 for k low to high do A(k) B(k);end MERGE处理两个已分类的序列剩余元素处理过程将已分类的集合复制到A数组算法4.9MERGE算法描述46一个合并的例子A1A2A3A4A563941B1B2B3B4B53636hjihjii(1) low1，mid1，high2A1A2A3A4A536941B1B2B3B4B536369369(2) low1，mid2，high3hji1312323333

28、4447hji454(3) low4，mid4，high5465566A1A2A3A4A536941B1B2B3B4B53694141A1A2A3A4A536914B1B2B3B4B5369141346913469(4) low1，mid3，high5hji14115225326436546648归并分类的计算时间T(n)a n1 , a是常数2T(n2)cn n1 , c是常数当 n2k时，可得T(n) 2(2T(n/4)+cn/2)+cn 22T(n/4)+2cn 22(2T(n/8)+cn/4)+2cn 23T(n/8)+3cn 2kT(1)+kcn an+cnlogn如果2kn2k+1

29、，有T(n)T(2k1)则有T(n)O(nlogn)归并2个子数组所需的元素比较次数在n/2到n1之间49时间: 当子集合的元素很少时，算法的很多时间消耗在 递归的处理上。改进: 当子集合的元素个数适当少时，采用在小规模 集合上能有效工作的插入分类算法进行排序，而不是继续划分，以此克服上述缺点带来的时间消耗。空间: 辅助数组B的使用增加了算法的空间，且每次 调用MERGE时，都需要将B中的结果复制回A 中，消耗了一部分时间。改进: 用一个链接数组LINK(1:n)代替B，LINK中的 元素为A中元素的下标，它指示下一个元素所在 的下标位置。归并分类算法的缺点50 LINK(1:n)为一链接数组

30、，取值范围为1, 2, , n。可看成是A元素的指针，在分类表中它指向下一个元素所在的下标位置，用0表示结束。(1)(2)(3)(4)(5)(6)(7)(8)34018706q2的表为(2, 4, 1, 3) A(2)A(4) A(1)A(3)r5的表为(5, 8 , 6, 7) A(5)A(8)A(6)A(7)(1)(2)(3)(4)(5)(6)(7)(8)4332693523588946数组A:数组LINK:关于LINK数组 实例：下面是一个LINK集合，包含了两个已分类的子集合。q和r表示两个子集合的起始处：q2，r5qr51procedure MERGESORT1(low, high,

31、 p)global A(low:high), LINK(low:high)if (highlow116 ) then call INSERTIONSORT(A, LINK, low, high, p);else mid (lowhigh)2 ; call MERGESORT1(low, mid, q); call MERGESORT1(mid1, high, r); call MERGE1(q, r, p);endif end MEGESORT1当集合元素小于16时, 调用修改的插入分类算法归并分类递归调用合并两个子问题的解改进的归并分类算法52procedure MERGE1(q, r, p

32、)global n, A(1:n), LINK(0:n); int i, j, k;i q; j r; k 0;while (i0 and j0) do if (A(i)A(j) then LINK(k)i;ki;iLINK(i); else LINK(k)j;kj;jLINK(j);if (i0) then LINK(k)j; else LINK(k)i;pLINK(0);end MERGE1当q和r非空时进行以下操作: 加入一个关键字的下标到LINK数组中处理剩下的关键字使用LINK数组的归并函数53(1)(2)(3)(4)(5)(6)(7)(8)5010253015703555数组A:M

33、SORT1(1, 8, p)if (8115 ) then ISTSORT(A,LINK,1,8,p);else mid (18)24 ; MSORT1(1, 4, q); MSORT1(5, 8, r); MERGE1(q, r, p);end MSORT1 MSORT1(1, 4, q)if (4115 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回q2MSORT1(5, 8, r)if (8515 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回r5MERGE1(2,5,p);(0)(1)(2)(3)(4)(5)(

34、6)(7)(8)000000000数组LINK:034170862554012345678003417086数组LINK:MERGE1(2, 5, p)i2; j5; k0;while (i0 and j0) do if (A2A5) then LINK02; k2; i3; 2534718123456785010253015703555if (A3A5) else LINK25; k5; j7; if (A3A7) then LINK53; k3; i4; if (A4A7) then LINK34; k4; i1; if (A1A7) else LINK47; k7; j8; if (A1

35、A8) then LINK71; k1; i0; if (i0) then LINK18;pLINK02;数组A:2534718655思考题改进的归并分类算法的计算时间是多少？归并过程可以采用自底向上的设计方式来取消对栈空间的需要，试给出算法描述。56 任何以关键字比较为基础的分类算法，最坏情况下的时间下界都是(nlogn)，因此从数量级的角度上看, 归并分类是最坏情况下的最优算法。 采用二元比较树证明以比较为基础分类的时间下界57对3个关键字分类的二元比较树1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)A(2)A(2)A(3)A(1)A(3

36、)A(2)A(3)A(1)A(3)表示一次比较一种可能的分类序列假设参加分类的n个关键字A(1), , A(n)各不相同。那么任意两个关键字A(i)和A(j)的比较必然导致A(i)A(j)或者A(i)A(j)。58分析最坏情况下比较次数 比较树的最长路径 根到最远叶结点距离 树高T(n)从根到外节点的每一条路径分别与一种唯一的排列相对应。n个关键字有n！种排列。 比较树必定至少有n！ 个外节点。2T(n)n!2T(n)n! n(n1)(n2)(n/2) (n/2)n/2T(n)(n2)log(n2)(n4)lognT(n) (n log n)n4时，有n2 n1/2任何以关键字比较为基础的分类

37、算法，最坏情况下的时间下界都是(nlogn)。594.5 快速分类快速分类的基本思想：选取数组A中的某个元素 tAs，然后将其他元素 重新排列，使A中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。这个重新整理的过程称为划分，t称为划分元素。A1A2As1AsAs1An划分元素t经过一次划分后A1A2AjtAkAn每个元素都小于或等于t每个元素都大于或等于t60A1A2A3A4A5A6A75392718 第1次划分，选tA1，即t5，划分后得到如下结果： A1A2A3A4A5A6A72315798 第2次划分，选tA1，即t2，划分后结果： A1A2A3A4A5A6A

38、71235798 第3次划分，选tA5，即t7，划分后没有变化 第4次划分，选tA6，即t9，划分后结果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A71235789快速分类实例61procedure QUICKSORT(low,high)int low,high; global n, A(1:n)if lowhigh then jhigh1 call PARTITION(low, j) call QUICKSORT(low, j1) call QUICKSORT(j1, high) endifend QUICKSORT快速分类算法划分A(low, high), 函数

39、执行完后, j返回划分元素的下标递归调用划分之后得到的两个集合62procedure PARTITION(m, p)int m,p,i; global A(m:p1)vAm; im;loop loop ii1 until Aiv ; loop pp1 until Apv ; if (ip) then call INTERCHANGE(Ai, Ap) else exitrepeatAmAp; Apv;end PARTITIONPARTITION划分过程的实现交换Ai和Ap结束过程时, 参数p中的值为划分元素所在位置的下标, 该值将带回, 用于后面的QUICKSORT过程i从左向右移，直到Ai t

40、 p从右向左移，直到Apt63首先调用QUICKSORT(1,7) /low1, high7if 17 then j8; call PARTITION(1, 8); call QUICKSORT(low, j 1) call QUICKSORT(j+1, high) end QUICKSORT快速分类实例分析过程(I)等PARTITION(1, 8)调用结束后,返回参数j的值，才能执行递归调用PARTITION(m, p) /m1, p8tAm5; im1;loop(第1次) loop i until Ait ; i3 loop p until Apt ; p6 if (ip) then Ai

41、 Ap; A1A2A3A4A5A6A75392718A1A2A3A4A5A6A7531279864AmAp; 即A1A42Apt; 即A45end / p4的值带回loop(第2次,i3, p6) loop i until Ait ; i5 loop p until Apt ; p4 if (ip) 执行else exit loop1 A1A2A3A4A5A6A75312798A1A2A3A4A5A6A72315798递归调用QUICKSORT(low, j1) 即QUICKSORT(1, 3)递归调用QUICKSORT(j1,high) 即QUICKSORT(5, 7)快速分类实例分析过程(II)65快速分类算法的分析 I ：时间复杂性假设前提互不相同；随机选取划分元素划分单元随机选取的改进快速分类的性能取决于划分的对称性！随机选取更合理，因为最好能找到中间元素最坏情况下