B-Tree Редакция

Question

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

Сортировка списка конечных линии точек на у значения будет взять N журнал N с использованием сортировки слиянием

Каждая вставка удаления и поиска нашего structue данных (при условии, сво-дерева) будет < лог н

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

Что мне здесь не хватает, если t он время сортировки с использованием mergesort занимает время N log N, а вставка и удаление занимает время < log n - мы отбрасываем постоянный коэффициент, чтобы дать избыточное время N log N. Если нет, то как получается < log n пропадает без вести в общем, время работы ONotation?

Благодаря

Answer 1

Большой-O обозначение описывает асимптотическое поведение алгоритма. То есть он описывает поведение алгоритма как N тенденции к бесконечности. Часть алгоритма, который принимает N log N Время будет затмевать часть алгоритма, который принимает журнал N время. Значимость журнала N уменьшается до нуля, так как N становится большим.

Answer 2

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

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

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

Возможно, вам захочется начать с реализации наивного алгоритма, за которым следует структура, использующая структуру B-дерева.