Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 59
Текст из файла (страница 59)
для всех с = 1, 2,...,и, таких, что пехс[с] ф Х1Ь, выполняется соотношение Йеу[с] < Йеу[пехс[с]]. Предполагается также, что имеется переменная Ь, в которой хранится индекс первого элемента списка. Покажите, что при данных предположениях математическое ожидание времени поиска с помощью приведенного ниже рандомизированного алгоритма равно 0[~ссй). СОмРАст-1.!зт-БеАксн(Ь, и, Й) 1 с=А 2 сгЬ11е с ф Н1Е и Йеу[г] < Й 3 2 = 1сАхЭОм(1,п) 4 !Г Йеу[с] < Йеу[2] и Йеу[1] < Й 5 с=2 б И'Йеу[с] == Й 7 геФнгп с' 8 с = пех2[с] 9 ы с' == 1ссе или Йеу[с] > Й 10 гегнгп сс1е 11 е1яе ге1игп с Если в представленной выше процедуре опустить строки 3-7, получится обычный алгоритм, предназначенный для поиска в отсортированном связанном списке, в котором индекс с пробегает по очереди по всем элементам в списке.
Поиск прекращается в тот момент, когда происходит "обрыв" индекса с в конце списка или когда Йеу[с] > Й. В последнем случае, если выполняется соотношение Йеу[с] = Й, понятно, что ключ Й найден. Если же Йеу[с] > Й, то ключ Й в списке отсутствует, и поэтому следует прекратить поиск. В строках 3-7 предпринимается попытка перейти к случайно выбранной ячейке 2'. Такой переход дает преимущества, если величина Йеу[2] больше величины Йеу[с], но не превышает значения Й.
В этом случае индекс 2 соответствует элементу списка„к которому рано или поздно был бы осуществлен доступ при обычном поиске. Поскольку список компактен, любой индекс 2 в интервале от 1 до и отвечает некоторому объекту списка и не может быть пустым местом из списка свободных позиций. Вместо производительности процедуры СОМРАст-1,1эт-БеАксн мы проанализируем связанный с ним алгоритм СОМРАст-1лзт-БКАксн', в котором содержатся два отдельных цикла. В этом алгоритме используется дополнительный параметр 1, определяющий верхнюю границу количества итераций в первом цикле. Раз Глава!ц Элечентарные структуры данные СомРАст-Ь!кт-БеАксн (Ь, и, 1с, 1) 1 1=Ь 2 Гогу = 11ог 3 Р = КАНООМ(1, и) 4 1Г (веу[г] < 1сеу[Р] и иеу[Р] < и 5 Г=Р 6 1Г (ееу[г] == и 7 гегнгп Г 8 иЫ1е в ф нгс и Ееу[1] < Е 9 1 = иехг[1] 1О 1ГГ == Н!Ь или 1ееу[1] > /с 11 гегнгп нн.
12 е1ае гетигп 1 Для простоты сравнения алгоритмов СОМРАст-Ь1ет-БеАксн(Ь, и, и) и СОМРАст-Ь1зт-БеАксн'(Ь,и,й,г) будем считать, что последовательность целых чисел, которая возвращается вызовами КАноом(1, и), одна и та же для обоих алгоритмов. а Предположим, что в ходе работы цикла зг1111е в строках 2-8 процедуры СОМРАст-Ь!зт-БеАксн(Ь, и, к) выполняется Ф итераций. Докажите, что процедура СОМРАст-Ьгзт-БеАксн'(Ь, и, к,г) даст тот же ответ и что общее количество итераций в циклах Гог и иййе процедуры СОМРАст-Ь1ет-беАксн' не меньше Ь Пусть Хе — случайная величина, описывающая расстояние в связанном списке (т.е.
длину цепочки из указателей иехг) от элемента с индексом Г до искомого ключа Е после 1 итераций цикла Гог в строках 2-7 в вызове процедуры СОМРАСТ-Ь!ЯТ-БЕАКСН (Р, и, 1е, 1) й Докажите, что математическое ожидание времени работы процедуры СОМРАСТ-Ь!БТ-БеАксн (Р, и, ге,1) равно 0(1+ Е [Хе]). а Покажите, что Е [Хв] < 2," 1(1 — г/и)'. (Указание: воспользуйтесь уравнением (В.25).) а Покажите, что 2 ~ 11 г' < ив'1/(1+ 1). д. Докажите, что Е[Хв] < и/(1+1). а Покажите, что математическое ожидание времени работы процедуры СОМРАст-Ь1ет-БеАксн'(Ь, и, Ре, 1) равно 0(1+ и/1). ж Сделайте вывод о том, что математическое ожидание времени работы процедуры СОМРАст-Ь1ет-БеАксн равно О(,/и).
Часть Ш. Структуре~ даннык ВВ4 х Объясните, зачем в ходе анализа процедуры Сомрлст-1,!зт-Бкяксн понадобилось предположение о том, что все ключи различны. Покажите, что случайные переходы не обязательно приведут к сокращению асимптотического времени работы, если в списке содержатся ключи с одинаковыми значениями. Заключительные замечания Прекрасными справочными пособиями по элементарным структурам данных являются книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана (1ЛЬпап) [6] и Кнута (Кли!Ь) [208]с.
Описание базовых структур данных и их реализации в конкретных языках программирования можно также найти во многих других учебниках. В качестве примера можно привести книги Гудрича (ОоодпсЬ) и Тамазин (Таупайгйа) [146], Мейна (Мага) [240], Шаффера (БЬайег) [309] и Вейса (%е!00) [350-352]. В книге Гонне (Поппе!) [144] приведены экспериментальные данные, описывающие производительность операций над многими структурами данных.
Начало использования стеков и очередей в информатике в качестве структур данных по сей день остается недостаточно ясным. Вопрос усложняется тем, что соответствующие понятия существовали в математике и применялись на практике при выполнении деловых расчетов на бумаге еще до появления первых цифровых вычислительных машин. В своей книге [208] Кнут приводит относящиеся к 1947 году цитаты А.М. Тьюринга (А.М. Тпппй), в которых идет речь о разработке стеков для компоновки подпрограмм.
По-видимому, структуры данных, основанные на применении указателей, также являются "народным" изобретением. Согласно Кнуту указатели, скорее всего, использовались еще на первых компьютерах с памятью барабанного типа. В языке программирования А-1, разработанном Г.М. Хоппером (О.М. Норрег) в 1951 году, алгебраические формулы представляются в виде бинарных деревьев. Кнут считает, что указатели получили признание и широкое распространение благодаря языку программирования 1РЫ1, разработанному в 1956 году А. Ньювеллом (А.
)н)елае!!), Д.К. Шоу (1.С. БЬаяр) и Г.А. Саймоном (Н.А. Бппол). В язык 1Р1.- П1, разработанный в 1957 году теми же авторами, операции со стеком включены явным образом. Имеется русский перевод. Д. Кнут. Искусство лроераччнрования, т. Ь Основные авеорннсчы, 3-е нвд.— Мс И.Д. "Вильямс", 2000. Глава 11. Хеширование и хеш-таблицы Для многих приложений достаточно динамических множеств, поддерживающих только стандартные словарные операции 1мзпкт, Бялксн и Вн.кто. Например, компилятор, транслирующий язык программирования, поддерживает таблицу символов, в которой ключами элементов являются произвольные символьные строки, соответствующие идентификаторам в языке. Хеш-таблица представляет собой эффективную структуру данных для реализации словарей.
Хотя на поиск элемента в хеш-таблице может в наихудшем случае потребоваться столько же времени, сколько на поиск в связанном списке, а именно — Й(п), на практике хеширование исключительно эффективно. При вполне обоснованных допущениях среднее время поиска элемента в хеш-таблице составляет 0(1). Хеш-таблица обобщает обычный массив. Возможность прямой индексации элементов обычного массива обеспечивает доступ к произвольной позиции в массиве за время 0(1).
Более подробно прямая индексация рассматривается в разделе !1.1; она применима, если мы в состоянии выделить массив такого размера, какого достаточно для того, чтобы для каждого возможного значения ключа имелась своя ячейка. Если количество реально хранящихся в массиве ключей малб по сравнению с количеством возможных значений ключей, эффективной альтернативой массива с прямой индексацией становится хеш-таблица, которая обычно использует массив, размер которого пропорционален количеству реально хранящихся в нем ключей. Вместо непосредственного использования ключа в качестве индекса массива индекс вычисляется по значению ключа. В разделе 11.2 представлены основные идеи хеширования, в первую очередь направленные на разрешение коллизий (когда несколько ключей отображается в один и тот же индекс массива) с помошью цепочек.
В разделе 11.3 описывается, каким образом на основе значений ключей могут быть вычислены индексы массива. Здесь будет рассмотрено и проанализировано несколько вариантов хеш-функций. В разделе 11.4 вы познакомитесь с методом открытой адресации, представляющим собой еще один способ разрешения коллизий. Главный вывод, который следует из всего изложенного материала, — хеширование представляет собой исключительно эффективную и практичную технологию: в среднем все базовые словарные операции выполняются за время 0(1). В разделе 11.5 будет дано пояснение, каким образом "идеальное хеширование" может поддерживать наихудшее время поиска 0(1) в случае ис- БВб Часть 1П.
Струкввры оанльи пользования статического множества хранящихся ключей (т.е. когда множество ключей, будучи сохраненным, более не изменяется). 11.1. Таблицы с прямой адресацией Прямая адресация представляет собой простую технологию, которая хорошо работает для небольших совокупностей ключей. Предположим, что приложению требуется динамическое множество, каждый элемент которого имеет ключ из совокупности У = (О, 1,..., т — Ц, где т не слишком велико. Кроме того, предполагается, что никакие два злемента не имеют одинаювых ключей. Для представления динамического множества мы используем массив, или таблицу с прямой адресацией, который обозначим как Т10.. т — Ц, каждая позиция (роайюп), или ячейка, слог (а1ог) которого соответствует ключу из совокупности ключей У.
На рис. 11.1 проиллюстрирован данный подход. Ячейка )с указывает на злемент множества с ключом lс. Если множество не содеряснт элемента с ключом lс, то Т(к'1 = Нп.. Реализация словарных операций тривиальна. 111кест-АппкеББ-оеАксн (Т, )с) 1 ге1игн Т()с'1 (з1кест-АппкеББ-(хзект(Т,х) 1 Т~х.йеу~ = х Р1кест-АппкеББ-1зееете(Т, х) 1 Т~х.ансер'1 = хп. каждая из зтих операций выполняется за время 0(1). о Сопутствуюшие Ключ данные / Рис. 11.1. Реализация динвмическото мншкества с использованием таблицы с прямой адресацией Т. Кюкдый ключ в совокупности и = (О, 1,..., 9) соответствует индексу в таблице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
