47
правок
Изменения
м
\theta -> \Theta; log -> \log
'''Список с пропусками''' (''skip-list'') — одна из вероятностных структур данных, на ряде параллельных отсортированных связных списков с эффективностью, сравнимой с бинарными деревьями поиска. Все операции со списком с пропусками осуществляются за <tex>O(\log{n})</tex> с большой вероятностью.
Отсортированный связный список является простейшей структурой с временем поиска <tex>\thetaTheta(n)</tex>. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.
==Операции над структурой==
# Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат
Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\frac{n}{2}</tex>, на третьем уровне <tex>\frac{n}{4}</tex> и т.д. На уровне <tex>\log({n)}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\frac{1}{2}</tex>, на третий <tex>\frac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log({n)}</tex> равна <tex>\frac{1}{n}</tex>
===Удаление элемента===
