Изменения

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

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

389 байт убрано, 04:37, 22 февраля 2014
Нет описания правки
<tex>p_{m - j}</tex> был последним из <tex>p_0, p_1, \dots, p_m</tex> интересным квадратом в <tex>Q_{i + 1}</tex> небходимо, чтобы среди этих как минимум <tex>j + 1</tex> непустых четвертинок только одна (вероятность этого назовём <tex>Pr_1</tex>) или ноль (вероятность этого назовём <tex>Pr_0</tex>) были непустыми в <tex>Q_{i + 1}</tex>. Иначе, если будет хотя бы пара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>.
''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет. Хотя я постарался расписать поподробней, чем в статье.''
<tex>q = 1 - p</tex>
Анонимный участник

Навигация