355
правок
Изменения
м
}}
{{Теорема
|statement=
Локализационная структура занимает <tex>O(n)</tex> памяти.
|proof=
Триангуляция для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На уровне <tex>k</tex> точек <tex>m_k=p \cdot m_{k-1}</tex>. Получим геометрическую прогрессию, сумма которой равна <tex>O(n)</tex>.
→Время работы, требуемая память
=== Время работы, требуемая память ===
==== Память ====
{{Лемма
|statement=
Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.
}}
{{Теорема
|statement=
Локализационная структура занимает <tex>O(n)</tex> памяти.
|proof=
Триангуляция для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На уровне <tex>k</tex> точек <tex>m_k=p \cdot m_{k-1}</tex>. Получим геометрическую прогрессию, сумма которой равна <tex>O(n)</tex>.
}}
==== Время работы ====
{{Лемма
|statement=Среднее число рёбер, пересечённое отрезком <tex>qv_{i+1}</tex> во втором этапе алгоритма локализации, равно <tex>O(1)</tex>.
|proof=
Очевидное следствие из [[#levelslemma|леммы о числе уровней]] и [[#onelevellemma|леммы о времени, требуемом на локализацию на каждом уровне]].
}}
