B树修订

Question

如果我们正在寻找线路相交（仅水平和垂直线），并且我们有n行，其中一半垂直，没有交叉点

对y值的行终点列表进行排序将使用Mergesort进行n log n

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

因此，总搜索时间为n log n

我在这里缺少什么，如果使用Mergesort进行分类的时间需要n log n和插入和删除的时间<log n，我们会丢弃恒定因素才能给出n log n的超级时间。 <log n如何在总发射时间中丢失？

谢谢

Answer 1

BIG-O符号描述了该算法的渐近行为。也就是说，它将算法的行为描述为 n 无穷大的趋势。采用算法的部分 n 日志 n 时间将使获取日志的算法部分相形见 n 时间。日志的意义 n 一部分会减少相对较少的东西 n 变大。

Answer 2

我怀疑您的导师指的是 线段交点, ，这比简单地对细分进行排序更为复杂。您会注意到，本文引用了Shamos -Hoey算法，该算法使用二进制树来存储线段并有效地检测交叉点。

迈克尔是正确的，因为对于一次性的线段，使用二进制树是毫无意义的。但是，在检测相交的背景下，排序然后进行搜索将产生二次性能，并且不是最佳方法，因此为什么线检测算法使用二进制树。

例如，假设您从左到右对X轴沿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树结构的算法。