Algorithms Illuminated. Part 1: The Basics
Первая часть четырёхтомной серии, основанной на популярных онлайн-курсах автора и его лекциях в Стэнфордском университете. Книга представляет собой введение в фундаментальные концепции анализа и проектирования алгоритмов.
Основное внимание уделяется асимптотическому анализу и нотации «большое O» — базовому языку для обсуждения эффективности алгоритмов. Автор объясняет, почему для высокоуровневого проектирования важно концентрироваться на скорости роста времени выполнения относительно размера входных данных, абстрагируясь от постоянных множителей и младших членов.
Центральной темой является парадигма «разделяй и властвуй». Подробно разбираются классические алгоритмы, построенные на этой технике: сортировка слиянием (MergeSort), алгоритм Карацубы для умножения чисел, алгоритм Штрассена для умножения матриц, а также алгоритмы для подсчёта инверсий и поиска ближайшей пары точек. Для анализа таких рекурсивных алгоритмов вводится и доказывается мастер-теорема.
Отдельный раздел посвящён рандомизированным алгоритмам. На примере быстрой сортировки (QuickSort) и алгоритма линейного выбора (RSelect) демонстрируется, как использование случайности приводит к созданию простых, элегантных и эффективных решений. В книге также приводится доказательство нижней оценки сложности для алгоритмов сортировки, основанных на сравнениях.
