如果我们正在寻找线的交点(仅水平和垂直线)并且我们有 n 条线,其中一半是垂直的并且没有交点,那么
使用 mergesort 对 y 值上的线端点列表进行排序将采用 N log N
我们的数据结构(假设它是一个 b 树)的每次插入删除和搜索都将是 < log n
所以总搜索时间将是 N log N
我在这里遗漏了什么,如果使用合并排序的时间为 N log N,而插入和删除的时间为 < log n,我们是否删除常数因子以给出 N log N 的总时间。如果不是,那么 谢谢
最佳答案
大 O 表示法描述了算法的渐近行为。也就是说,它将算法的行为描述为 N 趋向于无穷大。算法中花费 N log N 时间的部分将使算法中花费 log N 时间的部分相形见绌。随着 N 变大,log N 部分的重要性逐渐降低。
关于java - B树修订,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2673801/