2

我有一个算法问题，我想看看它是否可以比 O(n) 更好地解决：

我给出了一个包含 n 个元素的表 T，其中每个元素都是一个元组 (s_i, e_i)，其中 s_i、e_i 在 N 中且 s_i < e_i，即每个元组都是某种区间。我必须找到与给定间隔 [t0, t1] 重叠的所有间隔，其中 t0, t1 在 N 和 t0 < t1。此外，我有两个可用的排序列表 S 和 E，分别包含 s 值或 e 值，以及指向 T 中相应条目的索引 i。这些列表分别按 s 值或 e 值排序。（假设 s 和 e 值都是唯一的。）

问题：

我们必须在 T 中找到每个区间/元组 (s_i, e_i)，其中 s_i <= t1 且 e_i >= t0。

到目前为止我的想法：

我们可以通过应用一个区间边界来排除一些元素，即在 S 中搜索 t1 或在 E 中搜索 t0。这为我们提供了剩余元素的列表 L：

L <- {e in E | e >= t0} or L <- {s in S | s <= t1}

但是，无论我们执行哪种搜索，L 中的元素数量都没有下限。此外，如果 s <= t1 或 e >= t0，我们必须分别检查 L 中的每个元素，具体取决于我们之前执行的搜索。

该解决方案的复杂度为 O(n)。

但是，假设 k 是与区间 [t0, t1] 重叠的最大元素数。如果我们假设 k << n，那么复杂度是 O(n/2)，因为我们可以通过选择适当的 L 搜索来排除至少 n/2 个元素。仍然 O(n/2) 在 O(n) 中。

你能想出更好的方法来解决这个问题吗？

（请随时改进这个问题。也许不是很清楚。谢谢）

4

2 回答 2

2

如果您对答案中的间隔数一无所知k，则无法击败O(N)，因为结果中可能有 N 个间隔。

如果你知道 k 比 N 小很多，你可能会做得更好。使用二进制搜索，您可以找到最后一个 i0 thats_i<t0和第一个 i1 that s_i1>t1。

然后你会找到最后一个 j0 thate_j0<t0和第一个 j1 that e_j1>t1。

结果介于 max(i0,j0) 和 min(i1, j1) 之间。所以你有 O(logN) + O(k)。

于 2013-09-14T18:14:44.967 回答
0

解决方案可以在cs.stackexchange.com找到：一般问题不能在 O(n) 以内解决。区间树为搜索与某个其他区间重叠的区间提供了 O(log n) + O(k) 复杂度，假设 k 是重叠区间的数量。

于 2013-09-16T03:56:59.713 回答