B-дерево редакция

Question

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

Сортировка списка строк конечных точек на значении y будет принимать n log n, используя mergesort

Каждая вставка Удалить и поиск нашей структуры данных (при условии, что его B-дерево) будет <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

Я подозреваю, что ваш репетитор имеет отношение к проблеме Сегмент линии пересечения, что сложнее, чем просто сортировка сегментов. Вы отмечете, что эта статья ссылается на алгоритм шамо-ходью, который использует двоичное дерево для хранения сегментов линии и эффективно обнаружено пересечений.

Майкл правильно в том, что использование бинарного дерева бессмысленно для одноразового рода линейных сегментов. Однако в контексте обнаружения пересечений сортировка, а затем поиск, даст квадратичную производительность и не является наилучшим подходом, поэтому алгоритмы обнаружения линии используют двоичные деревья.

Например, предположим, что вы сортируете свои сегменты линии вдоль оси 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-деревьев.