Изменения
Нет описания правки
== Оценка времени работы ==
{{Теорема
|statement=Время работы алгоритма {{---}} <tex>O((n+I)\log{n})</tex>, где <tex>I</tex> {{---}} количество пересечений.
||proof=Инициализация <tex>Q</tex> может быть выполнена за <tex>O(n\log{n})</tex>, инициализация <tex>T</tex> {{---}} за <tex>O(1)</tex>.
Далее, по ходу алгоритма мы обрабатываем каждое событие. Обработка включает в себя удаление события (<tex>O(nlog{n})</tex>), вызов функции findIntersection до двух раз, что может вызвать вставку новых событий <tex>O(n\log{n})</tex>. Также при обработке события <tex>p</tex> мы <tex>m(p) = \vert L(p) \cup C(p) \cup \U(p) \vert</tex> раз выполняем операции вставки, удаления, поиска над <tex>T</tex>. Каждая из этих операций требует <tex>O(\log{n})</tex> времени. Пусть <tex>m = \sum_{p} {m(p)}</tex>. Тогда время работы алгоритма {{---}} <tex>O(m\log{n})</tex>
Покажем, что <tex>m = O(n + I)</tex>, где <tex>I</tex> {{---}} количество пересечений.
Итак, время работы алгоритма: <tex>O((n+I)\log{n})</tex>.
}}
== Объём памяти ==
