算法导论 — 思考题7-6 对区间的模糊排序

（对区间的模糊排序）考虑这样的一种排序问题：我们无法准确知道待排序的数字是什么。但对于每一个数，我们知道它属于实数轴上的某个区间。也就是说，我们得到了 $n$ 个形如 $[a_i, b_i]$ 的闭区间，其中 $a_i ≤ b_i$ 。我们的目标是实现这些区间的模糊排序，即对 $j = 1, 2, …, n$ ，生成一个区间的排列 $<i_1, i_2, …, i_n>$ ，且存在 $c_j∈[a_{i_j},b_{i_j}]$ ，满足 $c_1 ≤ c_2 ≤ … ≤ c_n$ 。
　　a. 为 $n$ 个区间的模糊排序设计一个随机算法。你的算法应该具有算法的一般结构，它可以对左边端点（即 $a_i$ 的值）进行快速排序，同时它也能利用区间的重叠性质来改善时间性能。（当区间重叠越来越多的时候，区间的模糊排序问题会变得越来越容易。你的算法应能充分利用这一重叠性持。）
　　b. 证明：在一般情况下，你的算法的期望运行时间为 $Θ(n{\rm lg}n)$ 。但是，当所有的区间都有重叠的时候，算法的期望运行时间为 $Θ(n)$ （也就是说，存在一个值 $x$ ，对所有的 $i$ ，都有 $x ∈ [a_i, b_i]$ 。）你的算法不必显式地检查这种情况，而是随着重叠情况的增加，算法的性能自然地提高。
　　
　　解
　　a.
　　对区间的模糊排序，简单来说只需要在每个区间上任意取一点 $c_i$ ，对 $c_i$ 进行排序即可。实际上， $“$ 任意取区间的一点 $”$ 变成 $“$ 取区间左侧端点 $”$ 也是可行的。故对区间的模糊排序，可以转变成对区间左侧端点的排序。
　　我们现在考虑区间重叠的情况。如果有多个区间重叠，那么在排好序的序列中，这些重叠的区间之间的顺序是可以任意的。对于排序来说，可以认为这些重叠的区间是 $“$ 相等 $”$ 的关系。例如，考虑 $2$ 个区间 $[a_i, b_i]$ 和 $[a_j, b_j]$ ，当 $a_i ≤ b_j$ 并且 $a_j ≤ b_i$ 时，两个区间就是重叠的，此时可以认为 $[a_i, b_i] = [a_j, b_j]$ ，如下图所示。
　　算法导论 — 思考题7-6 对区间的模糊排序
　　然而，这种 $“$ 相等 $”$ 关系不具备传递性，即 $[a_i, b_i] = [a_j, b_j]$ 并且 $[a_j, b_j] = [a_k, b_k]$ 成立，并不代表 $[a_i, b_i] = [a_k, b_k]$ 成立。如下图所示 $[a_i, b_i]$ 与 $[a_j, b_j]$ 重叠， $[a_j, b_j]$ 与 $[a_k, b_k]$ 重叠，但是 $[a_i, b_i]$ 与 $[a_k, b_k]$ 并不重叠。
　　算法导论 — 思考题7-6 对区间的模糊排序
　　那么我们应当如何判断多于 $2$ 个的区间互相之间是 $“$ 相等 $”$ 的。以 $3$ 个区间为例， $[a_i, b_i]$ 、 $[a_j, b_j]$ 和 $[a_k, b_k]$ 。先判断 $[a_i, b_i]$ 和 $[a_j, b_j]$ 是否重叠，如果重叠，找出重叠的范围，以下图为例，重叠的范围是 $[a_j, b_i]$ 。我们再比较重叠范围 $[a_j, b_i]$ 与第 $3$ 个区间 $[a_k, b_k]$ ，如果二者重叠，说明 $3$ 个区间是完全重叠的，它们互相之间也是 $“$ 相等 $”$ 的。如果还有第 $4$ 个区间，那我们就需要比较前 $3$ 个区间的重叠范围与第 $4$ 个区间。
　　算法导论 — 思考题7-6 对区间的模糊排序
　　综合以上分析，我们可以借用思考题7-2的针对相同元素的快速排序。在每次递归调用PARTITION时，先选定最后一个区间作为主元。在遍历其他区间时，如果遇到一个区间与主元有重叠，则判定二者 $“$ 相等 $”$ ，并且以二者的重叠区域作为新的主元；如果判定二者 $“$ 不相等 $”$ ，则按照区间左侧端点的大小关系将区间划分到对应的子数组。由以上步骤可知，在遍历过程中，主元区间是有可能变化的。
　　以下只给出区间模糊排序中PARTITION过程的伪代码。
　　算法导论 — 思考题7-6 对区间的模糊排序
　　b.
　　如思考题7-2的结论，该算法的期望运行时间为 $Θ(n{\rm lg}n)$ 。
　　如果所有区间都重叠，这意味着所有区间都 $“$ 相等 $”$ ，这种情况下PARTITION过程只会递归调用一次，所以此时算法的运行时间为 $Θ(n)$ 。

算法导论 — 思考题7-6 对区间的模糊排序

相关推荐