228
правок
Изменения
→Запрос
При добавлении в карту очередного отрезка(в дальнейшем итерация алгоритма) глубина графа увеличивается максимум на 3. Из этого мы можем сделать простую оценку.
Наибольшее время на запрос, которое мы можем потратить {{---}} <tex>3n</tex>. Произойдет это в самом ужасном из самых ужасных случаев.
Как говорилось раньше отрезки мы добавляем рандомно, а потому редко будет самый ужасный случай и с вероятностных точек зрения время на запрос будет меньше.
