Изменения

Рассмотрим время работы для списка В качестве примера рассмотрим список с двумя уровнями<tex>L_1</tex> и <tex>L_2</tex>.Тогда время работы алгоритма поиска Поскольку элементы по уровням распределяются равномерно, то в среднем количество элементов между двумя соседними элементами уровня <tex>L_2</tex> будет зависеть от количества элементов на уровне составлять <tex>\dfrac{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 = \sqrt{n}</tex> сумма достигает минимального значения. Таким образом, время работы:поиска элемента составляет в среднем <tex>O(\sqrt{n})</tex>, отсюда выходит, что удаление и добавления элемента также происходит за <tex>O(\sqrt{n})</tex>, а для того, чтобы эффективнее использовать такой список, нам нужно генератор равновероятных чисел с вероятностью <tex>\dfrac{1}{\sqrt{n}}</tex>.

<tex> \approx \vert L_2\vert + \dfrac{\vert L_1\vert }{\vert L_2\vert } = \vert L_2\vert + \dfrac{n}{\vert L_2\vert }</tex> МинимизируяДопустим, мы получаемчто у нас имеется не два, что а <tex>\vert L_2 \vert ^ 2 = nk</tex> В итоге время за которое мы найдем элемент в списке с пропусками с двумя уровнями будет равняться: <tex> \sqrt{n} + \dfrac{n}{\sqrt{n}} = 2 \sqrt{n}</tex> Также можно убедиться, что список с пропусками, имеющий уровней. Тогда оптимально на каждом из <tex>k</tex> уровней, будет лучше всего работать с проходить не более <tex dpi=150>\sqrt[k]{n} </tex> элементами на уровне; время работы такого списка будет равно элементов, отсюда выходить оценка для поиска, добавления и удаления элементов равная <tex dpi=150>k O(\sqrt[k]{n} )</tex>.Для <tex>\log_2{n}</tex> уровней же время работы составит <tex dpi=150> \log_2{n} \cdot \sqrt[\log_2{n}]{n} = n ^ {\frac{1}{log_2{n}}} \cdot \log_2{n} = n ^ {\log_n{2}} \cdot \log_2{n} = 2\log_2{n}</tex>