170
правок
Изменения
м
В общемЭто почти геометрическая прогрессия, только на полином домножили, определяется всё равно экспоненциальным множителем, если так подумать, что это <tex>O(1)</tex>. Мне весьма лень Можно совсем строго написатьоценить, но вообще и так понятно. Разумеется, при условии <tex>p \in (0, 1)</tex>. Это почти геометрическая прогрессиячто ряд сходится, а сойтись он может только на полином домножилик константе.
Нет описания правки
Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое [[Список с пропусками | skip list]], и необходимо знать, что такое [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.
The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1</tex> каждый элемент из <tex>S_0</tex> входит с вероятностью <tex>p\in (0, 1)</tex> и так далее. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} сжатое квадродерево над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.
Заметим, что если какой-то квадрат [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересный]] в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-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>
}}
