算法设计与分析（第二章 递归与分治策略）.pptVIP

2.9 线性时间选择 第二种方法 Select的计算时间复杂性T(n)： 设数组长度为n 当n75时，算法select所用的计算时间不超过某一常数C1 当n≥75时，for循环执行n/5次，每次用时为某一常数（固定个数即5个中查找！）；select找中位数的中位数，由于长度为原长度的1/5，所以用时可记为T(n/5)；划分以后所得到数组至多有3n/4个元素，用时记为T(3n/4)。所以T(n)可以递归表示为： 复杂度分析 T(n)=O(n) 2.10 最接近点对问题 问题的提出： 给定平面上（二维）n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对的距离最小。 2.10 最接近点对问题 最直接的方法： 将每一个点与其他n-1个点的距离计算出来，找出最小距离的2点。 问题： 效率太低，需要O(n2)的计算时间。 已经证明： 该算法的计算时间下界是Ω(nlogn)。 目的： 寻找效率更高的方法，在Θ(nlogn)时间算法。 2.10 最接近点对问题 改进的方法--分治法： 将n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归的求最接近点对。 问题： 如何将求出的子集的最接近点对合并为原集合的最接近点对。 2.10 最接近点对问题 为了使问题易于理解和分析，先来考虑一维（线性）的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。 一个简单的办法是先把x1,x2,…,xn排好序，再进行一次线性扫描就可以找出最接近点对，T(n)=O(nlogn)。 问题：这种方法无法推广到二维情形。 2.10 最接近点对问题 假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。 递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。 能否在线性时间内找到p3,q3？ 下面来考虑一维的情形。 一维情况 2.10 最接近点对问题 一维情况 如果S的最接近点对是{p3,q3}，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。 由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。如[m, m+d)中有S中的点，则此点就是S2中最小点。 因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。 能否在线性时间内找到p3,q3？ 可能存在的问题： 分割点m的选取不当，会造成|S1|=1，|S2|=n-1的情形，使得： T(n) =T(n-1)+O(n)=O(n2) 解决方法： 这种情形可以通过“平衡子问题”方法加以解决，选取各点坐标的中位数作分割点。 2.10 最接近点对问题 一维情况 2.10 最接近点对问题 一维情况 由此，求一维点集S的最接近点对的算法为： public static double cpair1(S) { n=|S|; if (n2) return ∞; m=S中各点坐标中位数; 构造S1和S2; //S1={x|x=m} S2={x|xm} d1=cpair1(S1); d2=cpair1(S2); p=max(S1); q=min(S2); d=min(d1, d2, q-p); return d; } 复杂度分析 T(n)=O(nlogn) 2.10 最接近点对问题 二维情况 下面来考虑二维的情形。 设S中的点为平面上的点，它们都有两个坐标值x和y。 选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。 递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。 能否在线性时间内找到p,q？ 2.10 最接近点对问题 二维情况 考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中 由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。 因此，在分治法的合