B 树修订版

Question

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

使用归并排序对 y 值上的线端点列表进行排序将需要 N log N

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

，所以总搜索时间将为 N log N

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

谢谢

Answer 1

大 O 表示法描述了算法的渐近行为。也就是说，它描述了算法的行为N趋向于无穷大。需要 N log N 时间的算法部分将使需要 log N 时间的算法部分相形见绌。当 N 变大时，log N 部分的重要性会降低到相对为零。

Answer 2

我怀疑你的导师指的是线段相交的问题，它比只需对片段进行排序即可。您会注意到，本文引用了 Shamos–Hoey 算法，该算法使用二叉树来存储线段并有效地检测相交。

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

例如，假设您沿 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 树结构的算法。