Изучение алгоритмов

Предисловие 11
Глава 1. Знакомство с алгоритмами 18
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач 19
Бинарный поиск 20
Более эффективный поиск 23
Упражнения 27
Время выполнения 28
«О-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «О-большое» 32
«О-большое» определяет время выполнения в худшем случае 34
Типичные примеры «О-большого» 35
Упражнения 36
Задача о коммивояжере 37
Шпаргалка 39

Глава 2. Сортировка выбором 40
Как работает память 41
Массивы и связанные списки 43
Связанные списки 45
Массивы 46
Терминология 47
Упражнения 48
Вставка в середину списка 49
Удаление 50
Упражнения 51
Сортировка выбором 53
Пример кода 57
Шпаргалка 58

Глава 3. Рекурсия 59
Рекурсия 60
Базовый случай и рекурсивный случай 63
стек 65
Стек вызовов 66
Упражнения 68
Стек вызовов с рекурсией 69
Упражнения 73
Шпаргалка 74
Глава 4. Быстрая сортировка 75
«Разделяй и властвуй» 76
Упражнения 85
Быстрая сортировка 85
Снова об «О-большом» 92
Сортировка слиянием и быстрая сортировка 93
Средний и худший случай 95
Упражнения 99
Шпаргалка 99

Глава 5. Хеш-таблицы 100
Хеш-функции 103
Упражнения 107
Примеры использования 107
Использование хеш-таблиц для поиска 108
Исключение дубликатов 110
Использование хеш-таблицы как кэша 112
Шпаргалка 116
Коллизии 116
Быстродействие 119
Коэффициент заполнения 122
Хорошая хеш-функция 124
Упражнения 125
Шпаргалка 126

Глава 6. Поиск в ширину 127
Знакомство с графами 128
Что такое граф? 131
Поиск в ширину 132
Поиск кратчайшего пути 135
Очереди 136
Упражнения 137
Реализация графа 138
Реализация алгоритма 141
Время выполнения 146
Упражнения 147
Шпаргалка 150

Глава 7. Алгоритм Дейкстры 151
Работа с алгоритмом Дейкстры 152
Терминология 157
История одного обмена 160
Ребра с отрицательным весом 167
Реализация 170
Упражнения 181
Шпаргалка 181
Глава 8. Жадные алгоритмы 182
Задача составления расписания 183
Задача о рюкзаке 185
Упражнения 187
Задача о покрытии множества 187
Приближенные алгоритмы 189
Упражнения 196
NР-полные задачи 196
Задача о коммивояжере - шаг за шагом 197
Как определить, что задача является NР-полной? 202
Упражнения 205
Шпаргалка 205

Глава 9. Динамическое программирование 206
Задача о рюкзаке 206
Простое решение 207
Динамическое программирование 208
Задача о рюкзаке: вопросы 217
Что произойдет при добавлении элемента? 217
Упражнения 220
Что произойдет при изменении порядка строк? 220
Можно ли заполнять таблицу по столбцам, а не по строкам? 221
Что произойдет при добавлении меньшего элемента? 221
Можно ли взять часть предмета? 221
Оптимизация туристического маршрута 223
Взаимозависимые элементы 224
Может ли оказаться, что решение требует более двух «подрюкзаков»? 225
Возможно ли, что при лучшем решении в рюкзаке остается пустое место? 226
Упражнения 226
Самая длинная общая подстрока 226
Построение таблицы 228
Заполнение таблицы 229
Решение 230
Самая длинная общая подпоследовательность 232
Самая длинная общая подпоследовательность - решение 233
Упражнения 235
Шпаргалка 235

Глава 10. Алгоритм k ближайших соседей 236
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия 245
Выбор признаков 248
Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра 251
Прогнозы на биржевых торгах 252
Шпаргалка 252

Глава 11. Что дальше? 254
Деревья 254
Инвертированные индексы 258
Преобразование Фурье 259
Параллельные алгоритмы 260
MapReduce 261
Для чего нужны распределенные алгоритмы? 261
Функция map 261
Функция reduce 262
Фильтры Блума и Hyperloglog 263
Фильтры Блума 265
Hyperloglog 265
Алгоритмы SHA 266
Сравнение файлов 267
Проверка паролей 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи-Хеллмана 270
Линейное программирование 272
Эпилог 273
Ответы к упражнениям 273