Прикладные структуры данных и алгоритмы. Прокачиваем навыки (Венгроу Джей) ; Питер, 2024

Отзывы о втором издании
Предисловие
Для кого эта книга
Новое во втором издании
Что вы найдете в этой книге
Как читать эту книгу
Примеры кода
Интернет-ресурсы
Благодарности
Обратная связь
От издательства
Глава 1. О важности структур данных
Структуры данных
Массив: базовая структура данных
Операции над структурами данных
Измерение скорости
Чтение
Поиск
Вставка
Удаление
Множества: как одно правило может повлиять на
эффективность
Выводы
Упражнения
Глава 2. О важности алгоритмов
Упорядоченные массивы
Поиск в упорядоченном массиве
Бинарный поиск
Программная реализация
Сравнение алгоритмов бинарного и линейного
поиска
Викторина
Выводы
Упражнения
Глава 3. О да! Нотация "О большое"
"O большое": количество шагов при наличии N
элементов
Суть О-нотации
Погружение в суть О-нотации
Один алгоритм, разные сценарии
Алгоритм третьего типа
Логарифмы
Значение выражения O(log N)
Практические примеры
Выводы
Упражнения
Глава 4. Оптимизация кода с помощью О-нотации
Пузырьковая сортировка
Пузырьковая сортировка в действии
Программная реализация
Эффективность пузырьковой сортировки
Квадратичная задача
Линейное решение
Выводы
Упражнения
Глава 5. Оптимизация кода с О-нотацией и без нее
Сортировка выбором
Сортировка выбором в действии
Программная реализация
Эффективность сортировки выбором
Игнорирование констант
Категории алгоритмической сложности в О-нотации
Практический пример
Значимые шаги
Выводы
Упражнения
Глава 6. Повышение эффективности с учетом
оптимистичных сценариев
Сортировка вставками
Сортировка вставками в действии
Программная реализация
Эффективность сортировки вставками
Средний случай
Практический пример
Выводы
Упражнения
Глава 7. О-нотация в работе программиста
Среднее арифметическое четных чисел
Конструктор слов
Выборка из массива
Среднее значение температуры в градусах
Цельсия
Бирки для одежды
Подсчет единиц
Поиск палиндрома
Вычисление произведений всех пар чисел
Работа с несколькими наборами данных
Взломщик паролей
Выводы
Упражнения
Глава 8. Молниеносный поиск с помощью хеш-
таблиц
Хеш-таблицы
Хеширование
Создание тезауруса для удовольствия и прибыли,
но в основном для прибыли .
Поиск в хеш-таблице
Однонаправленный поиск
Разрешение коллизий
Создание эффективной хеш-таблицы
Великий компромисс
Хеш-таблицы для организации данных
Хеш-таблицы для ускорения выполнения кода
Подмножество массива
Выводы
Упражнения
Глава 9. Создание чистого кода с помощью стеков
и очередей
Стеки
Абстрактные типы данных
Стек в действии
Программная реализация: линтер на базе стека
О важности ограниченных структур данных
Очереди
Реализация очереди
Очередь в действии
Выводы
Упражнения
Глава 10. Рекурсивно рекурсируем с помощью
рекурсии
Рекурсия вместо цикла
Базовый случай
Чтение рекурсивного кода
Рекурсия глазами компьютера
Стек вызовов
Переполнение стека
Обход файловой системы
Выводы
Упражнения
Глава 11. Учимся писать рекурсивный код
Категория рекурсивных задач: многократное
выполнение действия
Рекурсивный прием: передача дополнительных
параметров
Категория рекурсивных задач: вычисления
Два подхода к вычислениям
Нисходящая рекурсия: новый способ мышления
Нисходящий способ мышления
Вычисление суммы элементов массива
Обращение строки
Подсчет символов "x" в строке
Задача с лестницей
Базовый случай для задачи с лестницей
Генерация анаграмм
Эффективность алгоритма генерации анаграмм
Выводы
Упражнения
Глава 12. Динамическое программирование
Бесполезные рекурсивные вызовы
Пошаговый разбор выполнения рекурсивной
функции max
Маленькое исправление для большого "O"
Эффективность рекурсии
Перекрывающиеся подзадачи
Динамическое программирование с помощью
мемоизации
Реализация мемоизации
Восходящее динамическое программирование
Восходящий подход для вычисления элементов
последовательности Фибоначчи
Мемоизация и восходящий подход
Выводы
Упражнения
Глава 13. Рекурсивные алгоритмы для ускорения
выполнения кода
Разбиение
Программная реализация
Алгоритм быстрой сортировки (Quicksort)
Программная реализация
Эффективность быстрой сортировки
Взгляд на быструю сортировку сверху
Вычисление эффективности быстрой сортировки с
помощью О-нотации
Временная сложность быстрой сортировки в
худшем сценарии
Быстрая сортировка и сортировка вставками
Алгоритм быстрого выбора
Эффективность алгоритма быстрого выбора
Программная реализация
Сортировка как основа для других алгоритмов
Выводы
Упражнения
Глава 14. Структуры данных на основе узлов
Связные списки
Реализация связного списка
Чтение
Программная реализация: чтение элементов
связного списка
Поиск
Программная реализация: поиск по связному списку
Вставка
Программная реализация: вставка элемента в
связный список
Удаление
Программная реализация: удаление элемента из
связного списка
Эффективность операций над связными списками
Связные списки в действии
Двусвязные списки
Программная реализация: добавление элемента в
двусвязный список
Движение вперед и назад
Очереди на основе двусвязных списков
Программная реализация
Выводы
Упражнения
Глава 15. Тотальное ускорение с помощью
двоичных деревьев поиска
Деревья
Двоичные деревья поиска
Поиск
Эффективность поиска в двоичном дереве поиска
Log(N) уровней
Программная реализация: поиск значения в
двоичном дереве
Вставка
Программная реализация: вставка значения в
двоичное дерево поиска
Порядок вставки
Удаление
Удаление узла с двумя дочерними элементами
Поиск узла-преемника
Узел-преемник с правым дочерним элементом
Полный алгоритм удаления
Программная реализация: удаление значения из
двоичного дерева поиска ..
Эффективность удаления значения из двоичного
дерева поиска
Двоичные деревья поиска в действии
Обход двоичного дерева поиска
Выводы
Упражнения
Глава 16. Расстановка приоритетов с помощью куч
Приоритетные очереди
Кучи
Свойство кучи
Полные деревья
Особенности кучи
Вставка в кучу
Поиск последнего узла
Удаление из кучи
Кучи и упорядоченные массивы
Проблема последнего узла... снова
Массивы в качестве куч
Обход кучи на основе массива
Программная реализация: вставка значения в кучу
Программная реализация: удаление значения из
кучи
Другие варианты реализации кучи
Кучи в качестве приоритетных очередей
Выводы
Упражнения
Глава 17. Префиксные деревья
Префиксные деревья
Узел префиксного дерева
Класс Trie
Хранение слов
Важность звездочки
Поиск в префиксном дереве
Программная реализация
Эффективность поиска в префиксном дереве
Вставка значения в префиксное дерево
Программная реализация
Создание функции автозаполнения
Собираем все слова
Пошаговый разбор рекурсивных вызовов
Завершение функции автозаполнения
Префиксные деревья с дополнительными
значениями: улучшенная функция автозаполнения
Выводы
Упражнения
Глава 18. Отражение связей между объектами с
помощью графов
Графы
Графы и деревья
Терминология графов
Простейшая реализация графа
Ориентированные графы
Объектно-ориентированная реализация графа
Поиск по графу
Поиск в глубину
Пошаговый разбор поиска в глубину
Программная реализация
Поиск в ширину
Пошаговый разбор поиска в ширину
Программная реализация
Поиск в глубину и поиск в ширину
Эффективность поиска по графу
Временная сложность 0(V + E)
Взвешенные графы
Реализация взвешенного графа
Задача о кратчайшем пути
Алгоритм Дейкстры
Подготовка алгоритма Дейкстры
Этапы алгоритма Дейкстры
Пошаговый разбор алгоритма Дейкстры
Поиск кратчайшего пути
Программная реализация: алгоритм Дейкстры
Эффективность алгоритма Дейкстры
Выводы
Упражнения
Глава 19. Работа в условиях ограниченного
пространства
Выражение пространственной сложности с
помощью O-нотации
Компромисс между временем выполнения и
занимаемой памятью
Скрытые издержки рекурсии
Выводы
Упражнения
Глава 20. Оптимизация кода
Предварительное условие: определение текущей
эффективности
Определение лучшей эффективности из возможных
Развитие воображения
Волшебные поиски
Волшебный поиск авторов книг
Дополнительная структура данных
Проблема двух сумм
Выявление закономерностей
Игра с монетками
Генерация примеров
Перестановка чисел для уравнивания сумм (задача
о sum swap)
Жадные алгоритмы
Максимальный элемент массива
Наибольшая сумма элементов подраздела массива
Жадные предсказания цен на акции
Замена структуры данных
Алгоритм для проверки анаграмм
Группировка элементов массива
Выводы
Заключительные мысли
Упражнения
Приложение. Решения к упражнениям