算法设计与分析(三)分治法

《算法设计与分析(三)分治法》由会员分享，可在线阅读，更多相关《算法设计与分析(三)分治法（123页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析算法设计与分析2011.92011.9(ACM(ACM创新实验班创新实验班) )“分而治之”的问题求解策略。3.1 3.1 一般方法一般方法1. 1. 问题的提出问题的提出 用计算机进行问题求解时，如果问题的规模n很小，可以直接求解，如排序问题，当n=1时，不需任何计算即可完成。 当n=2时，作一次比较即可。当n=3时，作3次比较也可完成，当n比较大时，问题求解就不那么容易了。一般情况下，要想直接解决一个规模较大的问题，有时是相当困难的。该怎么办？三、分治法三、分治法（ Divide and Conquer Divide and Conquer ）如何求解规模较大问题？如何求解规

2、模较大问题？分析问题的特征，寻找合适的解决问题的方法 分治法是求解较大规模问题的一种有效方法，并是很多高效算法的设计基础。2. 分治法的基本思想 分治法的设计思想是，将一个难以直接解决的、规模较大问题，分割成若干个规模较小、相对容易解决的、但性质相同的子问题，然后分别解决这些子问题。在获得这些较小子问题的解之后，再将子问题的解合并成原始问题的解。 这种算法设计策略叫做分治法。具体的说，就是： 对于一个规模为n的问题，若规模较小，则直接解决；否则将其分解为k个规模较小的子问题，如果这些子问题还较大，则可以递归地将子问题分解为更小的子问题，直到子问题的规模足够小、可以直接求解为止，然后求解子问题，

3、并在得到子问题的解之后逐级合并，最后得到原问题的解。 原问题与子问题的求解是一个自然的递归过程，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 注：分治算法本身并不一定要用递归过程描述。可用分治法求解的问题一般应具有以下几个特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决；2) 该问题可以分解为若干个规模较小的“同质”问题；3) 子问题的解可以最终合并为原始问题的解； 4) 每次分解出的子问题是相互独立的，子问题之间不包含公共的子“子问题”。 分治法的三个基本步骤 ： 1）分解：将原问题分解为若干个规模较小、相互独立，但与原问题性质相同的子问题； 2）

4、求解：若子问题规模较小、可直接求解时则直接解，否则递归地求解各个子问题 3）合并：将各个子问题的解合并为原问题的解。 在用分治策略时，子问题应该怎样分解才为适宜？子问题的规模应该怎样才为适当？ 实践经验告诉我们，在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的k个子问题。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 。 许多问题可以取 k=2，二分法是最常用的分治策略。3.3.分治策略的抽象化控制过程分治策略的抽象化控制过程二分策略二分策略算法3.1 分治策略的抽象化控制procedure D

5、ANDC(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) /pmq/ return(COMBINE(DANDC(p,m), DANDC(m+1,q) endifend DANDCk=2：二分是最常用的分解策略；SMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小，是则无需再进一步分就可求解；G(p,q)： 当SMALL(p,q)为真时，对输入规模为q-p+1的子问题直接求解；DIVIDE(p.q)：当规模还较大时，进一步分解，返回p,q区间的

6、分割点；DANDC(p,m)、DANDC(m+1,q)：递归求解COMBINE(x,y)：结果合并函数最初的调用：DANDC(1,n)DANDC的计算时间 若所分成的两个子问题的规模大致相等，则DANDC总的计算时间可用递归关系式表示如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 注：T(n)：表示输入规模为n时的DANDC计算时间g(n)：表示对足够小的输入规模直接求解的计算时间f(n)：表示COMBINE对两个子区间的子结果进行合并的时间 1. 1. 问题的描述问题的描述 已知一个按非降次序排列的元素表a1, a2, ,an，判定某给定的元素x是否在该表中出现

7、。 若是，则找出x在表中的位置并返回其所在位置的下标 若非，则返回0值。3.23.2二分检索二分检索折半查找折半查找2. 2. 问题分析问题分析 1） 二分检索是有序表上的检索问题。 2）给出一种问题的形式描述如下： I=(n, a1, a2, ,an,x) 3）选取下标k，由此将I分解为3个子问题： I1=(k-1, a1, a2, ,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, a2, ,an,x) 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， 若xak，则只在I3中求解，对I1不用求解； 对I1 、I3的求解可再次采用分治方法求解规模较大规模足

8、够小规模较大递归过程算法3.1 二分检索procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1; highn; while lowhigh do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeat j0end BINSRCH3. 3. 二分检索二分检索 二分检索：每次选取中间元素的下标进行分解。注： 给定一个按非降次序排列的元素数组A(1:n)，n1,判断x是否出现。若是，置j，使得x=A(j)若非，j=0取中策略例3.1：设A(1:9)=(-15，-6，0，7，9

9、，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1表1 运行轨迹示例x=101x=-14x=82lowhighmidlowhighmidlowhighmid19519519569714269789811189899921找不到找到找到成功的检索不成功的检索成功的检索 1 2 3 4 5 6 7 8 9BINSRCH(A,n,x,j)能正确地运行吗？1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都能按要求正确执行即首先满足确定性和能行性2）终止性问题 算法初始部分置low1, highn 若n=0，不进入循环，j置0，算法终止 否则，进入循环，计算

10、mid, 或 x=A(mid)，j置为mid，算法终止； 或xA(mid)，置lowmid+1，进入下次循环；搜索范围实际缩小为mid+1, high，对low, mid-1区间不做进一步搜索； 因low, high, mid都是整型变量，故按照上述规则，在有限步内，或找到某个mid，有A(mid) = x；或变得lowhigh，在A中没有找到任何元素等于x，算法终止。1）空间特性 n+5个空间位置，分别存放A、x、j、 mid、low、high，所以空间复杂度为(n)。4.4.性能分析性能分析2) 时间特性 区分以下情况进行分析 成功和不成功检索情况: 成功检索：指所检索的x恰好在A中出现。

11、 由于A中共有n个元素，故成功检索恰好有n种可能的情况 不成功检索：指x不出现在A中。 根据取值情况，不成功检索共有n+1种可能性（用区间表示）： xA(1) 或 A(i)xA(i+1),1iA(n) 最好、最坏、平均检索情况最好情况：最少几次运算就能达到目的。 执行步数最少，计算时间最短。 成功检索的最好情况：若x恰好是A中的某个元素，最少 几次确定x在A中的出现位置：1次 不成功检索的最好情况：若x不是A中的任何元素，最少 几次能判断出这一结论最坏情况：最多几次运算才能达到目的。 执行步数最多，计算时间最长。平均情况：典型数据配置下的执行情况，一般为各种情 况下计算时间的平均值。运算的频率

12、计数的统计1. while循环体外语句的频 率计数为12. 集中考虑while循环中x与A 中元素的比较运算 其它运算的频率计数 与比较运算有相同的数量 级。 3. case语句的分析：假定只 需一次比较就可确定case 语句控制是三种情况的哪 一种。procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1; highn; while lowhigh do mid case :xA(mid):low mid+1 :else:jmid;return endcase repeat j0end BINSRCH实例分析（例实例分析（例3.13.

13、1）每种查找情况所需的元素比较次数统计如下： A 元素 -15 -6 0 7 9 23 54 82 101成功检索比较次数 3 2 3 4 1 3 2 3 4 不成功检索比较次数 3 3 3 4 4 3 3 3 4 4成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次n不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次基于二元比较树的分析基于二元比较树的分析（1）什么是二元比较树？ 算法过程的主体是x与一系列中间元素A(mid)比较运算。可用一棵二元树描述这一过程，称为二元比较树（2）二元比较树的构

14、成u结点：分为内结点和外结点两种 内结点：代表一次元素比较，用 圆形结 点表示，存放一个 mid值(下标)， 代表成功检索情况。 外结点：用方形结点表示， 表示不成功 检索情况，本身不代表比较操作。u路 径：代表检索中元素的比较序列u分 支：“小于”进入左分支， “大于” 进入右分支。例3.1的二元比较树二元比较树的查找过程p 若x在A中出现，则算法在一个圆形的内结点处结束p 若x不在A中出现，则算法在一个方形的外结点处结束 注：二元比较树中，外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处已经结束。 例3.1的二元比较树与x比较大于小于关于二分检索时间复杂度的定理关于二分检索

15、时间复杂度的定理定理3.1 若n在区域2k-1,2k)中，则对于一次成功的检索， BINSRCH至多做k次比较；对于一次不成功的检索， 或者做k-1次比较，或者做k次比较。证明要点证明要点：比较过程： 成功检索在内结点处结束，不成功检索在外结点处结束 成功检索在i级的某个内结点终止时，所需要的元素比较次数是i， 等于根到该内结点的路径长度1。 不成功检索在i级的外部结点终止所需的元素比较次数是i-1， 等于根到该外结点的路径长度。证明要点之二证明要点之二： 二分检索中，每次mid取中值，故其二元比较树是一种“结点平衡”的树： 当2k-1n2k时，结点分布情况为： 内结点：1至k级 外结点：k级

16、或k+1级， 外部结点在相邻的两级上 最深一层或倒数第2层证明：证明：由于由于由于由于：n2k-1,2k) klogn， 故，1）不成功检索 由于外结点在最末的两级上，故不成功检索的最好、最坏和平均情况的计算时间均为 2）成功检索 最好情况：根结点代表成功检索的最好情况，在第一级，故其计算时间为 最坏情况：最深一层的内结点代表成功检索的最坏情况，在第 级，故其计算时间为 这里利用外部结点和内部结点到根距离和之间的关系证明二分检索成功检索的平均计算时间为O(logn)。 由根到所有内结点的距离之和称为内部路径长度，记为I； 由根到所有外结点的距离之和称为外部路径长度，记为E。则有关系， E=I+

17、2n . 记， U(n)是不成功检索的平均计算时间，则 U(n) = E/(n+1) . S(n)是成功检索的平均计算时间，则 S(n) = I/n + 1 . 成功检索的平均情况下的计算时间是多少？ 由上面 得: S(n) = (1+1/n)U(n) -1 当n,S(n) U(n) ，而U(n) = 所以 S(n) =最后的结论： 证毕。 成功检索最好 平均 最坏不成功检索最好 平均 最坏以比较为基础的检索：算法中只允许使用元素间的比较运算， 而不允许对它们实施其它运算。问题：A为n个元素的有序表，设A(1:n)，A(1) A(2) A(n)。检索一给定元素x是否在A中出现。 问：是否存在其

18、它以元素比较为基础的检索算法，它的计 算时间在最坏情况下比二分检索有更低的数量级?4. 4. 以比较为基础检索的时间下界以比较为基础检索的时间下界分析分析：任何以比较为基础的检索算法，其执行过 程都可以用二元比较树来描述。内结点内结点：表示一次元素的比较，并代表：表示一次元素的比较，并代表成功检索成功检索情况。每棵比较树中恰情况。每棵比较树中恰 好含有好含有n n个内结点，分别与个内结点，分别与n n个不同个不同i i值相对应；值相对应；外结点外结点：代表不成功检索情况。每棵比较树中恰好有：代表不成功检索情况。每棵比较树中恰好有n+1n+1个外结点分别个外结点分别 与与n+1n+1中不成功检索

19、情况相对应。中不成功检索情况相对应。 以比较为基础的有序检索问题最坏情况下的时间下界：定理3.1 设A(1:n)含有 n(n1)个不同的元素，且有 A(1) A(2) max then maxA(i) endif if A(i) min then minA(i) endif repeatend STRAITMAXMIN 算法的性能： 在输入规模为n时，这个算法所执行的元素比较次数是2n-2。问题：有没有更快的算法解决上述问题？ 用分治法设计一个解决上述问题的算法。方法二，分治求解。 记问题的一个实例为：I = (n, a1 , an)。采用二分法将I分成两个子集合进行处理： 和 则有， MAX

20、(I) = max(MAX(I1),MAX(I2) MIN(I) = min(MIN(I1),MIN(I2) MAX(I)和MIN(I)分别代表I中元素的最大者和最小者。采用递归的设计策略，得到以下算法：找最大最小元素的递归算法找最大最小元素的递归算法算法3.4 递归求取最大和最小元素procedure MAXMIN(i,j,fmax,fmin) /A(1:n)是含有n个元素的全局数组，参数i,j是整数，1i,jn，代表当前的查找区间 / /该过程把A(i:j)中的最大和最小元素分别赋给fmax和fmin / integer i,j;global n,A(1:n) case :i=j: fma

21、xfminA(i) /只有一个元素 :i=j-1:if A(i)2当n是2的幂时(n=2k),化简上式有， T(n)=2T(n/2) +2 =2(2T(n/4) + 2) + 2 =2k-1T(2) + =2k-1+2k-2 =3n/2-2性能比较性能比较1）与STRAITMAXMIN算法相比，比较次数减少了25%（3n/2-2 : 2n-2)。已经达到了以元素比较为基础的找最大最小元素的算法计算时间的下界：2）存在的问题递归调用造成： 空间占用量大 入栈参数：i, j, fmax, fmin和返回地址五个值。 有 级的递归时间可能不比预计的理想 如果元素A(i)和A(j)的比较与i和j的比较

22、在时间上相差不大时，算法MAXMIN不可取。 详见计算机算法基础。方法三，改进的方法一。算法3.2-1 直接找最大和最小元素算法的改进procedure STRAITMAXMIN(A,n,max,min)/将A中的最大值置于max，最小值置于min/ Integer i,n maxminA(1) for i2 to n do if A(i) max then maxA(i) endif else if A(i) min then minA(i) endif repeatend STRAITMAXMIN 改进：最好的情况下只需要n-1次比较；但最坏的情 况下还是需要2(n-1)。平均3(n-1)

23、/2。策略：策略： 设fmin、fmax分别代表当前最小值和最大值。然后成对地处理集合中的元素：每对元素先互相比较，然后把较小者与fmin比较，把较大者与fmax比较，根据情况修正fmin和fmax。开始的时候置：开始的时候置：u 如果n为奇数，则将fmin=fmax=a1u 如果n为偶数，则fmin=min(a1,a2)，fmax=max(a1,a2)改进：改进： 这样的处理使得每二个元素比较三次即可，而不是每个元素都需要2次比较运算。故至多 次比较就可同时找出最大、最小元素。方法四：最坏情况为方法四：最坏情况为3n/23n/2的迭代算法的迭代算法1. 1. 归并排序归并排序 首先将原始数组

24、A中的元素分成两个子集合：A1(1: )和A2( +1 :n)。分别对这两个子集合单独分类，然后将已分类的两个子序列归并成一个含有n个元素的、分类好的序列。这样的一个分类过程称为归并分类。3.4 3.4 基于分治的分类算法基于分治的分类算法1 1）算法描述）算法描述算法算法3.4 3.4 归并分类算法归并分类算法procedure MERGESORT(low,high) /A(low:high)是一个全程数组，low和high分别指示当前待分类区间的最小下标和最大下标，含有high-low+10个待分类的元素/ integer low,high if lowmid then for kj to

25、 high do B(i) A(k);ii+1; repeat else for kh to mid do B(i) A(k);ii+1; repeat endif for k low to high do A(k) B(k) repeat /将已归并的集合复制到A中/ end MERGE2 2）性能分析）性能分析(1) 过程MERGE的归并时间与两数组元素的总数成正比，可表示为：cn。(2) 过程MERGESORT的分类时间用递推关系式表示如下: a n=1,a是常数 T(n)= 2T(n/2)+cn n1, c是常数 化简: 若n=2k,则有, T(n) =2(2T(n/4)+cn/2)+

26、cn = 4T(n/4) + 2cn =4T(2T(n/8) +cn/4) + 2cn = =2kT(1)+kcn = an+cnlogn /k=logn/ 若2kn2k+1，则有T(n)T(2k+1)。 所以得：T(n) = (nlogn) 3 3）一般讨论：以比较为基础分类的时间下界）一般讨论：以比较为基础分类的时间下界（1 1）分类的）分类的“ “本质本质” ” 给定n个记录R1,R2,Rn，其相应的关键字是k1,k2,kn。 分类就是确定1,2,n的一种排列P1,P2,Pn,使得记录的关键字满足以下非递减（或非递增）排列关系 从而使n个记录成为一个按关键字排列有序的序列： (2)(2)

27、以关键字比较为基础的分类算法的时间下界以关键字比较为基础的分类算法的时间下界 最坏情况下的时间下界为： 假设参加分类的n个关键字A(1),A(2),A(n)互异。任意两个关键字的比较必导致A(i)A(j)的结果。 利用二元比较树描述元素间的比较过程：u若A(i)A(j)，进入下一级的右分支 算法在外部结点终止。 从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。 故，以比较为基础的分类算法的最坏情况下界等于二元比较树的最小高度。初始集合

28、中的元素因顺序不同，将导致排序过程走不同的分支现基于二元树的性质有：现基于二元树的性质有： 由于n个关键字有n!种可能的排列，所以分类的二元比较树中将有 n!个外部结点。 每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列。 设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点。 记算法在最坏情况下所作的比较次数为T(n)，则有 T(n)=k 生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1；则，根据和的分析，有： n!2T(n) 化简： 当n1时，有n!n(n-1)(n-2)( )(n/2)n/2 当n4时，有 T(n)(n/2

29、)log(n/2)(n/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为： (nlogn) 2.2.快速分类快速分类 快速分类是一种基于划分的分类方法。 划分：在待分类集合A中选取某元素t，按照与t的大小关系重新整理A中元素，使得整理后t被置于序列的某位置上，而在t以前出现的元素均小于等于t，在t以后的元素均大于等于t。这一元素的整理过程称为划分（Partitioning）。 划分元素：元素t被称为划分元素。 快速分类：这种通过对待排序集合反复划分达到分类目的算法称为快速分类算法。1 1）算法描述）算法描述算法3.6 划划分过程（分过程（PARTITIONPARTITION）

30、算法描述）算法描述procedure PARTITION(m,p) /用A(m)划分集合A(m:p-1) integer m,p,i; global A(m:p-1) vA(m);im /A(m)是划分元素/ loop loop ii+1 until A(i)v repeat / i由左向右移/ loop pp-1 until A(p)v repeat /p由右向左移/ if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m)A(p)； A(p)v /划分元素在位置p/end PARTITION A(p)被定义，但为一限

31、界值，不包含在实际的分类区间内。pivv算法算法3.7 3.7 快速分类算法快速分类算法 procedure QUICKSORT(p,q) /将数组A(1:n)中的元素A(p),A(q)按递增的方式分类。 A(n+1)有定义，且假定A(n+1)+/ integer p,q;global n,A(1:n) if pq then jq+1 /进入时，A(j)定义了划分区间p,q的上界，首次调用时j=n+1 call PARTITION(p,j) /出口时，j带出此次划分后划分元素所在的下标位置/ call QUICKSORT(p,j-1) /对前一子集合递归调用 call QUICKSORT(j+

32、1,q) /对后一子集合递归调用 endif end QUICKSORT 2 2）快速分类算法时间分析）快速分类算法时间分析n统计的对象：元素的比较次数Partition过程，记为：C(n)n两点假设 参加分类的n个元素各不相同 PARTITION中的划分元素v是随机选取的（针对平均情况的分析）随机选取划分元素： 在划分区间m,p-1随机生成某一坐标：iRANDOM(m, p-1)； 调换A(m)与A(i)：vA(i); A(i) A(m); im 作用：将随机指定的划分元素的值调换到A(m)位置。算法主体 不变。之后，仍从A(m)开始执行划分操作。递归层次QuickSort(1,n)Quic

33、kSort(1,j1-1)QuickSort(j1-1,n)QuickSort(1,j21-1)QuickSort(j21+1, j1-1)QuickSort(j1-1,j22-1)QuickSort(j22+1,n)n个元素参加划分和分类去掉1个第一级的划分元素n-1个元素参加划分和分类去掉2个第二级的划分元素n-3个元素参加划分和分类去掉4个第三级的划分元素第一层第二层第三层 设在任一级递归调用上，调用PARTITION处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：理想情况，第一级少1，第二级少2，第三级少4， ；最坏情况，每次

34、仅减少1（每次选取的划分元素刚好是当前集合中最小或最大者）n 最坏情况分析最坏情况分析 记最坏情况下的元素比较次数是Cw(n)； PARTITION一次调用中的元素比较数是p-m+1，若一级递归调用上处理的元素总数为r，则 PARTITION的比较总数为O(r)。 最坏情况下（第i次调用Partition所得的划分元素恰好是第i小元素），每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。 即：Cw(n)= = (n2)n 平均情况分析平均情况分析 平均情况是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。

35、设调用PARTITION(m,p)时，所选取划分元素v恰好是A(m:p-1)中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是A(m:j-1)和A(j+1:p-1)的概率是：1/(p-m), mjp。 记平均情况下的元素比较次数是CA(n)；则有， 其中，n+1是PARTITION第一次调用时所需的元素比较次数。 CA(0) = CA(1) = 0 化简上式可得： CA(n)/(n+1)= CA(n-1)/n + 2/(n+1) = CA(n-2)/(n-1) + 2/n + 2/(n+1) = CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n

36、+1) = CA(1)/2+由于所以得，CA(n)2(n+1)loge(n+1) = (nlogn) 最坏情况下，递归的最大深度为n-1. 故，需要栈空间：O(n)改进： 使用一个迭代模型可以将栈空间总量减至： O(logn)3 3）快速分类算法空间分析）快速分类算法空间分析4）一个改进了的快速分类迭代算法模型处理策略：每次在Partition将文件A(p:q)分成两个文件A(p:j-1)和A(j+1,q)后，先对其中较小的子文件进行分类。当小的子文件分类完成后，再对大的子文件进行分类。栈：需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一

37、步分类。pqjtopj1算法3.8 QuickSort2(p,q) integer STACK(1:max),top /max=2 global A(1:n);local integer j top0 loop while pq do jq+1 call PARTITION(p,j); if j p high，然后把第i个元素前与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。（算法略）3. 3. 改进的插入分类算法改进的插入分类算法3.5选择问题选择问题1.问题描述问题描述 在n个元素的表A(1:n)中找第k小元素，1kn。注：A未经分类。2.设计思路设计思路 1）先排序，后查找）

38、先排序，后查找 排序后第k位的元素即为待查找的元素 时间复杂度O(nlogn) 存在的问题存在的问题：有点浪费，排序涉及了太多k以外的元素。 2）利用）利用PARTITION过程设计一个较低时间复杂度过程设计一个较低时间复杂度的算法的算法 PARTITION(1，n)：在第一次划分后，划分元素v被放在位置A(j)上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。此时， 若k=j，则A(j)即是第k小元素；否则， 若kj，则A(1:n)中的第k小元素将出现在A(j+1:n)中第k小元素在A(j+1:n)中，但是A(j+1:n)中的第k-j小元素1njk=jj-1元素n-

39、j元素A(j)即是第k小元素1njkjj-1元素n-j元素j+1:新的起点情况1：情况2：情况3：3. 利用PARTITION实现的选择算法 算法3.9 找第k小元素 procedure SELECT(A,n,k) /在数组A(1:n)中找第k小元素，并将之放在A(k)中。/ integer n,k,m,r,j; m1;r n+1;A(n+1) + /A(n+1)被定义，并置为一大值，用于限界/ loop /在进入循环时，1mkrn+1 / j r /将剩余元素的最大下标加1后置给j / call PARTITION(m.j) /返回j,它使得A(j)是第j小的值/ case :k=j: re

40、turn :kj, j+1是新的下界/ endcase repeat end SELECT 4. SELECT算法分析 两点假设 A中的元素互异 随机选取划分元素，且选择A中任一元素作为划分元 素的概率相同 分析 每次调用PARTITION（m,j),所需的元素比较次数是 (j-m+1)。 在执行一次PARTITION后，或者找到第k小元素，或者将 在缩小的子集(A(m,k-1)或A(k+1,j)中继续查找。缩小 的子集的元素数比上一次划分的元素数至少少1。1) 1) 最坏情况最坏情况 SELECT的最坏情况时间是(n2)最坏情况下的特例最坏情况下的特例： 输入A恰好使对PARTITION的第

41、i次调用选用的划分元素是第i小元素，而k=n。 此时，（区间下界）m随着PARTITION的每一次调用而仅增加1，j保持不变。 PARTITION最终需要调用n次。 则,n次调用的时间总量是2)2)平均情况平均情况 设 是找A(1:n)中第k小元素的平均时间。 是SELECT的平均计算时间，则有并定义则有：TA(n)R(n)。对n个不同的元素，问题实例可能有n!种不同的情况。综合考查所有情况后得到的平均值在所有可能的情况下，找所有可能的k小元素某个特定的k定理定理3.3SELECT的平均计算时间的平均计算时间TA(n)是是(n)证明： PARTITION的一次执行时间是(n)。在随机等概率选择

42、划分元素时，首次调用PARTITION中划分元素v刚好是A中第i小元素的概率为1/n，1in。 则，存在正常数c，c0,有， n2 且有， n2 划分元素ik,将在i的前半部分求解令令cR(1)R(1)。利用。利用数学归纳法数学归纳法证明，对所有证明，对所有n2n2，有，有R(n)4cn.R(n)4cn. 当n=2时，由上式得： 假设对所有的n, 2nm，有R(n)4cn 当n = m时，有， 由于R(n)是n的非降函数，故当m为偶数而k=m/2，或当m为奇数而k=(m+1)/2时， 取得极大值。因此， 若m为偶数，则 若m为奇数，则 由于TA(n)R(n)，所以TA(n)4cn。 故，TA(

43、n)=(n)1km-11m k+1m-15. 5. 最坏情况是最坏情况是 (n)(n)的选择算法的选择算法1）采用两次取中间值的规则精心选取划分元素）采用两次取中间值的规则精心选取划分元素 目标：精心选择划分元素，避免随机选取可能出现的极端情况。 步骤：分三步 首先，将参加划分的n个元素分成 组，每组有r个元素(r1)。（多余的 个元素忽略不计） 然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1i ，共得 个中间值一次取中。 之后，对这 个中间值分类，再找出其中间值mm。将mm作为划分元素执行划分二次取中。n例：设 n=35, r=7。 分为n/r = 5个元素组： B1，B2，B

44、3，B4，B5； 每组有7个元素。 B1-B5按照各组的mi的非降次 序排列。 mm = mi的中间值，1i5由图所示有：mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5r个元素的中间值是第 小元素；至少有 个mi小于或等于mm；也至少有 个mi大于或等于mm。 故，至少有 个元素小于或等于mm。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5

45、 同理，也至少有 个元素大于或等于mm。以以r=5r=5为例。为例。使用两次取中间值规则来选择划分元素v(即mm)，可得到，u 至少有 个元素小于或等于选择元素vu 且至多有 个元素大于等于v mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5同理同理，u 至少有 个元素大于或等于选择元素vu 且至多有 个元素小于等于v mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5故故， 这样的v可较好地划分A中的n个元素：比足够多的元素大，也比足够多的元素小，不论落在那个区域，总可以在下一步查找前舍去足够多的元素，而在剩下的“较小”范围内

46、继续查找。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B52 2）算法描述）算法描述算法3.10 使用二次取中规则的选择算法的说明性描述 Procedure SELECT2(A,k,n) /在集合A中找第k小元素 若nr，则采用插入排序法直接对A分类并返回第k小元素。否则 把A分成大小为r的 个子集合，忽略多余的元素 设M=m1,m2,m 是 子集合的中间值集合 vSELECT2(M, , ) jPARTITION(A，v) case :k=j: return(v) :kj: 设S是A(1:j-1)中元素的集合; return(SELECT2(S,k,j-1)

47、 :else: 设R是A(j+1:n)中元素的集合; return(SELECT2(R,k-j,n-j) endcase end SELECT2 3) 3) 算法分析算法分析 记T(n)是SELECT2所需的最坏情况时间 对特定的r分析SELECT2：选取r=5。 假定A中的元素各不相同，则有 若nr，则采用插入法直接对A分类并返回第k小元素 (1) 把A分成大小为r的 个子集合，忽略多余的元素 (n) 设M=m1,m2,mr 是 子集合的中间值集合 (n) vSELECT2(M, , ) T(n/5) jPARTITION(A，v) (n) case T(3n/4),当n24 :k=j: r

48、eturn(v) :kn 不再是线性关系。故有T(n)(n)改进： 方法一：将A集合分成3个子集合U,S和R，其中U是由A中所有与v相同的元素组成，S是由A中所有比v小的元素组成，R则是A中所有比v大的元素组成。 同时步骤更改： case :|S|k:return(SELECT2(S,k,|S|) :|S|+|U|k:return(v) :else: return(SELECT2(R,k-|S|-|U|,|R|) endcase 从而保证 |S|和|R|0.7n+1.2成立，故关于T(n)的分析仍然成立。 T(n) = (n)方法二：选取其他的r值进行计算 取r=9。重新计算可得，此时将有 个

49、元素小于或等于v，同时至少有 大于或等于v。 则 当n90时，|S|和|R|都至多为 基于上述分析，有新的递推式：相等元素的一半 c1n n90 T(n) T(n/9)+T(63n/72)+c1n n90 用归纳法可证： T(n)72c1n 即，T(n) = (n) 算法中需要解决的两个问题 1) 如何求子集合的中间值？ 当r较小时，采用INSERTIONSORT(A,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为中间下标位置所对应的元素。 2) 如何保存 个子集合的中间值？ 在各组找到中间元素后，将其调整到数组A的前部，按子集合的顺序关系连续保存。从而可方便用递归调用的方式

50、对这些中间值进行排序并找出中间值的中间值（即，二次取中）。 4 4）SELECT2SELECT2的实现的实现算法3.11 SELECT2算法的实现 procedure SEL(A,m,p,k) /返回一个i，使得im,p，且A(i)是A(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r; integer n,i,j loop if p-m+1r then call INSERTIONSORT(A,m,p); return (m+k-1); endif np-m+1 /元素数/ for i1 to do /计算中间值/ call INSERTIONSORT(A,m+

51、(i-1)*r,m+i*r-1) /将中间值收集到A(m:p)的前部/ call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1) repeat jSEL(A,m,m+ -1, )/mm/ call INTERCHANGE (A(m),A(j) /产生划分元素，将之调整到第一个元素/ jp+1 call PARTITION(m,j) case :j-m+1=k: return(j) :j-m+1k: pj-1 :else: kk-(j-m+1);mj+1 endcase repeat end SEL算法3.12 SELECT2算法实现的递归程序描述 procedure

52、 SEL(A,m,p,k) /返回一个i，使得im,p，且A(i)是A(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r; integer n,i,j if p-m+1r then call INSERTIONSORT(A,m,p); return (m+k-1); endif np-m+1 /元素数/ for i1 to do /计算中间值/ call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) /将中间值收集到A(m:p)的前部/ call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1) repeat jS

53、EL(A,m,m+ -1, )/mm/ call INTERCHANGE (A(m),A(j) /产生划分元素，将之调整到第一个元素/ jp+1 call PARTITION(m,j) case :j-m+1=k: return j :j-m+1k: return SEL(A,m,j-1,k) :else: return SEL(A,j+1,p,k-(j-m+1) endcaseend SEL3.6 矩阵乘积的Strassen算法1. 回顾一下矩阵运算 已知两个n阶方阵： A(aij)nxn , B(bij)nxn 1）矩阵加法 CAB (cij)nxn ，其中, 计算量：(n2) 2）矩阵乘

54、法 CAB (cij)nxn ，其中， 计算量：(n3)。共有n2个cij需要计算，每个cij需要n 次乘运算,n-1次加法问：是否可以用少于n3次乘法完成C的计算? 1969年Strassen： n2.812. 矩阵乘法 例 2X2的两个矩阵，直接相乘的计算过程如下： 故，A、B直接相乘，需要8次乘法和4次加法 StrassenStrassen的计算方法：的计算方法： 令： P=(a11+a22)(b11+b22) Q=(a21+a22) b11 R=a11 (b12-b22) S=a22 (b21-b11) T=(a11 + a12)b22 U=(a11 a21) (b11 + b12)

55、V=(a12 a22) (b21 + b22) 则， c11=P+S-T+V = (a11+a22)(b11+b22) + a22 (b21-b11) -(a11 + a12)b22+(a12 a22) (b21 + b22) a11b11+a12b21 c12=R+T a11b12+a12b22 c21=Q+S a21b11+a22b21 c22=P+R-Q-U a21b12+a22b22 Strassen计算方法的分析： 令： P=(a11+a22)(b11+b22) Q=(a21+a22) b11 R=a11 (b12-b22) S=a22 (b21-b11) T=(a11 + a12)

56、b22 U=(a11 a21) (b11 + b12) V=(a12 a22) (b21 + b22) 则， c11=P+S-T+V c12=R+T c21=Q+S c22=P+R-Q-U计算量：计算量： 乘法次数：7次 加（减）法次数：18次特点：特点： 增加了加（减）法计算量，减少了乘法计算量带来的改进：带来的改进： 直观上，在用程序完成的计算中，通常认为乘法运算比加法运算需要更多的时间，Strassen矩阵乘通过减少乘法计算量、适当增加加法计算量，从总体上减少矩阵乘的运算时间。到底能减少多少呢？StrassenStrassen矩阵乘法的一般形式矩阵乘法的一般形式（1969年Strasse

57、n ） 设 n 2k ，两个n阶方阵为 A(aij)nxn B(bij)nxn （注：若n2k ，可通过在A和B中补0使之变成阶是2的幂的方阵） 首先，将A和B分成4个(n/2)x(n/2)的子矩阵： 对比对比：简单矩阵分块相乘：简单矩阵分块相乘 8次(n/2)x(n/2) 矩阵乘 4次(n/2)x(n/2) 矩阵加 任意两个子矩阵块的乘可以沿用同样的规则继续下去，即：如果子矩阵的阶大于2，则将子矩阵分成更小的子矩阵，直到每个子矩阵只含一个元素为止。 从而可以构造出一个递归计算过程。时间分析：时间分析： 令T(n)表示两个nxn矩阵相乘的计算时间，则首次分块时，需要： 1) 8次(n/2)x(

58、n/2) 矩阵乘 8T(n/2) 2) 4次(n/2)x(n/2) 矩阵加 dn2 故， 其中，b，d是常数 化简：T(n) = O(n3)StrassenStrassen矩阵乘的一般方法（矩阵乘的一般方法（分块分块）令 P=(A11+A22)(B11+B22) Q=(A21+A22) B11 R=A11 (B12-B22) S=A12 (B21-B11) T=(A11 + A12)B22 U=(A11 A21) (B11 + B12) V=(A12 A22 ) (B21 + B22) 则， C11=P+S-T+V C12=R+T C21=Q+S C22=P+R-Q-U计算量：(n/2)x(n

59、/2) 矩阵乘法：7次(n/2)x(n/2) 矩阵加法：18次 注：Strassen矩阵乘也是一个递归求解过程， 任意两个子矩阵块的乘可以沿用同样的规则进行。StrassenStrassen矩阵乘法的计算复杂度分析矩阵乘法的计算复杂度分析 令T(n)表示两个n=2k阶矩阵的Strassen矩阵乘所需的计算时间，则有： b n2 T(n) = 7T(n/2) + an2 n2 其中， a和b是常数 化简： T(n) = an2(1+7/4+(7/4)2+(7/4)k-1) + 7kT(1) cn2(7/4)logn+7logn cn2nlog(7/4) + nlog7 cnlog4+log7-l

60、og4 + nlog7 (c+1)nlog7 (nlog7)(n2.81)#includeusingnamespacestd;constintN=6;/DefinethesizeoftheMatrixtemplatevoidStrassen(intn,TAN,TBN,TCN);templatevoidinput(intn,TpN);templatevoidoutput(intn,TCN);intmain()/DefinethreeMatricesintANN,BNN,CNN;/对对A和和B矩阵赋值，随便赋值都可以，测试用矩阵赋值，随便赋值都可以，测试用for(inti=0;iN;i+)for(

61、intj=0;jN;j+)Aij=i*j;Bij=i*j;/调用调用Strassen方法实现方法实现C=A*BStrassen(N,A,B,C);/输出矩阵输出矩阵C中值中值output(N,C);system(pause);return0;/*TheInputFunctionofMatrix*/templatevoidinput(intn,TpN)for(inti=0;in;i+)coutPleaseInputLinei+1endl;for(intj=0;jpij;/*TheOutputFanctionofMatrix*/templatevoidoutput(intn,TCN)coutThe

62、OutputMatrixis:endl;for(inti=0;in;i+)for(intj=0;jn;j+)coutCijendl;/*MatrixMultiplicationasthenormalalgorithm*/templatevoidMatrix_Multiply(TAN,TBN,TCN)/CalculatingA*B-Cfor(inti=0;i2;i+)for(intj=0;j2;j+)Cij=0;for(intt=0;t2;t+)Cij=Cij+Ait*Btj;/*MatrixAddition*/templatevoidMatrix_Add(intn,TXN,TYN,TZN)fo

63、r(inti=0;in;i+)for(intj=0;jn;j+)Zij=Xij+Yij;/*MatrixSubtraction*/templatevoidMatrix_Sub(intn,TXN,TYN,TZN)for(inti=0;in;i+)for(intj=0;jn;j+)Zij=Xij-Yij;/*参数参数n指定矩阵指定矩阵A,B,C的阶数，因为随着递归调用的阶数，因为随着递归调用Strassen函数函数*矩阵矩阵A,B,C的阶数是递减的的阶数是递减的N只是预留足够空间而已只是预留足够空间而已*/templatevoidStrassen(intn,TAN,TBN,TCN)TA11NN,A

64、12NN,A21NN,A22NN;TB11NN,B12NN,B21NN,B22NN;TC11NN,C12NN,C21NN,C22NN;TM1NN,M2NN,M3NN,M4NN,M5NN,M6NN,M7NN;TAANN,BBNN;if(n=2)/2-orderMatrix_Multiply(A,B,C);else/ 将矩阵将矩阵A和和B分成阶数相同的四个子矩阵，即分治思想。分成阶数相同的四个子矩阵，即分治思想。 for(inti=0;in/2;i+)for(intj=0;jn/2;j+)A11ij=Aij;A12ij=Aij+n/2;A21ij=Ai+n/2j;A22ij=Ai+n/2j+n/2

65、;B11ij=Bij;B12ij=Bij+n/2;B21ij=Bi+n/2j;B22ij=Bi+n/2j+n/2;/CalculateM1=(A0+A3)(B0+B3)Matrix_Add(n/2,A11,A22,AA);Matrix_Add(n/2,B11,B22,BB);Strassen(n/2,AA,BB,M1);/CalculateM2=(A2+A3)B0Matrix_Add(n/2,A21,A22,AA);Strassen(n/2,AA,B11,M2);/CalculateM3=A0(B1-B3)Matrix_Sub(n/2,B12,B22,BB);Strassen(n/2,A11,

66、BB,M3);/CalculateM4=A3(B2-B0)Matrix_Sub(n/2,B21,B11,BB);Strassen(n/2,A22,BB,M4);/CalculateM5=(A0+A1)B3Matrix_Add(n/2,A11,A12,AA);Strassen(n/2,AA,B22,M5);/CalculateM6=(A2-A0)(B0+B1)Matrix_Sub(n/2,A21,A11,AA);Matrix_Add(n/2,B11,B12,BB);Strassen(n/2,AA,BB,M6);/CalculateM7=(A1-A3)(B2+B3)Matrix_Sub(n/2,A

67、12,A22,AA);Matrix_Add(n/2,B21,B22,BB);Strassen(n/2,AA,BB,M7);/CalculateC0=M1+M4-M5+M7Matrix_Add(n/2,M1,M4,AA);Matrix_Sub(n/2,M7,M5,BB);Matrix_Add(n/2,AA,BB,C11);/CalculateC1=M3+M5Matrix_Add(n/2,M3,M5,C12);/CalculateC2=M2+M4Matrix_Add(n/2,M2,M4,C21);/CalculateC3=M1-M2+M3+M6Matrix_Sub(n/2,M1,M2,AA);Ma

68、trix_Add(n/2,M3,M6,BB);Matrix_Add(n/2,AA,BB,C22);/SettheresulttoCNfor(inti=0;in/2;i+)for(intj=0;jn/2;j+)Cij=C11ij;Cij+n/2=C12ij;Ci+n/2j=C21ij;Ci+n/2j+n/2=C22ij;Strassen矩阵乘法是通过递归实现的，C+实现代码如下： Strassen矩阵乘法只有在n相当大时才优于通常的矩阵乘法。 理论意义大于实际意义。3.7 3.7 最近点对问题最近点对问题1. 问题描述 已知平面上分布着点集P中的n个点p1,p2,.pn，点i的坐标记为(xi,y

69、i)，1in。两点之间的距离取其欧式距离，记为 问题：找出一对距离最近的点。注：允许两个点位于同一个位置，此时两点之间的距离为0。平面上分布的点集pipj分析：分析： 一种全搜索的方法：对每对点都计算距离，然后比较大小，找出其中的最小者。 该方法的时间复杂度为： 计算点间距离： O(n2)，因为需要计算n(n-1)/2对 点间的距离。 找最小距离：O(n2)，因为需要n(n-1)/2-1次比较。 所以，总的时间复杂度：O(n2)。问：有没有更好的办法？有没有更好的办法？2.2.求解最近点对问题的分治方法求解最近点对问题的分治方法 这里，利用分治法设计一个具有O(nlogn)时间复杂度的算法求解

70、最近点对问题设计策略：设计策略： 1）首先将所有的点按照x坐标排序。排序过程需要O(nlogn)的时间，不会从整体上增加时间复杂度的数量级。 2）划分：由于点已经按x坐标排序，所以空间上可以“想象” 画一条垂线，作为分割线，将点集分成左、右两半PL和PR。 则，最近的一对点或者在PL中，或者在PR中，或者一个在PL中而另一个在PR中（跨越分割线）。记, dL:PL中的最近点对距离； dR:PR中的最近点对距离； dC:跨越分割线的最近点对距离。dLdCdR分割线PLPR 建立一个递归过程求dL和dR，并在此基础上计算dC。而且，要使得dC的计算至多只能花O(n)的时间。 这样，递归过程将由两个

71、大致相等的一半大小的递归调用和O(n)附加工作组成，总的时间就可以控制在O(nlogn)以内（事实上，我们希望该时间达到O(nlogn)）。 基于上述思想的算法流程大致描述如下： (1)做分割线（垂线）将点集分为PL和PR两部分 (2)递归地在PL中的找具有dL的点对 (3)递归地在PR中的找具有dR的点对 (4)在跨越分割线的点对中找具有dC的点对 (5)返回min(dL,dR,dC)对应的点对。 该如何实现？该如何实现？ 令=min(dL,dR)，通过观察可得，如果dC ，则dC对应的点对必然在分割线两侧的 距离以内，如图所示。把这个区域叫做带(strip)。从而，对dC的搜索只限制在st

72、rip区域内即可，限定了需要考虑的点的个数。dLp1dRp2p3p6p4d5strip3）计算dC方法一：对均匀分布的大型点集，可预计位于该带中的点的个数均匀而“稀疏”，平均只有 个点在这个带中。因此，可以O(n)的时间计算出这些点对之间的距离。描述如下： for i=1 to numPointsInStrip do for j=i+1 to numPointsInStrip do if dist(pi,pj)。 dCx y 计算dC的改进： 设点按它们的y坐标排序，如果pi和某个pj的y坐标相差大于，那么这样的pi可以终止计算，继续处理pi+1。改进的算法描述如下： for i=1 to n

73、umPointsInStrip do for j=i+1 to numPointsInStrip do if pi and pj s y-coordinates differ by more than break; else if dist(pi,pj) = dist(pi,pj);分析： 上述改进对运算时间的影响是显著的，因为对每一个pi，在pi和pj的y坐标相差大于时就会退出内层循环，这一过程中仅有少数的点pj被考察，大大减少了计算量。如， dLp1dRp2p3p6p4d5对于p3只有两个点p4和p5落在垂直距离之内的带状区域中。 一般情况：对于任意的点pi，在最坏情况下，最多有7个点pj

74、需要考虑。 这是因为，pi和pj点必定落在该带状区域左半部分的X方块内，或者落在该带状区域右半部分的X方块内。最坏情况下，每个方块包含4个点，分别落在四个角上，并且其中一个是pi，另外7个就是需要考虑的pj点。如图所示，左半部分(x )右半部分(x)PL1PL2PL3PL4PR1PR2PR3PR4这样，对于每个pi，有最多7个点pj要考虑，所以对每个pi的计 算时间可看作是O(1)的。则，计算比 好的dC的时间就 为O(n)。于是得：最近点对求解过程由两个一半大小的递归调用加上合 并两个结果的线性附加工作组成，那么最近点对问题就 可以得到O(nlogn)的解了吗？还有问题需要讨论：还有问题需要

75、讨论：点y坐标的排序问题。 问题所在：如果每次递归都要对点的y坐标进行排序，则这又要有O(nlogn)的附加工作。总的时间为 可得，整个算法的时间复杂度就为O(nlog2n)。如何处理？进一步改进进一步改进：改进对点的坐标进行排序的处理方法。策略策略：设置两个表， P表：按x坐标对点排序得到的表； Q表：按y坐标对点排序得到的表。 这两个表可以在预处理阶段花费O(nlogn)时间得到。再记，PL和QL是传递给左半部分递归调用的参数表， PR和QR是传递给右半部分递归调用的参数表。首先：在使用上述策略将P分为两个部分之后，复制Q到QL和 QR中，然后删除QL和QR中不在各自范围内的点，这一 操作

76、花费O(n)时间即可完成。而此时QL和QR均已按y坐 标排好序。 然后：将PL、PR和上面的QL、QR带入递归过程进行处理，PL、 PR是按照x坐标排序的点集，QL、QR是按照y坐标排序 的点集。最后：当递归调用返回时，扫描Q表，删除其x坐标不在带内的 所有点。此时Q中就只含有带中的点，而且这些点已是 按照y坐标排好序了的。这一处理需要O(n)的时间。综上所述综上所述，所有附加工作的总时间为O(n)，则整个算法的 计算时间为作业题：1. 棋盘覆盖问题。 在一个2k x 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。如图1所示，蓝色的为特殊方

77、格： 棋盘覆盖问题是指，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 试用分治法设计一个求解棋盘覆盖问题的算法。图1 特殊棋盘，蓝色的为特殊方格图2 四中L形骨牌2.大整数乘积 大整数（big integer）：位数很多的整数，普通的计算机不能直接处理，如： 9834975972130802345791023498570345 显然，这样的整数普通的计算机和程序语言是无法直接表示的。 大整数运算：给定两个n位的整数I，J, 加、减法：可以用O(n)的时间计算出I+J和I-J，即使I、J是大整数； 乘法：若I、J超过普通计算机可以表示的数据范围，怎么计算IxJ? 如 I = 9834975972135791023498570345 J = 3432450018098972347892345023方法一：按照小学数学的方法，“列算式”直接求解。适当地编制算法，可以实现大整数乘，但时间复杂度为O(n2)。方法二：利用分治法设计一个计算两个n二进制位的大整数相乘的算法，要求计算时间低于O(n2)。分析你所给出的算法的时间复杂度。3. 计算机算法基础P99，4.54. 计算机算法基础P100，4.205. 计算机算法基础P100，4.25