Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.)

Томас Кормен ЧарльзЛейзерсон Рональд Ривест Клиффорд Штайн АЛГОРИТМЫ ПОСТРОЕНИЕ И АНАЛИЗ ВТОРОЕ ИЗДАНИЕ Москва Санкт-Петербург ° Киев 2005 ББК 32.973.26-018.2.75 В24 УДК 681.3.07 Издательский дом "Вильямс" Зав. редакцией С.Н. Тригуб Перевод с английского канд. техн. наук ИВ. Красикова, НА.

Ореховой, В.Н. Романова Под редакцией канд. техн. наук И.В. Красикова По общим вопросам обращайтесь в Издательский дом "Вильямс" по адресу: )пГо1шъч111ашарцЫ)айпй.сот, )зггр://нпвтчлч11!1ашврцЫ)а)з!пй.сот 1154!9,Москва, а/я 783; 03150, Киев, а/я 152 Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. В24 Алгоритмы: построение и анализ, 2-е издание.: Пер. с англ.

— М.: Издательский дом "Вильямс", 2005. — 1296 с.: ил. — Парал. тнт. англ. 1БВ)ч) 5-8459-0857-4 (рус.) Фундаментальный труд известных специалистов в области кибернетики достоин занять место на полке любого человека, чья деятельность так или иначе связана с информатикой и алгоритмами. Для профессионала эта книга может служить настольным справочником, для преподавателя — пособием для подготовки к лекциям и источником интересных нетривиальных задач, для студентов и аспирантов— отличным учебником.

Каждый может найти в ней именно тот материал, который касается интересующей его темы, и изложенный именно с тем уровнем сложности и строгости, который требуется читателю. Описание алгоритмов на естественном языке дополняется псевдокодом, который позволяет любому имеющему хотя бы начальные знания и опыт программирования, реализовать алгоритм на используемом им языке программирования. Строгий математический анализ и обилие теорем сопровождаются большим количеством иллюстраций, элементарными рассуждениями и простыми приближенными оценками.

Широта охвата материала и степень строгости его изложения дают основания считать эту книгу одной из лучших книг, посвященных разработке и анализу алгоритмов. ББК 32.973.26-018.2.75 Ос Издательский дом "Вильямс", 2005 Ос М!Т Ргем, 2002 !5ВН 5-$459-0857-4 (рус.) !ЗВ)Ч 0-07 — 0 ! 3151- ! !англ.) Все названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм. Никакая часть настоящего издания нн в каких целях не может быть воспроизведена в какой бы то нн было форме н какими бы то нн было срсдствамн, буль то электронные нлн механические, включая фотокопирование н запись на магнитный носитель, если на это нет письменного разрешения издательства М!Т Ргем.

ОГЛАВЛЕНИЕ Введение Часть 1. Основы Глава 1. Роль алгоритмов в вычислениях Глава 2. Приступаем к изучению Глава 3. Рост функций Глава 4. Рекуррентные соотношения Глава 5. Вероятностный анализ и рандомизированные алгоритмы Часть 11. Сортировка и порядковая статистика Глава 6. Пирамидальная сортировка Глава 7. Быстрая сортировка Глава 8. Сортировка за линейное время Глава 9. Медианы и порядковые статистики Часть Ш. Структуры данных Глава 10.

Элементарные структуры данных Глава 11. Хеш-таблицы Глава 12. Бинарные деревья поиска Глава 13. Красно-черные деревья Глава 14. Расширение структур данных Часть 1У. Усовершенствованные методы разработки и анализа Глава 15. Динамическое программирование Глава 16. Жадные алгоритмы Глава 17. Амортизационный анализ Часть У. Сложные структуры данных Глава 18. В-деревья Глава 19. Биномиальные пирамиды 30 43 46 57 87 109 140 173 178 198 220 240 255 260 282 316 336 365 383 386 442 482 511 515 537 Оглавление Глава 20. Фибоначчиевы пирамиды Глава 21. Структуры данных для непересекающихся множеств Часть Ч1. Алгоритмы для работы с графами Глава 22. Элементарные алгоритмы для работы с графами Глава 23. Минимальные остовные деревья Глава 24. Кратчайшие пути из одной вершины Глава 25.

Кратчайшие пути между всеми парами вершин Глава 26. Задача о максимальном потоке Часть Ч11. Избранные темы Глава 27. Сортирующие сети Глава 28. Работа с матрицами Глава 29. Линейное программирование Глава 30. Полиномы и быстрое преобразование Фурье Глава 31. Теоретико-числовые алгоритмы Глава 32. Поиск подстрок Глава 33. Вычислительная геометрия Глава 34. ХР-полнота Глава 35. Приближенные алгоритмы Часть М11. Приложения: математические основы Приложение А. Ряды Приложение Б. Множества и прочие художества Приложение В. Комбинаторика и теория вероятности Библиография Предметный указатель 558 581 607 609 644 663 708 734 795 799 823 869 926 954 1017 1047 1085 1151 1189 1191 1202 1226 1257 1277 СОДЕРЖАНИЕ Введение 30 Часть 1. Основы Введение 43 44 Глава 1.

Роль алгоритмов в вычислениях 1. 1 Алгоритмы Какие задачи решаются с помощью алгоритмов? Структуры данных Методические указания Сложные задачи Упражнения 1.2 Алгоритмы как технология Эффективность Алгоритмы и другие технологии Упражнения Задачи Заключительные замечания Глава 2. Приступаем к изучению 2.1 Сортировка вставкой Инварианты цикла и корректность сортировки вставкой Соглашения, принятые прн составлении псевдокода Упражнения 2.2 Анализ алгоритмов Анализ алгоритма, работающего по методу вставок 46 46 47 50 50 51 52 52 52 54 55 55 56 57 57 59 61 63 64 66 Содержание Наихудшее и среднее время работы Порядок возрастания Упражнения 2.3 Разработка алгоритмов 2.3.1 Метод декомпозиции 2.3.2 Анализ алгоритмов, основанных на принципе "разделяй и властвуй" Анализ алгоритма сортировки слиянием Упражнения Задачи Заключительные замечания Г1зава 3.

Рост функций 3.1 Асимптотические обозначения 9-обозначения О-обозначения П-обозначения Асимптогические обозначения в уравнениях и неравенствах о-обозначения ы-обозначения Сравнение функций Упражнения 3.2 Стандартные обозначения и часто встречающиеся функции Монотонность Округление в большую и меньшую сторону Модульная арифметика Полиномы Показательные функции Логарифмы Факториал ы Функциональная итерация Итерированная логарифмическая функция Числа Фибоначчи Упражнения Задачи Заключительные замечания Глава 4.

Рекуррентные соотношения Технические детали 4.1 Метод подстановки Как угадать решение 69 70 71 71 72 78 78 81 83 86 87 88 88 91 92 93 94 95 96 97 98 98 98 98 99 99 100 102 102 103 103 104 105 108 109 110 111 112 Содержание Тонкие нюансы Остерегайтесь ошибок Замена переменных Упражнения 4.2 Метод деревьев рекурсии Упражнения 4.3 Основной метод Основная теорема Использование основного метода Упражнения * 4.4 Доказательство основной теоремы 4.4.1 Доказательство теоремы для точных степеней 4.4.2 Учет округления чисел Упражнения Задачи Заключительные замечания Глава 5. Вероятностный анализ и рандомизированные алгоритмы 5.1 Задача о найме сотрудника Анализ наихудшего случая Вероятностный анализ Рандомизированные алгоритмы Упражнения 5.2 Индикаторная случайная величина Анализ задачи о найме сотрудника с помощью индикаторных случайных величин Упражнения 5.3 Рандомизированные алгоритмы Массивы, полученные в результате случайной перестановки Упражнения * 5.4 Вероятностный анализ и дальнейшее применение индикаторных случайных величин 5.4.1 Парадокс дней рождения Анализ с помощью индикаторных случайных величин 5.4.2 Шары и урны 5.4.3 Последовательности выпадения орлов 5.4.4 Задача о найме сотрудника в оперативном режиме Упражнения Задачи Заключительные замечания 113 114 114 115 115 120 121 121 122 123 124 125 130 133 133 138 140 140 142 142 143 144 144 146 148 149 151 155 156 157 158 160 161 165 167 168 171 10 Содержание Часть 11.

Сортировка и порядковая статистика Введение Глава б. Пирамидальная сортировка 6.1 Пирамиды Упражнения 6.2 Поддержка свойства пирамиды Упражнения 6.3 Создание пирамиды Упражнения 6.4 Алгоритм пирамидальной сортировки Упражнения 6.5 Очереди с приоритетами Упражнения Задачи Заключительные замечания Глава 7. Быстрая сортировка 7.1 Описание быстрой сортировки Разбиение массива Упражнения 7.2 Производительность быстрой сортировки Наихудшее разбиение Наилучшее разбиение Сбалансированное разбиение Интуитивные рассуждения для среднего случая Упражнения 7.3 Рандомизированная версия быстрой сортировки Упражнения 7.4 Анализ быстрой сортировки 7.4.1 Анализ в наихудшем случае 7.4.2 Математическое ожидание времени работы Время работы и сравнения Упражнения Задачи Заключительные замечания Глава 8.

Сортировка за линейное время 8.1 Нижние оценки алгоритмов сортировки Модель дерева решений Нижняя оценка для наихудшего случая Упражнения 173 174 178 179 181 182 184 184 187 187 188 190 193 194 196 198 199 199 203 203 203 204 204 205 207 208 209 209 209 210 210 213 214 219 220 221 221 222 223 Содержание 8.2 Сортировка подсчетом Упражнения 8.3 Поразрядная сортировка Упражнения 8.4 Карманная сортировка Упражнения Задачи Заключительные замечания 224 226 226 230 230 234 234 238 240 241 241 242 243 247 247 250 252 254 Часть П1.

Структуры данных Введение 255 256 нескольких массивов одного массива Глава 9. Медианы и порядковые статистики 9.1 Минимум н максимум Одновременный поиск минимума и максимума Упражнения 9.2 Выбор в течение линейного ожидаемого времени Упражнения 9.3 Алгоритм выбора с линейным временем работы в наихудшем случае Упражнения Задачи Заключительные замечания 11зава 10. Элементарные структуры данных 10.1 Стеки и очереди Стеки Очереди Упражнения 10.2 Связанные списки Поиск в связанном списке Вставка в связанный список Удаление из связанного списка Ограничители Упражнения 10.3 Реализация указателей и объектов Представление объектов с помощью Представление объектов с помощью Выделение и освобождение памяти Упражнения 10.4 Представление корневых деревьев Бинарные деревья 260 260 260 262 263 264 265 265 266 266 268 269 269 270 271 273 274 274 12 Содержание Корневые деревья с произвольным ветвлением Другие представления деревьев Упражнения Задачи Заключительные замечания Глава 11.

Хеш-таблицы 11.1 Таблицы с прямой адресацией Упражнения 11.2 Хеш-таблицы Разрешение коллизий при помощи цепочек Анализ хеширования с цепочками Упражнения 11.3 Хеш-функции Чем определяется качество хеш-функции Интерпретация ключей как целых неотрицательных чисел 11.3.1 Метод деления 11.3.2 Метод умножения * 11.3.3 Универсальное хеширование Построение универсального множества хеш-функций Упражнения 11.4 Открытая адресация Линейное исследование Квадратичное исследование Двойное хеширование Анализ хеширования с открытой адресацией Упражнения * 11.5 Идеальное хеширование Упражнения Задачи Заключительные замечания Глава 12. Бинарные деревья поиска 12.1 Что такое бинарное дерево поиска Упражнения 12.2 Работа с бинарным деревом поиска Поиск Поиск минимума и максимума Предшествующий и последующий элементы Упражнения 12.3 Вставка и удаление Вставка 275 276 276 277 280 282 283 284 285 286 288 290 291 291 292 292 293 294 297 298 300 302 303 303 305 307 308 312 313 315 316 317 319 319 320 321 321 323 324 324 13 Содержание 325 327 328 331 332 335 383 384 386 387 389 391 Удаление Упражнения * 12.4 Случайное построение бинарных деревьев поиска Упражнения Задачи Заключительные замечания Глава 13.