B树修订

Question

如果我们正在寻找线的交点（水平和垂直线只），我们有一半的垂直n行并没有交集，然后

分拣线终点的y值之列表会采取使用归并

每个插入删除和查找我们的数据药结构的（假设它的一个b-tree）将<为log N

因此总的搜索时间将是N日志N

N日志ñ如果我在这里错过了什么他使用mergesort进行排序的时间需要N log N的时间，插入和删除需要一段时间< log n我们是否将常数因子降低到N log N的整个时间。如果不是那么怎么回事< log n缺失在总的运行时间？

谢谢

Answer 1

big-O符号描述算法的渐近行为。也就是说，它将算法的行为描述为朝向无穷大的趋势。算法的这一部分需要花费时间的部分算法，该部分需要日志N时间。 N部分的重要性减小到相对无关，因为N变大。

Answer 2

我怀疑你的导师指的是Line Segment Intersection的问题，这比简单的排序片段更复杂。您会注意到，本文引用了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树结构。