计算机算法复习第2章

《计算机算法复习第2章》由会员分享，可在线阅读，更多相关《计算机算法复习第2章（52页珍藏版）》请在金锄头文库上搜索。

1、第二章 分治法,主要内容 分治法的思想 分治法的算法设计模式 分治法的举例（算法及时间复杂度） 二分检索、找最大最小值、归并分类、快速分类、选择问题、矩阵乘法 分治算法的时间复杂度求解 重点难点 分治法的抽象控制策略：如何把分治的思想应用到实际应用中去。,2.1 方法概述,一、基本思想 1、设计思想：将整个问题分成若干个小问题后,分而治之。 2、适用条件： 问题规模很大； 可以分成若干个与原问题性质相同的子问题，并可以分别求解。 子问题的解通过整合可以得到原问题的解。 3、设计方法：使用递归策略。,4、 设计步骤 (1)分解：将原问题分解为若干个相互独立、与原问题形式相同的子问题； (2)求解

2、：若子问题容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决； (3)合并：将已求解的各个子问题的解，逐步合并以得到原问题的解。,问题(N个输入),（1）分治 （2）求解 （3）合并,二、分治法的算法设计模式 Divide-and-Conquer(n) /n为问题规模 1 if n = n0 /n0 为可解子问题的规模 2 then 3 4 解子问题 5 return( 子问题的解 ) 6 4 for i 1 to k /分解为k个子问题 5 do yi Divide-and-Conquer(|Pi|)/递归解决Pi 6 T MERGE(y1,y2,.,yk) /合并子问题 7 r

3、eturn T,递归过程,注意：分治法可以用递归实现，也可以用循环实现。,其中：其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。算法MERGE(y1,y2,.,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,.,Pk的相应的解y1,y2,.,yk合并为P的解。 应用分治法时子问题规模的选择 在用分治法设计算法时，最好使子问题的规模大致相同。 平衡(balancing)子问题的思想是使子问题规模大致相等。,假设每次将原问题分成a个子问题，每个问题的大小是原问题规模的1/b; 分解该子问题的时间复杂度为D(n)； 合并该

4、子问题的时间复杂度为C(n)。,时间复杂性分析：,二分法的时间复杂度 假设每次将原问题分成2个子问题，每个问题的大小是原问题规模的1/2; 分解该子问题的时间复杂度为 (1)； 合并该子问题的时间复杂度为 C(n)。 g(n) n足够小 T(n)= 2T(n/2)+ C(n) 否则,2.2 二 分 检 索,一、问题描述 已知一个按非降次序排列的元素表a1,a2,an,要求判定某给定元素x是否在该表中出现。若是，则找出x在表中的位置，并将此下标值赋给变量j；若非，则将j置成0。,定义问题的形式描述：I=(n, a1, a2, ,an,x) 问题分解：选取下标k，将I分解为3个子问题： I1=(k

5、-1, a1, a2, ,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, ak+2, ,an,x) 求解过程 若ak=x，则有解k，对I1、I3不用再求解； 若xak，则只在I3中求解，对I1不用求解； 合并过程：无需合并 如果对所求解的问题（或子问题）所选的下标k都是其元素的中间元素下标（例如，对于I，k=(n+1)/2）,则所产生的算法就是通常所说的二分检索.,三、二分检索算法 算法2.3 二分检索 /给定一个按非降次序排列的元素数组A(1:n),n1,判 断x是否出现。若是，置j，使得x=A(j),若非，j=0/ BINSEARCH(A,n,x) 1 low 1

6、2 high n,3 while lowhigh，数组A中没有找到x，返回j0 4 do 5 6 /取处于low和high之间的中间值 7 if x=Amid/找到值为x的元素，mid即为其下标，返回mid 8 then return mid 9 else if x Amid/如果x Amid，则x可能位于low与mid之间， 10 /否则x可能位于mid与high之间 11 then high mid - 1 12 else low mid + 1 13 14 retrun 0,非递归形式,四、算法的证明 证明:binarySearch(A,n,x,j)能正确运行 确定性和能行性 终止性 算

7、法初始部分置low1, highn 若n=0，不进入循环，j置0，算法终止 否则，进入循环，计算mid, x=A(mid)，j 置为mid，算法终止； xA(mid)，lowmid+1，搜索范围实际缩小为mid+1, high 正确性 按照上述规则，在有限步内，或找到某个mid，有A(mid) = x；或变得lowhigh，在a中没有找到任何元素等于x，算法终止。,假定在A9中顺序存放着以下9个元素：-15，-6，0，7，9，23，54，82，101。要求检索下列x的值：101，-14和82是否在A中出现。,从算法中可以看到,所有的运算基本上都是进行比较和数据传送，前两条是赋值语句,频率计数均

8、为1。在while循环中，我们集中考虑循环的次数，而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级，找到这九个元素中的每一个所需的元素循环的次数如下：,五、时间复杂性分析 (1) (log n) (log n) (log n) (log n) (log n),分析：对于A中的n个数，如果x在A中出现，则是成功检索，所以成功检索共有n种情况，而不成功的检索，x将取n+1个区间中的不同值，因此在计算出x在这2n+1种情况下的执行时间后，就可以求出其在各种情况下的时间复杂性了。,例子：A： （1） （2） （3） （4） （5） （6） （7） （8 ） （9 ） 元素： -15

9、 -6 0 7 9 23 54 82 101 比较次数： 3 2 3 4 1 3 2 3 4,成功检索的比较次数是25/92.77。 不成功检索有10种，如果xA（1）,A(1)xA(2), A(2)xA(3), A(5)xA(6),A(6)xA(7),A(7)xA(8) ，为了判断x不在A中，算法要比较3次，而其余的情况要比较4次，因此一次不成功检索的元素平均比较次数就是（3+3+3+4+4+3+3+3+4+4）/10=3.4 。 由于算法的执行过程实质上是x与一系列中间元素A（mid）的比较过程，所以可以用一个二元比较树来描述。,二元比较树： （1）此树的结点由内结点和外结点组成； （2）

10、每个内结点表示一次元素比较，用圆形结点表示，在以元素比较为基础的二分检索中，每个内结点存放一个mid值； （3） 外结点用方形结点表示，在二分检索中它表示一次不成功的检索； （4）x如果在A 中出现，则算法就在一个圆形结点处结束，该结点将指出x在A中的下标； x如果不在A 中出现，则算法就在一个方形结点处结束，如图所示。,5,2,9,7,1,3,4,8,6,xA(1),A(1)xA(2),A(3)xA(4),A(2)xA(3),A(6)xA(7),A(5)xA(6),A(4)xA(5),A(8)xA(9),XA(9),A(7)xA(8),二元比较树：算法执行过程的主体是x与一系列中间元素a(m

11、id)比较。可用一棵二元树描述这一过程。,内结点：表示一次元素比较，用圆形结点表示，存放一个mid值；代表一次成功检索,外结点：在二分检索算法中表示一种不成功检索的情况，用方形结点表示。,若x在A中出现，则算法在一个圆形的内结点处结束。 若x不在A中出现，则算法的在一个方形的外结点处结束,注： 外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。,证明：考察以n个结点描述BINSRCH执行过程的二元比较树.,定理2.1 若n在区域2k-1, 2k)中，则对于一次成功的检索，BINSRCH 至多作k次比较，而对于一次不成功的检索，或者作k-1次比较或者作k次比较。,二分检索中每

12、次mid取中值，二元比较树是“结点平衡”树 当2k-1n2k时，结点分布情况为： 内结点：1至k级 外结点：k级或k+1级 外部结点在相邻的两级上最深一层或倒数第2层 比较过程： 成功检索在内结点处结束，不成功检索在外结点处结束 成功检索在i级的某个内结点终止时，元素比较次数是i 不成功检索在i级的外部结点终止，元素比较次数是i-1,由此：最坏情况下的成功检索和不成功检索的计算时间是（logn）,最好情况下的成功检索在根结点处到达，时间是（1），而最好情况的不成功检索要logn次元素比较，所以时间是（logn）。由于外部节点都在k和k+1级，因此，每种不成功检索的时间都是（logn），故平均情

13、况下不成功检索的计算时间是（logn）。,E=I+2n (1) 令S(n)是成功检索的平均比较数，则 S（n)=I/n+1 (2),平均情况下成功检索的时间复杂性分析： 设根到所有内部结点的距离之和称为内部路径长度I，由根到所有外部结点的距离之和称为外部路径长度E，可以证明：,为什么要+1,令U（n)是不成功检索的平均情况比较数，而任何一个外部结点所需要的比较数是由根到该结点路径的长度，由此得： U(n)=E/(n+1) (3) 利用（1）-（3）可以得到： S(n)=(1+1/n)U(n)-1 因此：平均情况下成功检索的时间复杂性为： (log n)。,五、一种二分检索的变形BINSEARC

14、H1。 BINSEARCH1的while循环中x和Amid之间只用作一次比较。,BINSEARCH1(A,n,x,j) 1 low 1 2 high n+1 3 while low high 4 do 5 6 mid (low + high) / 2 7 if (x Amid) /在循环中只比较一次 8 then high mid 9 else lowmid 10 11 if x = Alow 12 then j low /x出现 13 else j=0 / x不出现 14 return j,BINSEARCH和BINSEARCH1相比较可看出，对于任何一种成功的检索，BINSEARCH1平均

15、要比BINSEARCH多作 次比较。BINSEARCH1的最好、平均和最坏情况时间对于成功和不成功的检索都是 。,六、以比较为基础的检索算法 问题：设n个元素的有序表a1:n，a1 a2 an。检索一给定元素x是否在a中出现。 问：是否预计还存在有以元素比较为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有更低的数量级? 以比较为基础的算法：假定算法中只允许进行元素间的比较，而不允许对它们实施其它运算。,任何以比较为基础的检索算法,其执行过程都可以用二元比较树来描述。,内结点：表示一次元素的比较，并代表成功检索情况。每棵比较树中恰好含有n个内结点，分别与n个不同i值相对应,外结点：代表不成功检索情况。每棵比较树中恰好有n+1个外结点分别与n+1中不成功检索情况相对应。,一、直接求最大、最小元素 算法2.5 直接找最大和最小元素 maxmin(A,n) /将A(1:n)中的最大元素置于max，最小元素置于min/ 1 max A1 2 min A1; 3 for i 2 to n 4 do 5 6 if max Ai 7 then min Ai 8 ,2.