Изменения

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

Список с пропусками

1177 байт добавлено, 17:45, 29 мая 2012
Вставка элемента
===Вставка элемента===
TodoДля вставки элемента в список с пропусками, нам необходимо выполнить следующие шаги:# Найти с помощью алгоритма поиска позицию, куда нам надо вставить этот элемент# Вставить наш элемент в нижний уровень списка с пропусками# «Подбросить монетку» и в зависимости от результата протолкнуть элемент на уровень выше# Повторять предыдущий шаг до тех пор, пока у нас «подброс монетки» дает положительный результат Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\frac{n}{2}</tex>, на третьем уровне <tex>\frac{n}{5}</tex> и т.д. На уровне <tex>log(n)</tex> у нас окажется <tex>\frac{n}{2^n}</tex> элементов. 
===Удаление элемента===
Todo
90
правок

Навигация