Изменения

Перейти к: навигация, поиск

Skip quadtree: определение, время работы

230 байт убрано, 00:17, 22 февраля 2014
Нет описания правки
Для оценки мат. ожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex>. <tex>p(h = k) = p(h \leq k) \cdot p(h \geq k)</tex>.
<tex>p(h \leq l k) = (1 - p^{k})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k</tex>, равна <tex>p^{k}</tex>.1<tex>p(h \g k) = (1 - (1 - p^{k + 1})^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k + 1</tex>, равна <tex>1 - 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>
Анонимный участник

Навигация