Изменения

На каждом уровне совершается <tex>O(1)</tex> шагов поискадля любой точки <tex>x</tex>.

ЫЫЫПусть в <tex>Q_i</tex> (то есть на <tex>i</tex>-ом уровне) поиск точки <tex>x</tex>, начинающийся с корня, проходит по квадратам <tex>p_0, p_1, \dots, p_m</tex>. Пусть случайная величина <tex>j</tex> {{---}} количество шагов поиска в <tex>Q_i</tex>, тогда <tex>p_{m - j}</tex> {{---}} последний квадрат из <tex>p_0, p_1, \dots, p_m</tex>, являющийся интересным в <tex>Q_{i + 1}</tex>. Оценим вероятность того, что делается <tex>j</tex> шагов. Забьём на случай <tex>j = 0</tex>, так как он не важен при расчёте мат. ожидания. На пути <tex>p_{m - j + 1} \dots, p_m</tex> будет хотя бы <tex>j + 1</tex> непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустых четвертинки, одна из них {{---}} следующий квадрат на пути, в котором тоже хотя бы 2 непустых четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустых четвертинки. Чтобы <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>. Иначе, если будет хотя бы 2 непустые четвертинки, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>. ''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет'' <tex>Pr_0 \leq p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше. <tex>Pr_1 \leq (j + 1) \cdot p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ровно одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше. ''В общем, если чуть подумать, оценки на <tex>Pr_0</tex> и <tex>Pr_1</tex> довольно ясны.'' <tex>E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)})</tex> В общем, если так подумать, это <tex>O(1)</tex>. Мне пока лень совсем строго написать, но вообще и так понятно. Разумеется, при условии <tex>p \in (0, 1)</tex>.