Рецепты для компьютера
Алгоритм — конечная последовательность точных инструкций для решения задачи. Слово происходит от имени персидского математика аль-Хорезми (ок. 780–850), чей трактат «Китаб аль-джабр» заложил основы алгебры. Формальное определение дали Алан Тьюринг (машина Тьюринга, 1936) и Алонзо Чёрч (лямбда-исчисление, 1936) — независимо друг от друга.
Алгоритм решает задачу, но два алгоритма для одной задачи могут работать за разное время. Сортировка 1 миллиона чисел пузырьком — триллион операций; быстрая сортировка Хоара — 20 миллионов. Разница в 50 000 раз. Поэтому анализ сложности — не теоретическая забава, а практическая необходимость.
Big O: язык скорости алгоритмов
Big O нотация описывает, как растёт время работы при увеличении объёма данных n. Придумал её Пауль Бахман (1894), популяризировал Эдмунд Ландау — поэтому иногда называют «символы Ландау».
O(1) — константа: доступ к элементу массива по индексу. Не зависит от размера данных.
O(log n) — логарифмический: бинарный поиск. Каждый шаг отсекает половину. Для миллиарда элементов — всего 30 шагов.
O(n) — линейный: перебор всех элементов. Удвоил данные — удвоил время.
O(n log n) — линеарифмический: merge sort, quicksort. Оптимальная скорость для сортировки сравнением (доказано в 1960-х).
O(n²) — квадратичный: пузырьковая сортировка, два вложенных цикла. 10 000 элементов — 100 миллионов операций.
O(2ⁿ) — экспоненциальный: полный перебор подмножеств. При n=40 — триллион вариантов.
Классические алгоритмы сортировки
Пузырьковая сортировка (bubble sort) — сравнивает соседние элементы и меняет местами. O(n²), придумана в 1956 году. Используется только в учебных целях.
Сортировка слиянием (merge sort) — Джон фон Нейман, 1945. Делит массив пополам, сортирует половинки рекурсивно, затем сливает. Гарантированный O(n log n), но требует дополнительную память O(n).
Быстрая сортировка (quicksort) — Тони Хоар, 1960. Выбирает опорный элемент (pivot), разделяет массив на «меньше» и «больше», рекурсивно сортирует части. В среднем O(n log n), в худшем O(n²), но на практике самая быстрая. Используется в стандартных библиотеках C, Java, Python (Timsort — гибрид merge sort и insertion sort).
Алгоритмы поиска
Линейный поиск — перебор элементов по порядку, O(n). Работает на любых данных, но медленный.
Бинарный поиск — работает только на отсортированных данных. Сравнивает средний элемент, отбрасывает половину. O(log n). Описан ещё в книге Джона Мочли (1946), но первая корректная реализация без ошибок появилась только в 1962 году — 16 лет на правильный код из 20 строк.
Поиск в графах — BFS (поиск в ширину) и DFS (поиск в глубину). BFS находит кратчайший путь в невзвешенном графе. Алгоритм Дейкстры (1959) — для взвешенных графов. A* (Питер Харт, 1968) — для графов с эвристикой (используется в GPS-навигации и играх).
NP-полнота: границы вычислимости
В 1971 году Стивен Кук доказал теорему: задача выполнимости булевых формул (SAT) — NP-полная. Это значит, что если найдётся быстрый алгоритм для SAT, то ВСЕ задачи класса NP решатся быстро. Проблема P ≟ NP — открытый вопрос тысячелетия (Клэйовский институт, $1 000 000 за решение).
Практический смысл: задача коммивояжёра (оптимальный маршрут через N городов), упаковка рюкзака, раскраска графа — для всех этих задач не существует известных алгоритмов быстрее экспоненциального. Для 50 городов полный перебор потребует больше времени, чем существует Вселенная.
Рекурсия и динамическое программирование
Рекурсия — алгоритм вызывает сам себя с уменьшенной задачей. Числа Фибоначчи: F(n) = F(n-1) + F(n-2). Наивная рекурсия — O(2ⁿ), потому что пересчитывает одни и те же значения.
Динамическое программирование (DP) — Ричард Беллман, 1953. Сохраняет уже вычисленные подзадачи в таблицу. Фибоначчи с DP — O(n) вместо O(2ⁿ). DP применяется в биоинформатике (выравнивание ДНК), экономике (оптимальное распределение ресурсов) и распознавании речи (алгоритм Витерби, 1967).