355
правок
Изменения
м
→Время работы, требуемая память
Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.
}}
{{Лемма
|statement=Среднее число рёбер, пересечённое отрезком <tex>qv_{i+1}</tex> во втором этапе алгоритма локализации, равно <tex>O(1)</tex>.
|id=edgeslemma
|proof=
{{TODO|t=Доказательство}}
}}
{{Лемма
|statement=Среднее число треугольников, посещённых на третьем этапе алгоритма локализации, равно <tex>O(1)</tex>.
|id=triangleslemma
|proof=
{{TODO|t=Доказательство}}
}}
{{Лемма
'''1 этап''': средняя степень вершины <tex>v_{i+1}</tex> равна <tex>O(1)</tex>, поэтому треугольников, в которых может лежать отрезок <tex>qv_{i+1}</tex> тоже <tex>O(1)</tex>. Просмотрев их все, за <tex>O(1)</tex> можно понять, в каком из них лежит отрезок <tex>qv_{i+1}</tex>.
'''2 этап''': число рёбер, пересечённых отрезком <tex>qv_{i+1}</tex>, равно <tex>O(1)</tex> {{TODO([[#edgeslemma|t=Почему?}}по лемме]]). Поэтому этот этап локализации тоже происходит за <tex>O(1)</tex>.
'''3 этап''': число треугольников, посещённых на третьем этапе локализации, равно <tex>O(1)</tex> {{TODO([[#triangleslemma|t=Почему?}}по лемме]]).
}}
{{Теорема
