Изменения
Нет описания правки
== Оценка времени работы ==
== Объём памяти ==
Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения торезков, соседних в статусе, то объём используемой памяти сократиться до <tex>O(n)</tex>. Для этого нужно удалять точкт пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдется соседняя в статусе пара отрезков, которая пересекается в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.
== См. также ==
