Грокаем алгоритмы
Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018
Предисловие
Благодарности
О книге
Структура книги
Как работать с этой книгой
Для кого предназначена эта книга
Условные обозначения и загружаемые материалы
Об авторе
От издательства
Глава 1. Знакомство с алгоритмами
Введение
Что вы узнаете об эффективности алгоритмов
Что вы узнаете о решении задач
Бинарный поиск
Бинарный поиск (Binary search)
Более эффективный поиск
Упражнения
Время выполнения
«О-большое»
Время выполнения алгоритмов растет с разной скоростью
Наглядное представление «О-большое»
«О-большое» определяет время выполнения в худшем случае
Типичные примеры «О-большого»
Упражнения
Задача о коммивояжере
Шпаргалка
Глава 2. Сортировка выбором
Как работает память
Представление памяти в виде бесконечной ленты
Массивы и связанные списки
Массив (Array), Связанный список (Linked list)
Связанные списки
Массивы
Терминология
Упражнения
Вставка в середину списка
Удаление
Упражнения
Сортировка выбором
Сортировка выбором (Selection sort)
Пример кода
Шпаргалка
Глава 3. Рекурсия
Рекурсия
Базовый случай и рекурсивный случай
Стек
Стек вызовов
Упражнения
Стек вызовов с рекурсией
Упражнения
Шпаргалка
Глава 4. Быстрая сортировка
«Разделяй и властвуй»
Разделяй и властвуй (Divide and conquer)
Упражнения
Быстрая сортировка
Быстрая сортировка (Quicksort)
Снова об «О-большом»
Сортировка слиянием и быстрая сортировка
Средний и худший случай
Упражнения
Шпаргалка
Глава 5. Хеш-таблицы
Хеш-функции
Упражнения
Примеры использования
Использование хеш-таблиц для поиска
Исключение дубликатов
Использование хеш-таблицы как кэша
Шпаргалка
Коллизии
Быстродействие
Коэффициент заполнения
Хорошая хеш-функция
Упражнения
Шпаргалка
Глава 6. Поиск в ширину
Знакомство с графами
Что такое граф?
Поиск в ширину
Поиск в ширину (Breadth-first-search, BFS)
Поиск кратчайшего пути
Очереди
Упражнения
Реализация графа
Направленный ациклический граф (Directed acyclic graph, DAG), Направленный граф (Directed graph)
Реализация алгоритма
Время выполнения
Упражнения
Шпаргалка
Глава 7. Алгоритм Дейкстры
Работа с алгоритмом Дейкстры
Терминология
Взвешенный граф (Weighted graph), Циклический граф (Cycle graph)
История одного обмена
Ребра с отрицательным весом
Реализация
Упражнения
Шпаргалка
Глава 8. Жадные алгоритмы
Задача составления расписания
Задача о составлении расписания
Задача о рюкзаке
Упражнения
Задача о покрытии множества
Приближенные алгоритмы
Множество (Математика), Приближенные алгоритмы
Упражнения
NР - полные задачи
Задача о коммивояжере - шаг за шагом
Как определить, что задача является NР-полной?
Упражнения
Шпаргалка
Глава 9. Динамическое программирование
Задача о рюкзаке
Простое решение
Динамическое программирование
Задача о рюкзаке: вопросы
Что произойдет при добавлении элемента?
Упражнения
Что произойдет при изменении порядка строк?
Можно ли заполнять таблицу по столбцам, а не по строкам?
Что произойдет при добавлении меньшего элемента?
Можно ли взять часть предмета?
Оптимизация туристического маршрута
Взаимозависимые элементы
Может ли оказаться, что решение требует более двух «подрюкзаков»?
Возможно ли, что при лучшем решении в рюкзаке остается пустое место?
Упражнения
Самая длинная общая подстрока
Построение таблицы
Заполнение таблицы
Решение
Самая длинная общая подпоследовательность
Самая длинная общая подпоследовательность - решение
Упражнения
Шпаргалка
Глава 10. Алгоритм k ближайших соседей
Апельсины и грейпфруты
Построение рекомендательной системы
Построение рекомендательных систем