Изменения
Нет описания правки
Математическое ожидание количества уровней составляет <tex>O(\log(n))</tex>
|proof=
Для оценки мат. ожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex>. <tex>p(h = k) = 1 - p(h \leq > k) \cdot - p(h \geq < k)</tex>.
<tex>p(h < k) = (1 - p^{k})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k</tex>, равна <tex>p^{k}</tex>.
<tex>p(h > k) = (1 - (1 - p^{k + 1})^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k + 1</tex>, равна <tex>1 - p^{k + 1}</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>O(\log(n))</tex> в среднем.
|proof=
}}
