java - B树修订

Question

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

使用 mergesort 对 y 值上的线端点列表进行排序将采用 N log N

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

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

我在这里遗漏了什么，如果使用合并排序的时间为 N log N，而插入和删除的时间为 < log n，我们是否删除常数因子以给出 N log N 的总时间。如果不是，那么

谢谢

Answer 1

大 O 表示法描述了算法的渐近行为。也就是说，它将算法的行为描述为 N 趋向于无穷大。算法中花费 N log N 时间的部分将使算法中花费 log N 时间的部分相形见绌。随着 N 变大，log N 部分的重要性逐渐降低。