0

如果我们正在寻找线的交叉点（仅限水平线和垂直线）并且我们有 n 条线，其中一半是垂直的并且没有交叉点，那么

使用合并排序对 y 值上的行端点列表进行排序将花费 N log N

每次插入删除和搜索我们的数据结构（假设它是一个 b-tree）将是 < log n

所以总搜索时间将是 N log N

我在这里缺少什么，如果使用合并排序的时间需要 N log N 并且插入和删除需要 < log n 的时间，我们是否会丢弃常数因子以给出 N log N 的总时间。如果不是，那么< log n 怎么会在 ONotation 总运行时间中丢失？

谢谢

4

2 回答 2

1

big-O 符号描述了算法的渐近行为。也就是说，它将算法的行为描述为N趋向于无穷大。需要N log N时间的算法部分将使需要 log N时间的算法部分相形见绌。随着N变大，log N部分的重要性相对而言会降低。

于 2010-04-20T09:05:10.557 回答
0

我怀疑你的导师指的是Line Segment Intersection的问题，它比简单地对线段进行排序更复杂。您会注意到本文引用了 Shamos–Hoey 算法，该算法使用二叉树来存储线段并有效地检测交叉点。

Michael 是正确的，因为对于一次性的线段，使用二叉树是没有意义的。然而，在检测交叉点的情况下，排序后搜索将产生二次性能，并不是最好的方法，因此线检测算法使用二叉树。

例如，假设您沿 x 轴从左到右对线段进行排序。一个简单的检测算法将类似于：

for (int i=0; i<segs.length - 1; ++i) {
  boolean searching = true;

  for (int j=i+1; j<segs.length && searching; ++j) {
     if (segments overlap on x-axis) {
       // Check for intersection.
     } else {
       // No overlap so terminate inner loop early.
       // This is the advantage of having a sorted list.
       searching = false;
     }
  }
}

由于双重嵌套循环，最坏的情况是 O(n^2)，并且发生在所有线段在 x 轴上重叠时。最好的情况是线性的，并且在 x 轴上没有任何线段重叠时发生。

您可能希望从实现朴素算法开始，然后是使用 B 树结构的算法。

于 2010-04-20T10:39:52.220 回答