1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 25
Текст из файла (страница 25)
целыми регистрами. Тогда время считывания входных данных есть йлн. Если отношение ЬП ограничено постоянной, то тривиальная нижняя оценка сложности сортировки имеет вид сл, где с — некоторая постоянная. Воцрос о достижимости (по порядку) таких нижних оценок открыт.— Прим. перев. 12Ь ЗАМЕЧАИИ5! !Нз ЛИТЕРАТУРЕ Замечания ле литературе Книга Кнута [1973а! представляет собой энцнилопедическое руководство по методам сортировки.
Сортдеревом берет начало от Уильямса (1964]; некоторые улучшения сделаны Флойдом [1964! Быстрсорт ввел Хоор (1962]. Улучшения Быстрсорт по схеме упр. 3.28 предложены Синглтоном [1969[, а также Фрейзером, Мак-Келларам [!970], Алгоритм 3.6 для нахождения порядковой статистики, линейный в худшем случае, изложен в работе Блюма, Флойда, Пратта, Ривеста, Тарьяна [1972]. Хейдиан, Соубел [1969! и Пратт, Яо [1973] исследуют число сравнений, необходимое для нахождения некоторых порядковых статистик. Результат упр. 3.21 получен Кнслицыным [1964[. Упр.
3.22, 3.23 и 3.29 взяты из работы Флойда, Ривеста (1973], где также приведена более сильная нижняя оценка, чем та, что указана в упр. 3.22. Упр. 3.19, 3.20 и некоторые обобщения обсуждаются в работах Гейла, Карпа [1970! и Лю [1972[. Интересное приложение сортировки к нахождению выпуклой оболочки множества точек на плоскости дано Грэхемом [1972]. Стабильнан сортировка рассмотрена Хорватом [1974]. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, 4 КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ Хороший подход к разработке эффективного алгоритма для данной задачи — изучить ее сущность.
Часто задачу можно сформулировать на языке основных математических понятий, таких, как множество, и тогда алгоритм для нее можно изложить в терминах основных операций над основными объектами. Преимущество такой точки зрения в том, что можно проанализировать несколько различных структур данных и выбрать из них ту, которая лучше всего подходит для задачи в целом. Таким образом, разработка хорошей структуры данных идет рука об руку с разработкой хорошего алгоритма.
В настоящей главе изучаются семь основных операций над множествами, типичных для многих задач информационного поиска. Мы приведем разнообразные структуры данных для представления множеств и рассмотрим пригодность каждой из них в ситуациях, когда выполняется та или иная последовательность операций различных типов. 4.1. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Будем рассматривать следующие основные операции над множествами. Ь ПРИНАДЛЕЖАТЬ(а, 5). Устанавливает принадлежность а множеству 5; если а Е 5, печатается "да"; в противном случае— "иет." 2. ВСТАВИТЬ(а, 5).
Заменяет 5 на 5 ц(а). 3. УДАЛИТЬ(о, 5). Заменяет 5 на 5 — (а). 4. ОБЪЕДИНИТЬ(5„5„5,). Строит множество 5,=5, ц5,. Мы будем предполагать, что в тех случаях, когда применяется эта операция, множества 5, и 5, не пересекаются; это делается для того, чтобы избежать необходимости удалять повторяющиеся экземпляры одного и того же элемента в 5, ц 5,.
5. НАЙТИ (а). Печатает имя того множества, которому в данный ол. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ момент принадлежит а. Если а принадлежит более чем одному множеству, то операция не определена. 6. РАСЦЕПИТЬ(а, Я). Здесь предполагается, что множество Я наделено линейным порядком (. Операция разбивает Я на два множества Зк=(Ь|(м=а н Ь ЕЯ) и Яо=(Ь!Ь)а н Ь ЕЯ. 7. М(Ь) (Я). Выдает наименьший (относительно «) элемент множества 5. Многие задачи, встречающиеся на практике, можно свести к одной или нескольким подзадачам, таким, что каждую подзадачу можно абстрактно сформулировать как последовательность основных команд, которые следует выполнить на некоторой базе данных (универсальном множестве элементов).
В данной главе мы будем изучать последовательности О команд, каждая нз которых является операцией одного из перечисленных выше семи типов. Например, выполнение последовательностей, состоящих из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ, составляет существенную часть многих задач поиска.
Структура данных, которую можно использовать для выполнения последовательности этих операций, будет называться словарем. В настоящей главе рассматривается несколько структур данных (такие, как таблицы расстановки, деревья двоичного поиска н 2-3-деревья), которые могут быть словарями. Здесь возникает много интересных вопросов. Нас будет интересовать главным образом временная сложность выполнения операций в О, т. е.
время как функция длины последовательности О и размера базы данных. Мы исследуем временную сложность в худшем случае и в среднем, а также сложность выполнения о в префиксном и свободном режимах. Определение. Выполнение последовательности операций О в префиксном режиме требует, чтобы операции в и выполнялись в порядке слева направо, причем (-я операция в О должна выполняться без просмотра какой бы то ни было последующей операции. При свободном режиме разрешается просматривать всю последовательность а в любой момент времени. Очевидно, что всякий префиксный алгоритм (т. е. работающий в префиксном режиме) может работать как свободный (т.
е. в свободном режиме), но обратное верно не всегда. Мы увидим ситуации, когда свободный алгоритм работает быстрее любого из известных префнксных. Однако во многих приложениях приходится рассматривать только префиксные алгоритмы. Пусть дана последовательность операций, которую надлежит выполнить. Основной вопрос: какую структуру данных использовать для представления универсальной базы данныхУ Часто задача будет требовать осторожного взвешивания всех за и против каждого о А.Ако, Д:и. Хопкрккьк, Дм. Уоьпоп ГЛ.
А СТРУКТУРЫ ДАИНЪ|Х ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ конкретного выбора. В типичной ситуации последовательность будет состоять из нескольких операций, подлежащих многократному выполнению, часто в неизвестном порядке. Может оказаться несколько структур данных, каждая из которых позволяет одну операцию выполнять легко, а другие — с большим трудом. Во многих случаях лучшим решением будет компромисс. Часто мы будем использовать структуру, которая не делает максимально легким выполнение ни одной из операций, но позволяет выполнить всю работу лучше, чем прн любом очевидном подходе. Приведем пример, показывающий, как сформулировать задачу о построении остовного дерева для графа в терминах последователь.
ности операций над множествами. Определение. Пусть О= (У, Е) — неориентированный граф. Остовным деревом Я (для) графа 6 называется неориентированное дерево вида (У, Т), Т~Е. Осяоаным лесом (для) графа О называется множествонеориентированныхдеревьеввида ((У„Т|,), (У„Т,), ... ..., (УА, ТА)), в котором У| образуют разбиение множества') У, а каждое множество Т, является (возможно, пустым) подмножеством в Е.
Функцией стоимости для графа 6= (У, Е) называется отображение с из Е в множество вещественных чисел. Стоимостью подграфа б'= (У', Е') графа б считается с(6')= Х с(е). вв Пример 4.1. Рассмотрим алгоритм, приведенный на рис. 4.1, для нахождения для данного графа 6=(У, Е) остовного дерева 3=(У, Т) наименьшей стоимости. Зтот алгоритм построения остов- ного дерева наименьшей стоимости подробно обсуждается в разд.
5,1, а его применение проиллюстрировано в примере 5.1. В алгоритме на рис. 4.1 участвуют три множества Е, Т и УЕ. Множество Е содержит ребра данного графа О, а Т используется для сбора ребер окончательного остовного дерева, Работа алгоритма состоит в преобразовании остовного леса для О в единое остовиое дерево. Множество УЯ содержит множества узлов, входящих в деревья этого остовного леса. Вначале УЯ содержит каждый узел графа 6 в виде одноэлементного множества. Можно считать этот алгоритм последовательностью операций с тремя множествами Е, Т и УЕ. В строке 1 формируется начальное значение для Т, в строках 2 и 3 — для УЯ (элементы множества УЕ сами являются множествами).
В строке 3 добавляются исходные одноэлементные множества к УЕ. Строка 4, управляющая основным циклом алгоритма, предполагает наличие счетчика множеств, составляющих УЕ. В строке 7 выясняется, соединяет ли ребро (о, и|) два остовных дерева в остовном лесу. Если да, то в строке 8 этн два В то У|ЦУв(!...(!У =У я У|ПУ7 |3| е м~й АЬ ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Ьея!п т-а; 2.
$г5 — И; 3. 4ог каждый узел ОЕ)г с(о добавить одноэлемеитное множество (о) к )г5; 4. тч)т!(е !(г5!)) 1 до Ьеи(п 6. выбрать из Е ребро (и, тв) наименьшей стоимости; 6, удалить (О, в) из Е; 7. )! и и иг принадлежат разным множествам ягт и (!га из Р5 1)теп Ьея)п 8. заменить )(гт и Яг", в (т5 на )!т, В Яр;, 9. добавить (О, тв) к 7' епс! епд епс! Рис. 4Л. Алгоритм для нахождения остовного дерева наименьшей стоимости.
дерева сливаются, а в строке 9 ребро (о, ги) добавляется к окончательному остовному дереву. Строка 7 предполагает, что мы можем найти имя того множества в (г5, которое содержит конкретный узел. (Вид имен, действительно используемых для множеств в тг5, не важен, так что можно употреблять произвольные имена.) По существу, строка 7 предполагает, что мы можем эффективно выполнить основную операцию НАЙТИ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
