《分治递归算法》-课件.pptVIP

对于最后一条的例子： 求最长非递减子序列 如： a[]={1,2,3,2,3,2,3,4,5,6,6,8} 则所得结果为a[5]到a[11]为最长的非递减序列 怎样写这么个程序？ Divide and Conquer * Divide and Conquer * Divide and Conquer * Divide and Conquer * * * 自己考虑下归并排序是不是也满足这些要求？ * 思考：对于这个问题，该如何分解？ * 给定平面上n个点的坐标, 找出其中欧几里德最近的两个点 枚举算法: 需要枚举O(n2)个点对, 每个距离的计算时间为O(1), 总O(n2) 有更好的算法吗? 最近点对问题 * 分治法求解需要考虑哪些问题？与前两题有什么不同？ 令d=min{dl, dr}, 则跨越两边的点对中，只有竖条中的才有可能更近 * 需要检查竖条里的所有点对吗? 在最糟糕的情况下，n个点可能全部都在竖线里！ * 从上往下看, 对于任何一个p, 另一侧可能与它组成更近的点对在一个正方形中, 它最多只有4个点(否则这个方格中会有距离比d小的点对) * 最坏情况(同一行的红蓝点几乎重合), 需要检查接下来的7个点 * Closest-Pair(P, 1, r)//点集P[]，从第1个点到第r个点 if r – l 3 then return Brute-Force(P, l, r) q ? é(l+r)/2ù//点集分解 dl ? Closest-Pair(P, l, q-1)//递归求解 dr ? Closest-Pair(P, q, r) d ? min(dl, dr) for i ? l to r do//考察处在分界线中间的元素 if P[q].x - d ￡ P[i].x ￡ P[q].x + d then append P[i] to S Sort S on y-coordinate//对中间元素的y坐标排序 for j ? 1 to size_of(S)-1 do if any of d(S[j],S[j]+1), ..., d(S[j],S[j]+7) is smaller than d, set d to the smallest 13. return d * 由于合并时要把竖条内的点按y坐标排序, 因此合并是O(nlogn)的 递归方程: 解得T(n)=O(nlog2n) 下面把它优化到O(nlogn) 时间复杂度分析 * Closest-Pair(P, 1, r)//点集P[]，从第1个点到第r个点 if r – l 3 then return Brute-Force(P, l, r) q ? é(l+r)/2ù//点集分解 dl ? Closest-Pair(P, l, q-1)//递归求解 dr ? Closest-Pair(P, q, r) d ? min(dl, dr) for i ? l to r do//考察处在分界线中间的元素 if P[q].x - d ￡ P[i].x ￡ P[q].x + d then append P[i] to S Sort S on y-coordinate//对中间元素的y坐标排序 for j ? 1 to size_of(S)-1 do if any of d(S[j],S[j]+1), ..., d(S[j],S[j]+7) is smaller than d, set d to the smallest 13. return d * 如果左右两边集合的点都是在y轴方向上有序的，并且方向相同，那么在对中间元素的y值进行时排序就可以在O(n)时间内完成。 如何使左右集合的点在y轴方向上有序呢？ * 实现把所有点分别按x和y排序放在两个有序表x表和y表 Divide. 把点按x值分成两半后, 按顺序遍历y表, 根据x值拆分成两个y表. 这一步O(n) Combine. 合并得到拆分前的y表, 同时把在竖条内的点提取出来扫描一遍, 这一步O(n) 因此时间复杂度降为O(nlogn) 现详细描述对y表的两个操作 优化 * x表为: (1, 3), (2, 2), (3, 4), (4, 1) y表为: (4, 1), (2, 2), (1, 3), (3, 4) 根据x表, 需把点分成两部分: x=2和x=3 按顺序遍历y表, 判断出四个点应分别放在右边、左边、左边和右边, 拆分后的结果为 左边(红色)y表: (2, 2), (1, 3) 右边(蓝色)y表: (4, 1), (3, 4) 拆分后得到的两个点集仍分