Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 56
Текст из файла (страница 56)
Аналогично, если бы в пирамиде поддерживались операции Млх~мгзм н Ехтнлст Мдхгмом, ее можно было бн назвать объединяемой невозрастающей пирамидой (гпегбаЫе так-ьеар). Глава 10. Элементарные структуры данных Если в представленной выше процедуре опустить строки 3-7, получится обычный алгоритм, предназначенный для поиска в отсортированном связанном списке, в котором индекс 1 пробегает по всем элементам в списке. Поиск прекращается в тот момент, когда происходит "обрыв" индекса 1 в конце списка или когда Ееу [1] > й. В последнем случае, если выполняется соотношение Еед [1] = 1с, то понятно, что ключ 1с найден. Если же Йеу [1] > Й, то ключ Й в списке отсугствует и поэтому следует прекратить поиск. В строках 3-7 предпринимается попытка перейти к случайно выбранной ячейке 2.
Такой переход дает преимущества, если величина йеу [7] больше величины йеу [1], но не превышает значения й. В этом случае индекс з соответствует элементу списка, к которому рано или поздно был бы осуществлен доступ при обычном поиске. Поскольку список компактен, любой индекс 2 в интервале от 1 до п отвечает некоторому объекту списка и не может быть пустым местом из списка свободных позиций. Вместо анализа производительности процедуры СомРАст Ь!эт ЗеАксн мы проанализируем связанный с ним алгоритм СомРАст 1лзт ЯеАксн', в котором содержатся два отдельных цикла. В этом алгоритме используется дополнительный параметр 1, определяющий верхнюю границу количества итераций в первом цикле: СОМРАСТ ЬБТ БЕАКСН (Х, и, Й, 1) 1 1 — Ьеад[Ь] 2 аког д ~ — 1 го 1 3 йо 2 КАмэОм(1, п) 4 Рб Йеу[г] < /сеу[2] и Йеу[2] < к 5 1'пеп г' 6 1Г йеу[г] = Й 7 гпеп ге1пгп 1 8 нй11е 1 ~ м1 и Йеу[1] < Й 9 йо 1 — пех1[1] 1О 111 = ме или йеу[г] > lс 11 1пеп гегнгп ип.
12 е1ае ге1пгп 1 Для простоты сравнения алгоритмов СомРАст 1лзт БеАксн(Ь,п, Е) и СомРАст валат БеАксн'(Ь,п,й,1) будем считать, что последовательность случайных чисел, которая возвращается процедурой КАмэОм(1, п), одна и та же для обоих алгоритмов. а) Предположим, что в ходе работы цикла и Ы1е в строках 2-8 процедуры СомРАст 1.Бт БеАесн(Ь, и, Й), выполняется 1 итераций. До- Часть й!. Структуры данных 280 кажите, что процедура Сомглст 1лзт Белксн'(Т„п, )с,1) даст тот же ответ, и что общее количество итераций в циклах 1ог и иЫ1е этой процедуры не меньше 1. Пусть при работе процедуры Сомглст 1.!зт Бвлксн'(Ь, и, Й, 1) Х~ — случайная величина, описывающая расстояние в связанном списке (т.е.
длину цепочки из указателей пез1) от элемента с индексом г' до искомого ключа )с после 1 итераций цикла 1ог в строках 2-7. б) Докажите, что математическое ожидание времени работы процедуры СомРлст 1.!Бт Белксн (Ь, п, й, г) равно О (г+ Е [Х~]). в) Покажите, что Е[Х~] < 2"," „(1 — г/и) . (Указание: воспользуйтесь уравнением (В.24)).
г) Покажите, что 2 „, г < п~+1/(1+1). д) Докажите, что Е [Х,] < и/(Ф + 1). е) Покажите, что математическое ожидание времени работы процедуры СомРлст 1!зт Бвлксн'(Х,, п,)с,1) равно О(1+п/1). ж) Сделайте вывод о том, что математическое ожидание времени работы процедуры Сомклст 1лзт Бвлксн равно О (~/й). з) Объясните, зачем при анализе процедуры Сомглст 1лзт БРлксн понадобилось предположение о том, что все ключи различны. Покажите, что случайные переходы не обязательно приведут к сокращению асимптотического времени работы„если в списке содержатся ключи с одинаковыми значениями.
Заключительные замечания Прекрасными справочными пособиями по элементарным структурам данных являются книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана (11!!шап) (6] и Кнута (Кпи1п) [182]. Описание базовых структур данных и их реализации в конкретных языках программирования можно также найти во многих других учебниках. В качестве примера можно привести книги Гудрича (Оообпсп) и Тамазии (Ташазз!а) (128], Мейна (Маш) [209], Шаффера (Бпайег) (273] и Вейса (%е1зз) [310, 312, 313]. В книге Гоннета (Ооппе1) [126] приведены экспериментальные данные, описывающие производительность операций над многими структурами данных.
Начало использования стеков и очередей в информатике в качестве структур данных по сей день остается недостаточно ясным. Вопрос усложняется тем, что соответствующие понятия существовали в математике и применялись на практике при выполнении деловых расчетов на бумаге еще до появления первых цифровых вычислительных машин. В своей книге (182] Кнут приводит относящиеся Глава 10. Элементарные структуры данных 281 к 1947 году цитаты А. Тьюринга (А.М. Типпй), в которых идет речь о разработке стеков для компоновки подпрограмм. По-видимому, структуры данных, основанные на применении указателей, также являются "народным" изобретением.
Согласно Кнуту, указатели, скорее всего, использовались еще на первых компьютерах с памятью барабанного типа. В языке программирования А-1, разработанном Хоппером (О.М. Норрег) в 1951 году, алгебраические формулы представляются в виде бинарных деревьев. Кнут считает, что указатели получили признание и широкое распространение благодаря языку программирования 1Р1.-11, разработанному в 195б году Ньюэлом (А. Нетче11), Шоу ().С. Блатч) и Симоном (Н.А. Зппоп). В язык 1Р1.-П1, разработанный в 1957 году теми же авторами, операции со стеком включены явным образом. ГЛАВА 11 Хе ш-таблицы Для многих приложений достаточны динамические множества, поддерживающие только стандартные словарные операции вставки, поиска и удаления.
Например, компилятор языка программирования поддерживает таблицу символов, в которой ключами элементов являются произвольные символьные строки, соответствующие идентификаторам в языке. Хеш-таблица представляет собой эффективную структуру данных для реализации словарей. Хотя на поиск элемента в хеш-таблице может в наихудшем случае потребоваться столько же времени, что и в связанном списке, а именно 6 (и), на практике хеширование исключительно эффективно. При вполне обоснованных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет О (1). Хеш-таблица представляет собой обобщение обычного массива. Возможность прямой индексации элементов обычного массива обеспечивает доступ к произвольной позиции в массиве за время О (1).
Более подробно прямая индексация рассматривается в разделе 11.1; она применима, если мы в состоянии выделить массив размера, достаточного для того, чтобы для каждого возможного значения ключа имелась своя ячейка. Если количество реально хранящихся в массиве ключей малб по сравнению с количеством возможных значений ключей, эффективной альтернативой массива с прямой индексацией становится хеш-таблица, которая обычно использует массив с размером, пропорциональным количеству реально хранящихся в нем ключей.
Вместо непосредственного использования ключа в качестве индекса массива, индекс вычисляется по значению ключа. В разделе 11.2 представлены основные идеи хеширования, в первую очередь направленные на разрешение коллизий (когда несколько ключей отображается в один и тот же индекс массива) при помощи 283 Глава 11. Хеш-таблицы цепочек. В разделе 11.3 описывается, каким образом на основе значений ключей могут быть вычислены индексы массива.
Здесь будет рассмотрено и проанализировано несколько вариантов хеш-функций. В разделе 11.4 вы познакомитесь с методом открытой адресации, представляющим собой еще один способ разрешения коллизий. Главный вывод, который следует из всего изложенного материала: хеширование представляет собой исключительно эффективную и практичную технологию — в среднем все базовые словарные операции требуют только О [1) времени. В разделе 11.5 будет дано пояснение, каким образом "идеальное хеширование'* может поддерживать наихудшее время поиска О (1) в случае использования статического множества хранящихся ключей 1т.е. когда множество ключей, будучи сохраненным, более не изменяется). 11.1 Таблицы с прямой адресацией Прямая адресация представляет собой простейшую технологию, которая хорошо работает для небольших множеств ключей.
Предположим, что приложению требуется динамическое множество, каждый элемент которого имеет ключ из множества У = 10, 1,..., гп — Ц, где ги не слишком велико. Кроме того, предполагается, что никакие два элемента не имеют одинаковых ключей. Для представления динамического множества мы используем массив, или таблицу с прямой адресацией, который обозначим как Т (О..т — 1], каждая позиция, или ячейка 1роз1йоп, а1о1), которого соответствует ключу из пространства ключей У.
На рис. 11.! представлен данный подход. Ячейка к указывает на элемент множества с ключом к. Если множество не содержит элемента с ключом к, то Т [к] = Н11.. На рисунке каждый ключ из пространства У = 10, 1,..., 9) соответствует индексу таблицы. Множество реальных ключей К = 12, 3, 5, 8) определяет ячейки таблицы, которые содержат указатели на элементы.
Остальные ячейки 1закрашенные темным цветом) содержат значение н1ы Реализация словарных операций тривиальна: 13!кест Аппкезз 8еАксн1Т, /с) гегцгп Т[к] 13~кест Аппкезе 1нзект[Т,х) Т[пеу(х]] — х 131кест Аппкезз 1з~.ете[Т, х) Т[йер(х]] — нш Каждая из приведенных операций очень быстрая: время их работы равно О (1). В некоторых приложениях элементы динамического множества могут храниться непосредственно в таблице с прямой адресацией. То есть вместо хранения 284 Часть 1П.
Структуры данных Рис. 11.1. Реализация динамического множества с использованием таблицы с прямой адресацией ключей и сопутствующих данных элементов в объектах, внешних по отношению к таблице с прямой адресацией, а в таблице — указателей на эти объекты, этн объекты можно хранить непосредственно в ячейках таблицы (что тем самым приводит к экономии используемой памяти). Кроме того, зачастую хранение ключа не является необходимым условием, поскольку если мы знаем индекс объекта в таблице, мы тем самым знаем и его ключ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
