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