Изменения

Структура данных основана на многоуровневом связном отсортированном списке. На самом нижнем (первом) уровне располагаются все элементы в отсортированном порядке. Дальше почти половина элементов таким же образом располагаются на втором, почти четверть <tex>-</tex> на третьем и так далее, но при этом известно, что если элемент расположен на каком-то уровнем <tex>iL_i</tex>-ом уровне, то он также соответственно расположен и на всех уровнях <tex>(i-1)L_j</tex>-ом, где <tex>(j < i-2)</tex>-ом и более низких уровнях.

Список с пропусками строится на основе существующего односвязного отсортированного спискаДопустим, что нам задан односвязный отсортированный список. 

Добавив дополнительные уровниТогда на первом уровне мы расположим заданный список, каждый из которых представляет предыдущий уровень без нечетных элементовна втором <tex>-</tex> только элементы с чётными номерами с ссылками на соответствующие элементы первого уровня, на третьем <tex>-</tex> с номерами, мы получим возможность осуществлять поисккратными <tex>4</tex>, вставку и удаление элементов подобно операциям с двоичным деревом поискатак далее. Соответственно, асимптотика этих операций Такой список будет составлять позволять в среднем за <tex>O(\log({n)})</tex>выполнять операции поиска, добавления и удаления элементов. 

Допустим, что в нашем списке с пропусками существуют <tex>k</tex> уровней, при этом первым уровнем (<tex>L_1</tex>) будет исходный список.

# Переместиться на один уровень вниз и перейти к пункту 2. Если рассматриваемый элемент находится на нижнем уровне <tex>- </tex> выйти из поиска

В Если в качестве примера рассмотрим список с двумя уровнями случайного источника использовать честную монету, то тогда если в списке будет <tex>L_1n</tex> и <tex>L_2</tex>. Поскольку элементы по уровням распределяются равномерноэлементов, то количество уровней в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет составлять равно <tex>\dfraclog{n}{\vert L_2 \vert}</tex>. Оценим среднее время доступа к элементу. Мы пройдём Тогда на последнем уровне будет не более <tex>\vert L_2 \vert</tex> двух элементов , а на втором каждом следующем будет почти в два раза больше. Тогда на каждом уровне, однако, мы проверим не более двух элементов (если бы на каком-нибудь шаге мы спустимся на нижней уровеньуровне проверили три элемента, то пройдём в среднем не более <tex>\dfrac{n}{\vert L_2 \vert}</tex> элементов (в противном случае это значило, что мы могли бы пройти ещё на верхнем уровне на один элемент на втором уровнебольше). Минимизируем величину <tex>\vert L_2 \vert + \dfrac{n}{\vert L_2 \vert}</tex>. Очевидно, что при Уровней всего <tex> \vert L_2 \vert = \sqrtlog{n}</tex> сумма достигает минимального значения. Таким образом, время откуда вытекает оценка времени поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrtlog{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>.

Допустим '''T''' find ('''list''' skip_list, что у нас имеется не два, а '''K''' key) '''node''' res '''for''' (res = skip_list.head; res.ref != ''null''; res = res.ref) <texfont color=darkgreen>k// Пока ещё не дошли до первого уровня </texfont> уровней '''while''' res. Тогда оптимально на каждом из key <texkey <font color=darkgreen>k</tex> уровней проходить не более <tex>\sqrt[k]{n}/ Переходим к следующему элементу</texfont> элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная <tex>O res = res.next(\sqrt[k]{n})</tex> '''return''' res.data

Таким образом# Найти с помощью алгоритма поиска позицию, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>\dfrac{n}{4}</tex> и т.дгде мог бы находиться элемент. На уровне <tex>\log{n}</tex> у нас окажется один # Вставить наш элементв текущий уровень списка с пропусками# Подбросить монету. Ну и соответственно вероятности попасть элементу # Если выпал «Орёл» то перейти на второй уровень — это выше и вернуться к шагу <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.# Иначе закончить операцию вставки

Используя монетку с распределением отличным от Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>. Используя монетку с распределением отличным от <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex>}, математическое ожидание количества элементов на уровне <tex>lk</tex> равно <tex dpi=150>n q^lk</tex>, каждый уровень на каждом следующем уровне будет составлять в среднем в <tex>q</tex> от предыдущего; раз больше элементов. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k}{q} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>\log(n)</tex> уровней получаем оценку, полученную ранее.