算法第四章课件

1、4.1 一般方法4.2 二分检索4.3 找最大和最小元素4.4 归并分类4.5 快速分类4.6 选择问题4.7 斯特拉森矩阵乘法第四章 分治法4.1 一般方法分治法的思想: 将一个输入规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。问题(N个输入)子问题1子问题2子问题K子问题1子问题2子问题k相同类型合并解分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。步骤：分（devide）二分为主多分比二分更好吗？ 治（conquar）递归调用，当规

2、模足够小时直接处理 组（combine）分治法问题特征：问题规模小到一定的程度就非常容易解决所有问题的共性特征2) 问题可分解为若干个规模较小的同类问题递归策略 分3) 子问题的解可以合并为该问题的解若不具备，可用贪心或动态规划4) 子问题是相互独立的保证采用分治法效率高，否则更适合采用动态规划分治策略DANDC的抽象化控制procedure DANDC(p,q)global n, A(1:n); integer m, p, q; /1pqn/if SMALL(p,q) then return(G(p,q) else mDIVIDE(p,q) return(COMBINE( DANDC(p,m

3、), DANDC(m+1,q)endifend DANDC判断输入规模q-p+1是否足够小,可直接求解G是求解该规模问题的函数分割函数, pmq, 原问题被分为A(p:m)和A(m+1:q)两个子问题合并函数,将两个子问题的解合并为原问题的解原问题为A(1:n) , 最初调用函数应该是DANCE(1,n); DANDC(p,q)是计算A(p:q)子问题的解4.1 一般方法k分法的复杂性分析一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阈值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(

4、n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。 procedure BINSRCH(A, n, x, j) int low, high, mid, j, n; low1; highn; while （low=high） do mid(low+high)/2; /*取中间值*/ case xAmid: lowmid+1 /*

5、寻找后一半*/ else: jmid; return; /*检索成功, 结束*/ endcase repeat j0; /*检索失败*/end BINSRCH二分检索算法检索x=9, 9=A5, 一次比较就成功, 最好情况-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A9检索x=-15, -15A5, -15A5, 101A7, 101A8, 101= A9, 4次比较, 成功检索x=8, 8A2, 8A3, 8A4, 4次比较, 不成功检索二分检索实例:设在A(1:9)中顺序放了以下9个元素：用五个特性判断是否是一个算法根据算法的描述，满足五个特性，是算法

6、证明算法是否正确如果n=0，则不进入循环，j=0，算法终止否则就会进入循环与数组A中的元素进行比较如果x=Amid，则j=mid，检索成功，算法终止否则，若xA(mid)，则缩小到A(mid+1)和A(n)之间检索按上述方式缩小检索区总可以在有限步内使lowhigh如果出现这种情况，说明x不在A中，j=0，算法终止二分检索算法正确性证明：-15-6079235482101A1 A2 A3 A4 A5 A6 A7 A8 A93234132343334433344成功检索有n种情况，不成功检索有n+1种情况成功：不成功：不论检索是否成功，算法的执行过程都是x与一系列中间元素Amid的比较过程，我们

7、可以用一棵二元比较树来描述算法的执行过程二元比较树内结点表示一次元素的比较,存放一个mid值外结点表示不成功检索的一种情况592-61-1530754476238829101一条路径表示一个元素的比较序列4.2 二分检索Notes: E=I+2n 的证明1.在 n=1 时显然成立2.设 内节点为 n-1 时成立，3. 内节点为 n 时 把最远的内节点（i级）拿掉，替换为一个外节点E=E 2i +(i-1) = E i - 1 I=I (i-1) E=I+2n-2= E=E+i+1= I+2n-1+i = I (i-1) +2n-1+i=I+2n成功检索平均比较数 S(n) = I/n+1不成功

8、检索平均比较数 U(n) = E/(n+1)推导得：S(n)=(1+1/n)U (n)-1S(n)=(logn) 关于确切比较次数的讨论：BINSRCH的一次比较假设不合理，是为了降低分析复杂度的权宜之计，但对近似表示无影响实际上应该用（*）替代BINSRCH相应语句每次循环固定一次比较的BINSRCH1算法的提出对于成功检索：最好最坏平均BINSRCH 1 log(n)log(n)BINSRCH(*) 22 log(n)1.5 log(n)BINSRCH1log(n)+1log(n)+1 log(n)+1以比较为基础检索的时间下界思考: 对于已排序的n个元素, 检索某元素x是否出现, 是否存

9、在以比较为基础的检索算法, 在最坏情况下该算法的计算时间比二分检索算法的计算时间更低对于以比较为基础的检索算法的分析，采取构建二元比较树的方式。二元比较树-顺序检索有n个如下关系的元素:A(1)A(2)A(n),检索一给定元素X是否在A中出现X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功线性检索以比较为基础检索的时间下界定理4.3: 设A(1:n)含有n(n1)各不同的元素，排序为A(1)A(2)max then max Ai; if Aimax then max=Ai;else if Aimin then min=Ai;直接算法的时间复杂度在最好、最坏、平均情况下均为2(n-1

10、)改进后的计算时间:(元素升序)最好情况为(n-1)(元素降序)最坏情况为2(n-1)平均情况为3/2(n-1)改进采用分治策略求最大最小元素I=(n,A(1),A(n)划分为I1=( n/2 ,A(1),A( n/2 ) )I2=( n-n/2 ,A( n/2 +1 ),A(n) )结果的合并分治法求最大和最小元素procedure MAXMIN( i, j, fmax, fmin)int i, j; global n, A(1:n);case i= j: fmax fmin Ai i= j-1: if Ai24.3 找最大和最小元素可以证明: 任何一种以比较为基础的找最大和最小元素的算法，

11、其元素比较次数的下界为 3n/2 -2但是不代表该算法最优，理由如下：MAXMIN算法分析MAXMIN所需的存储空间比直接算法多4.3 找最大和最小元素给出n个元素，则MAXMIN算法有 logn +1级的递归，每次递归都需要保存i, j, fmax, fmin和返回地址5个值直接算法需要空间为: n+3, 用n个位置存放数组A，还有i, max, min三个变量需要存储元素A(i)和A(j)的比较与i和j的比较时间相差不大时，过程MAXMIN不可取。 设MAXMIN的频率计数为C(n)，n=2k , k为整数, 当n2时, 有: C(n)=5n/2-3 4.3 找最大和最小元素C(n)= 2

12、C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 = 2k-1C(2)+3*( 2k-2 +2k-3+22+21+20 ) =2k+3*(2k-1-1) =2k+3*2k-1-3 =5n/2-32 n=2C(n)=2C( n/2 )+ 3 n2直接算法的比较次数为2(n-1), 加上实现for循环 需要的比较次数, 则为3(n-1), 虽然3(n-1)略大于 5n/2-3, 但MAXMIN算法还有递归所带来的时间 开销, 这种情况下直接算法要快一些结论: 如果数组A的元素之间的比较远比整型变量的比较代价昂贵，分治算法略优于直接比较算法。4.3 找最大和最小元素一般

13、方法(插入法)For j2 to n do将A(j)放入已分类A(1:j-1)4.4 归并分类问题描述: 给定一个含有n个元素的集合， 把它们按一定的次序分类(如非降次序)procedure INSERTIONSORT(A, n)A0 -;for j 2 to n do item Aj; i j-1; while ( itemAi) do Ai+1 Ai; i i-1; Ai+1 item; end INSERTIONSORT插入分类算法描述数组元素的移动插入排好序的值可能执行0j次(j=2,3n)最好情况(n)最坏情况的计算时间：2+n=(n(n+1)/2)-1=(n2)用item保存当前元

14、素值4.4 归并分类4.4 归并分类A0A1A2A3A4A5-639413639449, A4=A3; 936, 不用移动11-, A1=343, A2=416, A4=A3;14, A3=A2;1-, A1=1注：加一个元素A0从元素A2开始比较分：平均分为2个子集合治：递归调用分类算法，将2个子集合分类组：将2个分类的子集合并为一个分类集合4.4 归并分类分治策略设计归并分类算法A1A2A3A4A563941A1A2A3639A4A541A1A263A393636914A16A23A44A51分治策略设计归并排序算法134694.4 归并分类递归调用，分别对分解出来的两个子问题排序合并两个

15、已排好的序列，得到原问题的解归并排序算法描述Procedure MERGESORT(low,high)int low, high, mid;if (lowmid) then for kj to high do BiAk;ii+1 else for kh to mid do BiAk;ii+1 for k low to high do Ak Bk;end MERGE处理两个已分类的序列剩余元素处理过程将已分类的集合复制到A数组4.4 归并分类A1A2A3A4A563941low=1; mid=1; high=2; h=1; i=1; j=2; while (hmid and jhigh) do

16、if A1 A2 then else B1=A2; j=j+1=3 i=i+1=2; B1B2B3B4B53636if (hmid) then else for k=1 to 1 do B2=A1; i=i+1=3; for k=1 to 2 do Ak=Bk; 4.4 归并分类low=1; mid=2; high=3; h=1; i=1; j=3; while (hmid and jhigh) do if A1 A3 then B1=A1; h=h+1=2 i=i+1=2; if A2 A3 then B2=A2; h=h+1=3 i=i+1=3; if (hmid) then for k=

17、3 to 3 do B3=A3; i=i+1=4 for k=1 to 3 do Ak=Bk;A1A2A3A4A536941B1B2B3B4B5363693694.4 归并分类low=4; mid=4; high=5; h=4; i=4; j=5; while (hmid and jhigh) do if A4 A5 then else B4=A5; j=j+1=6 i=i+1=5; for k=4 to 5 do Ak=Bk; if (hmid) then else for k=4 to 4 do B5=A4; i=i+1=6; A1A2A3A4A536941B1B2B3B4B5369141

18、44.4 归并分类low=1; mid=3; high=5; h=1; i=1; j=4; while (hmid and jhigh) do if A1 A4 then else B1=A4; j=j+1=5 i=i+1=2; if (hmid) then else for k=2 to 3 do B4=A2; i=i+1=5 for k=1 to 5 do Ak=Bk; B5=A3; i=i+1=6 if A2 A5 then else B3=A5; j=j+1=6 i=i+1=4; if A1 A5 then B2=A1; h=h+1=2 i=i+1=3; A1A2A3A4A536914

19、B1B2B3B4B53691413469134694.4 归并分类归并分类的计算时间T(n)=a n=1 , a是常数(a=0)2T(n/2)+cn n1 , c是常数当 n=2k时，可得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，有T(n)T(2k+1)则有T(n)=O(nlogn)归并2个子数组所需的元素比较次数在n/2到n-1之间4.4 归并分类归并分类算法的缺点缺点1: 当子集合的元素很少时，算法的很多时间消耗

20、 在了递归的处理上。改进: 当子集合的元素个数适当少时，采用在小规模 集合上能有效工作的插入分类算法克服上述缺点 带来的时间消耗。缺点2: 辅助数组B的使用增加了算法的空间，且每次 调用MERGE时，都得将B中的结果复制到A中，消耗了一部分时间。改进: 用一个链接数组LINK(1:n)代替B，LINK中的 元素为A中元素的指针，它指向下一个元素所在 的下标位置。4.4 归并分类关于LINK数组LINK(1:n)为一链接数组，取值范围为1, 2, , n。可看成是A元素的指针，在分类表中它指向下一个元素所在的下标位置，用0表示结束。实例: 下面是一个LINK集合，包含了两个已分类的 子集合。q和

21、r表示两个子集合的起始处:q=2,r=51234567803417086q=2的表为(2, 3, 4, 1) A2A3A4A1r=5的表为(5, 7, 8, 6) A5A7A8A6123456785010253015703555数组A:数组LINK:4.4 归并分类procedure MERGESORT1(low, high, p)global A(low:high), LINK(low:high)if (high-low+116 ) then call INSERTIONSORT(A, LINK, low, high, p);else mid(low+high)/2 ; call MERGE

22、SORT1(low, mid, q); call MERGESORT1(mid+1, high, r); call MERGE1(q, r, p); end MEGESORT1改进的归并分类算法当集合元素小于16时, 调用修改的插入分类算法归并分类递归调用合并两个子问题的解4.4 归并分类使用LINK数组的归并函数procedure MERGE1(q, r, p)global n, A(1:n), LINK(0:n); int i, j, k;i q; j r; k 0;while (i0 and j0) do if (AiAj) then LINKki;ki;iLINKi; else LIN

23、Kkj;kj;jLINKj;if (i=0) then LINKkj; else LINKki;p LINK0;end MERGE1当q和r非空时进行以下操作: 加入一个关键字的下标到LINK数组中处理剩下的关键字4.4 归并分类123456785010253015703555数组A:MSORT1(1, 8, p)if (8-1+15 ) then ISTSORT(A,LINK,1,8,p);else mid= (1+8)/2=4 ; MSORT1(1, 4, q); MSORT1(5, 8, r); MERGE1(q, r, p); end MSORT1 MSORT1(1, 4, p)if

24、(4-1+15 ) then ISTSORT(A,LINK,1,4,p);end MSORT1 返回p=2MSORT1(5, 8, p)if (8-5+15 ) then ISTSORT(A,LINK,5,8,p);end MSORT1 返回p=5MERGE1(2,5,p);012345678000000000数组LINK:034170864.4 归并分类012345678003417086数组LINK:MERGE1(2, 5, p)i=2; j=5; k=0;while (i0 and j0) do if (A2A5) then LINK0=2; k=2; i=3; 253471812345

25、6785010253015703555if (A3A5) else LINK2=5; k=5; j=7; if (A3A7) then LINK5=3; k=3; i=4; if (A4A7) then LINK3=4; k=4; i=1; if (A1A7) else LINK4=7; k=7; j=8; if (A1A8) then LINK7=1; k=1; i=0; if (i=0) then LINK1=8;p=LINK0=2;4.4 归并分类取消栈使用自然合并排序算法思想12345678501025301570355515023410253056157078355512341025

26、3050567815355570123456781015253035505570首先 对数组A进行一遍扫描, 找出所有已排好序的子数组段然后将相邻的子数组段两两合并, 重复这种合并过程, 直到整个数组排好序4.4 归并分类 任何以关键字比较为基础的分类算法，最坏情况下的时间下界都是(nlogn)，因此从数量级的角度上看, 归并算法是最坏情况下的最优算法。采用二元比较树证明之以比较为基础分类的时间下界4.4 归并分类对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)A(2)A(3)

27、A(1)A(3)表示一次比较一种可能的分类序列4.4 归并分类分类算法的二元比较树：内节点表示关键词的一次比较叶节点表示分类的一种可能结果2T(n)叶结点实际数 n!满二叉树外节点数 n!种可能的全排列2T(n)n! (n/2) n/2T(n) (n/2)log (n/2) (n/4)log nT(n) = (n log n)最坏情况下比较次数=比较树的最长路径=根到最远叶结点距离=树高T(n)4.4 归并分类4.5 快速分类快速分类的基本思想：选取数组A中的某个元素 t=As，然后将其他元素 重新排列，使A中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。这个重新整

28、理的过程成为划分，t称为划分元素。A1A2As-1AsAs+1An划分元素t经过一次划分后A1A2AjtAkAn每个元素都小于或等于t每个元素都大于或等于t4.5 快速分类快速分类实例A1A2A3A4A5A6A75392718 第1次划分，选t=A1，即t=5，划分后得到如下结果： A1A2A3A4A5A6A72315798 第2次划分，选t=A1，即t=2，划分后结果： A1A2A3A4A5A6A71235798 第3次划分，选t=A5，即t=7，划分后没有变化 第4次划分，选t=A6，即t=9，划分后结果： A1A2A3A4A5A6A71235798A1A2A3A4A5A6A7123578

29、94.5 快速分类procedure QUICKSORT(low,high)int low,high; global n, A(1:n)if lowhigh then jhigh+1 call PARTITION(low, j) call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) endifend QUICKSORT快速分类算法划分A(low,high), 函数执行完后, j返回划分元素的下标递归调用划分之后得到的两个集合4.5 快速分类PARTITION划分过程的实现procedure PARTITION(m, p)int m,p,i; gl

30、obal A(m:p-1)vAm; im;loop loop ii+1 until Aiv ; loop pp-1 until Apv ; if (ip) then call INTERCHANGE(Ai, Ap) else exitrepeatAmAp; Apv;end PARTITION交换Ai和Ap结束过程时, 参数p中的值为划分元素所在位置的下标, 该值将带回, 用于后面的QUICKSORT过程i从左向右移，直到Ai t p从右向左移，直到Apt首先调用QUICKSORT(1,7) /low=1,high=7if 17 then j=8; call PARTITION(1, 8); c

31、all QUICKSORT(low, j-1) call QUICKSORT(j+1, high) end QUICKSORT4.5 快速分类快速分类实例分析过程等PARTITION(1, 8)调用结束后,返回参数j的值,才能执行递归调用PARTITION(m, p) /m=1, p=8t=Am=5; i=m=1;loop(第1次) loop i+ until Ait ; i=3 loop p- until Apt ; p=6 if (i0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋

32、盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 2k-12k-1 2k2k用到的骨牌数为（ 4k -1）/3tr棋盘左上角方格的行号,tc棋盘左上角方格的列号dr特殊方格所在的行号,tc特殊方格所在的列号void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s