8Введение

Глава 1. Основные понятия 15

Пространство — время 17

Оценка с точностью до порядка 17

Поиск сложных частей алгоритма 19

Сложность рекурсивных алгоритмов 20

Многократная рекурсия 21

Косвенная рекурсия 22

Требования рекурсивных алгоритмов к объему памяти 22

Логарифмы 25

Обращение к файлу подкачки 26

Псевдоуказатели, ссылки на объекты и коллекции 27

Глава 2. Списки 30

Коллекции 32

Список переменного размера 33

Класс SimpleList 36

Добавление элементов к связному списку 43

Удаление элементов из связного списка 44

Уничтожение связного списка 44

Сигнальные метки 45

Инкапсуляция связных списков 46

Доступ к ячейкам 47

Циклические связные списки 49

Проблема циклических ссылок 50

Двусвязные списки 50

Потоки 53

Глава 3. Стеки и очереди 60

Множественные стеки 62

Циклические очереди 65

Очереди на основе связных списков 69

Применение коллекций в качестве очередей 70

Приоритетные очереди 70

Многопоточные очереди 72

Глава 4. Массивы 75

Диагональные элементы 77

Прямая звезда 78

Нерегулярные связные списки 79

Индексирование массива 82

Глава 5. Рекурсия 86

Анализ времени выполнения программы 89

Анализ времени выполнения программы 91

Анализ времени выполнения программы 93

Анализ времени выполнения программы 96

Анализ времени выполнения программы 100

Бесконечная рекурсия 101

Потери памяти 102

Необоснованное применение рекурсии 103

Когда нужно использовать рекурсию 104

Глава 6. Деревья 121

Полные узлы 123

Списки потомков 124

Представление нумерацией связей 126

Полные деревья 129

Добавление элементов 135

Удаление элементов 136

Обход упорядоченных деревьев 139

Работа с деревьями со ссылками 144

Изменение MAX_PER_NODE 151

Использование псевдоуказателей в квадродеревьях 151

Восьмеричные деревья 152

Глава 7. Сбалансированные деревья 153

Удаление узла из АВЛ‑дерева 161

Производительность Б‑деревьев 167

Вставка элементов в Б‑дерево 167

Удаление элементов из Б‑дерева 168

Разновидности Б‑деревьев 169

Балансировка для устранения разбиения блоков 171

Вопросы, связанные с обращением к диску 173

База данных на основе Б+дерева 176

Глава 8. Деревья решений 179

Минимаксный поиск 181

Улучшение поиска в дереве игры 185

Метод ветвей и границ 187

Эвристики 191

Задача о выполнимости 207

Задача о разбиении 208

Задача поиска Гамильтонова пути 209

Задача коммивояжера 210

Задача о пожарных депо 211

Краткая характеристика сложных задач 212

Глава 9. Сортировка 213

Таблицы указателей 213

Объединение и сжатие ключей 215

Вставка в связных списках 222

Пирамиды 235

Приоритетные очереди 237

Алгоритм пирамидальной сортировки 240

Блочная сортировка с применением связного списка 243

Блочная сортировка на основе массива 245

Глава 10. Поиск 248

Поиск в упорядоченных списках 250

Поиск в связных списках 251

Интерполяционный следящий поиск 261

Глава 11. Хеширование 263

Преимущества и недостатки связывания 266

Хранение хеш‑таблиц на диске 270

Связывание блоков 274

Удаление элементов 275

Преимущества и недостатки применения блоков 277

Линейная проверка 278

Квадратичная проверка 284

Псевдослучайная проверка 286

Удаление элементов 289

Глава 12. Сетевые алгоритмы 292