Грокаем алгоритмы 2-е издание
Год издания: 2024
Автор: Bhargava Aditya / Бхаргава Адитья
Переводчик: ООО «Прогресс книга»
Жанр или тематика: Алгоритмы в программировании
Издательство: «Питер»
ISBN: 978-5-4461-4172-2
Серия: Библиотека программиста
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Интерактивное оглавление: Да
Количество страниц: 352
Описание: Алгоритмы — это пошаговые инструкции решения задач, большинство из которых уже были
кем-то решены, протестированы и доказали свою эффективность. Второе издание «Грокаем алгоритмы» упрощает изучение, понимание и использование алгоритмов. В этой книге вы найдете простые
и внятные объяснения, более 400 забавных иллюстраций и десятки примеров. Ее чтение — лучший
способ раскрыть всю мощь алгоритмов и подготовиться к интервью по программированию. Глубоких
знаний математики не требуется!
Вы узнаете о главных алгоритмах, позволяющих ускорить работу программ, упростить код и решить
распространенные проблемы программирования. Начните с сортировки и поиска, а затем развивайте
свои навыки для решения сложных задач, таких как сжатие данных и искусственный интеллект.
Научитесь сравнивать эффективность различных алгоритмов.
Во втором издании даны новые, более подробные описания деревьев, NP-полные задачи, а код
примеров обновлен на Python 3.
Пора грокать алгоритмы по-новому!
Примеры страниц (скриншоты)
Оглавление
Оглавление
Отзывы о первом издании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
О книге . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Как работать с этой книгой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Для кого предназначена эта книга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Структура книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
О коде в книге . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Об авторе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
О научном редакторе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
От издательства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Глава 1. Знакомство с алгоритмами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Что вы узнаете об эффективности алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . 28
Что вы узнаете о решении задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Оглавление 7
Бинарный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Более эффективный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Время выполнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
«O-большое» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Время выполнения алгоритмов растет с разной скоростью . . . . . . . . . . 38
Наглядное представление «O-большое» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
«O-большое» определяет время выполнения в худшем случае . . . . . . 43
Типичные примеры «O-большого» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Задача о коммивояжере . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Глава 2. Сортировка выбором . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Как работает память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Массивы и связанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Связанные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Терминология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Упражнение............................................................. 57
Вставка в середину списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Удаление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Какая структура данных используется чаще: массивы или списки? . . . . 60
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Сортировка выбором . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Пример кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Глава 3. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Базовый случай и рекурсивный случай . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
8 Оглавление
Стек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Стек вызовов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Упражнение............................................................. 79
Стек вызовов с рекурсией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Упражнение............................................................. 84
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Глава 4. Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
«Разделяй и властвуй» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Снова об «O-большом» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Сортировка слиянием и быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . 104
Средний и худший случаи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Глава 5. Хеш-таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Примеры использования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Использование хеш-таблиц для поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Исключение дубликатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Использование хеш-таблицы как кэша . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Коллизии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Быстродействие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Коэффициент заполнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
Хорошая хеш-функция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Оглавление 9
Глава 6. Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Знакомство с графами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Что такое граф? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Поиск кратчайшего пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Реализация графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Реализация алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Время выполнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Глава 7. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Ваше первое дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Каталоги файлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Космическая одиссея: поиск в глубину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Правильное определение дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Бинарные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Код Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Глава 8. Сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Балансировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Деревья повышают скорость вставки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Короткие деревья работают быстрее ................................. 187
АВЛ-деревья: разновидность сбалансированных деревьев . . . . . . . . . . 191
Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
Как АВЛ-дерево узнает, что требуется поворот? . . . . . . . . . . . . . . . . . . . . 195
Косые деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
10 Оглавление
B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Какие преимущества есть у B-деревьев? . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Глава 9. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
Работа с алгоритмом Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Терминология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
История одного обмена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
Ребра с отрицательным весом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Упражнение........................................................... 237
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Глава 10. Жадные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Задача составления расписания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Задача о покрытии множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Приближенные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
Глава 11. Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . 253
И снова задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Простое решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
Задача о рюкзаке: вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Что произойдет при добавлении элемента? . . . . . . . . . . . . . . . . . . . . . . . . 264
Упражнение........................................................... 267
Что произойдет при изменении порядка строк? . . . . . . . . . . . . . . . . . . . 267
Можно ли заполнять таблицу по столбцам,
а не по строкам? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Что произойдет при добавлении меньшего элемента? . . . . . . . . . . . . . 268
Оглавление 11
Можно ли взять часть предмета? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Оптимизация туристического маршрута . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Взаимозависимые элементы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Может ли оказаться, что решение требует более
двух «подрюкзаков»? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Возможно ли, что при лучшем решении в рюкзаке остается
пустое место? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Упражнение........................................................... 273
Самая длинная общая подстрока . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Построение таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
Заполнение таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Самая длинная общая подпоследовательность . . . . . . . . . . . . . . . . . . . . 279
Самая длинная общая подпоследовательность — решение . . . . . . . 280
Упражнение........................................................... 282
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Глава 12. Алгоритм k ближайших соседей . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Апельсины и грейпфруты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
Построение рекомендательной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
Извлечение признаков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
Регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Выбор признаков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
Упражнение........................................................... 297
Знакомство с машинным обучением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
OCR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Построение спам-фильтра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Прогнозы на биржевых торгах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Тренировка модели МО: общий обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
12 Оглавление
Глава 13. Что дальше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Линейная регрессия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Инвертированные индексы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Преобразование Фурье . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
Параллельные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
map/reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Фильтры Блума и HyperLogLog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Фильтры Блума . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
HyperLogLog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
HTTPS и обмен ключами Диффи — Хеллмана . . . . . . . . . . . . . . . . . . . . . . . . . 312
Локально-чувствительное хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Минимальные кучи и приоритетные очереди . . . . . . . . . . . . . . . . . . . . . . . . 318
Линейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Эпилог . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Приложение А. Производительность АВЛ-деревьев . . . . . . . . . . . . . . . . 322
Приложение Б. NP-трудные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Задачи разрешимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
Задачи выполнимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
Трудно решить, легко проверить . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
Сведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
NP-трудность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
NP-полнота . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
Шпаргалка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
Приложение В. Ответы к упражнениям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
