90
правок
Изменения
Новая страница: «'''Список с пропусками''' (''skip-list'') — одна из вероятностных структур данных, на ряде паралл...»
'''Список с пропусками''' (''skip-list'') — одна из вероятностных структур данных, на ряде параллельных отсортированных связных списков с эффективностью, сравнимой с бинарными деревьями поиска. Все операции со списком с пропусками осуществляются за <tex>O(\log{n})</tex> с большой вероятностью.
Отсортированный связный список является простейшей структурой со временем поиска <tex>\theta(n)</tex>. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>L_1</tex>, в котором содержатся все элементы и <tex>L_2</tex>, в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
1. Начинаем поиск элемента в верхнем левом углу
2. Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу
3. Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex>
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \approx \vert L_2\vert + \frac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \frac{n}{\vert L_2\vert }</tex>
Минимизируя, мы получаем, что <tex>\vert L_2 \vert ^ 2 = n</tex>
В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:
<tex> \sqrt{n} + \frac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:
* Для трех уровней: <tex> 3 \sqrt[3]{n}</tex>
* Для четырех уровней: <tex> 4 \sqrt[4]{n}</tex>
* Для пяти уровней: <tex> 5 \sqrt[5]{n}</tex>
* Для <tex>\log{n}</tex> уровней: <tex> \log{n} \sqrt[\log{n}]{n} = 2 \log{n}</tex>
В списках с пропусками, в которых содержится <tex>\log{n}</tex> уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в <tex>\log{n}</tex> списке с пропусками будет осуществляться за асимптотическое время <tex>O(\log{n})</tex>.
===Вставка элемента===
Todo
===Удаление элемента===
Todo
Отсортированный связный список является простейшей структурой со временем поиска <tex>\theta(n)</tex>. Одним из способов улучшить асимптотику данной структуры является добавление дополнительного уровня, обеспечивающего быстрый доступ через несколько элементов.
==Операции над структурой==
===Поиск элемента===
Допустим, что в нашем списке с пропусками существуют два уровня: <tex>L_1</tex>, в котором содержатся все элементы и <tex>L_2</tex>, в котором присутствует только часть из них. Между одинаковыми элементами этих двух списков существуют ссылки.
В таком случае алгоритм поиска в этой структуре будет представлять из себя следующие операции:
1. Начинаем поиск элемента в верхнем левом углу
2. Передвигаться будем по списку <tex>L_2</tex>, пока значение в следующей ячейке меньше или равно ключу
3. Переместиться в нижний уровень и продолжить аналогичный метод поиска по списку <tex>L_1</tex>
Тогда время работы алгоритма поиска будет зависеть от количества элементов на уровне <tex>L_2</tex>. Представим, что на этот уровень у нас случайным образом попало несколько элементов. Следовательно в худшем случае поиска мы получим следующую оценку на время работы:
<tex> \approx \vert L_2\vert + \frac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \frac{n}{\vert L_2\vert }</tex>
Минимизируя, мы получаем, что <tex>\vert L_2 \vert ^ 2 = n</tex>
В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться:
<tex> \sqrt{n} + \frac{n}{\sqrt{n}} = 2 \sqrt{n}</tex>
Делая аналогичные подсчеты для списков с пропусками, в которых содержится больше уровней, получаем:
* Для трех уровней: <tex> 3 \sqrt[3]{n}</tex>
* Для четырех уровней: <tex> 4 \sqrt[4]{n}</tex>
* Для пяти уровней: <tex> 5 \sqrt[5]{n}</tex>
* Для <tex>\log{n}</tex> уровней: <tex> \log{n} \sqrt[\log{n}]{n} = 2 \log{n}</tex>
В списках с пропусками, в которых содержится <tex>\log{n}</tex> уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в <tex>\log{n}</tex> списке с пропусками будет осуществляться за асимптотическое время <tex>O(\log{n})</tex>.
===Вставка элемента===
Todo
===Удаление элемента===
Todo
