355
правок
Изменения
→Время работы, требуемая память
Матожидание числа уровней в локализационной структуре — <tex>O(\log n)</tex>.
|proof=
Для оценки матожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex> при вероятности пройти на следующий уровень равной <tex>p</tex>. <tex>p(h \leq k) = (1 - p^{k + 1})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k + 1</tex>, равна <tex>p^{k + 1}</tex>. <tex>p(h \geq k) = (1 - (1 - p^k)^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k</tex>, равна <tex>1 - p^k</tex>. <tex>p(h = k) = 1 - p(h > k) - p(h < k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq 1 - (1 - p^k)^n \leq np^k</tex> <tex>E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)</tex> Оценим первую сумму: <tex>p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n \leq p(1) \cdot \log_{1/p} n + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n = O(\log(n))</tex>, поскольку сумма этих вероятностей не превосходит единицу. Оценим вторую сумму: <tex>\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k</tex> Рассмотрим эту сумму: <tex>\sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{TODO|tk =Доказательство0}^{\infty}(k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n))</tex> Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.
}}
{{Лемма
Локализационная структура занимает <tex>O(n)</tex> памяти.
|proof=
Триангуляция для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На уровне <tex>k</tex> точек <tex>m_k=p \cdot m_{{TODO|t=Доказательство}k-1}</tex>. Получим геометрическую прогрессию, сумма которой равна <tex>O(n)</tex>.
}}
