B-Tree Revision

Question

Если мы ищем пересечения линий (только горизонтальные и вертикальные линии), и у нас есть n линий с половиной из них вертикальных и без пересечений, то

Сортировка списка конечных точек строки по значению y займет N log N с использованием сортировки слиянием

Каждое удаление вставки и поиск в нашей структуре данных (при условии, что это b-дерево) будет

, поэтому общее время поиска будет N log N

Что мне здесь не хватает, если время сортировки с использованием mergesort занимает время N log N, а вставка и удаление занимают время

Спасибо

Answer 1

Обозначение big-O описывает асимптотическое поведение алгоритма. То есть он описывает поведение алгоритма как N , стремящееся к бесконечности. Часть алгоритма, которая занимает N log N время, будет карликовой частью алгоритма, который занимает log N время. Значение логарифмической части N уменьшается практически до нуля, так как 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-дерева.