Главная » Java, Структуры данных и алгоритмы » Вероятностный анализ skip-списков

0

Как уже отмечалось, skip-списки обеспечивают простую реализацию упорядоченного словаря. Но с точки зрения скорости выполнения skip-списки не являются самой лучшей структурой. В действительности, если не ограничить процедуру ввода от возможности выхода за пределы текущего верхнего уровня, алгоритм ввода рискует зациклиться (конечно, это не бесконечный цикл, так как вероятность выпадения монетки только одной стороной равна 0). Более того, невозможно беспрестанно добавлять в список элементы, не рискуя израсходовать всю память. В любом случае при завершении ввода объекта на верхнем уровне h максимальное время выполнения операций findElement, insertltem и removeElement в skip-списке S с количеством объектов п и высотой h составит 0(п + И). Такие затраты времени будут в случае, если высота башни каждого элемента достигает уровня h – 1, где h — высота списка S. Данная ситуация маловероятна. Из этого крайнего случая следует, что структура skip-списка строго подчинена другим реализациям словаря, приведенным в этой главе. Но такой вывод не вполне справедлив, так как эта возможность решения переоценивается.

Поскольку при вводе применяется генерация случайных чисел, то при анализе skip-списка необходимо учитывать определенную степень вероятности. Для начала это может выглядеть как соглашение по умолчанию, поскольку полный и тщательный вероятностный анализ может потребовать глубоких математических доказательств (в литературе о структурах данных и алгоритмах такие глубокие исследования приводятся). К счастью, для подобного анализа не обязательно понимание возможного асимптотического поведения skip-списков. Неформальный, интуитивный вероятностный анализ, приводимый ниже, основывается на базовых концепциях теории вероятности.

Определим предполагаемое значение высоты h списка 5 (считаем,что процесс ввода не останавливался на начальной стадии). Вероятность сохранения объекта на уровне i равна вероятности падения монеты одной и той же стороной (например, орлом), то есть составит 1/2′. Следовательно, максимальная вероятность наличия на уровне хотя бы одного объекта равна

с учетом известного соотношения — вероятность осуществления одного из п равновероятных событий составляет сумму вероятностей каждого.

Вероятность того, что высота h списка S больше /, равна вероятности наличия на уровне / хотя бы одного объекта, то есть не более Р/. Это означает, что h больше 3 log п с вероятностью максимум

Проще говоря, при константе с > 1 значение h будет больше с log п с максимальной вероятностью \/пс_\. Тогда минимальная вероятность того, что значение h меньше или равно clog п, составляет \ — \/пс-\. Таким образом, с высокой степенью вероятности можно утверждать, что высота h списка S составляет O(log п).

Рассматривая время выполнения поиска в skip-списке S, напомним, что такой поиск предполагает два вложенных while-цикла. Внутренний цикл выполняет сканирование вперед на уровне S до тех пор, пока не найдется ключ, не превосходящий ключ поиска к. Внешний цикл опускается вниз на следующий уровень и повторяет сканирование. Поскольку высота h списка S с высокой степенью вероятности составляет O(log п), количество переходов с той же вероятностью составит O(log п).

Теперь остается определить количество шагов сканирования вперед. Допустим, щ — количество ключей, исследуемых в процессе сканирования на уровне /. После ключа в стартовой позиции каждый последующий ключ при сканировании уровня / не может одновременно принадлежать уровню / + 1. Если бы любой из этих объектов находился на предыдущем уровне, он был бы обнаружен на предыдущем шаге сканирования. Таким образом, вероятность вхождения ключа в щ равна 1/2. Следовательно, предполагаемое значение щ точно будет равно предполагаемому количеству подбрасываний монеты, прежде чем выпадет «орел», то есть 2. А значит, предполагаемое время, затрачиваемое на сканирование вперед на каждом уровне /, составит 0(1). Поскольку Sс большой степенью вероятности может иметь O(log п) уровней, поиск в S может занять предположительно 0(log п) времени. С помощью подобного анализа можно доказать, что предполагаемое время выполнения ввода и удаления также составит 0(log п)[21].

И наконец, проанализируем требования к памяти. Как уже отмечалось, предполагаемое количество объектов на уровне / составляет я/2/, отсюда предполагаемое общее количество объектов в списке S соответствует

Следовательно, требуемый объем памяти предположительно составит 0(п). В^табл. 8.4 приведены данные выполнения операций словаря, реализованного skip-списком.

Операция

Время

size, isEmpty keys, elements

findElement, insertltem, removeElement findAHElements, removeAllElements

0(1) 0(n)

0(log n) (ожидаемое) 0(log n + s) (ожидаемое)

Таблица 8.4. Производительность словаря, реализованного с помощью skip-списка. Количество объектов словаря в момент выполнения операции обозначено п, размер возвращаемого ‘операциями findAHElements и removeAllElements итератора — 5. Предполагаемое требование к объему памяти есть 0(п)

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии