Алгоритмы: карта трека и как учиться решать задачи

Есть два способа читать книгу по алгоритмам. Первый — выучить, что сортировка слиянием работает за O(n log n), а Дейкстра — за O(m log n), и на этом успокоиться. Второй — понять, почему эти оценки такие, из каких кирпичей они собраны и как самому собрать похожую конструкцию под задачу, которой нет ни в одной книге. Первый даёт эрудицию, второй — навык. Этот трек про второй.

Статья-обзор даёт строгую рамку («что вообще считается алгоритмом»), карту трека и — главное — воспроизводимый метод разбора задачи, который дальше применяется в каждой статье. В конце мы разберём одну задачу четырьмя способами и увидим, как перебор за 25 секунд превращается в решение за 1 миллисекунду.

Что такое алгоритм, если говорить строго

Бытовое определение «последовательность шагов» бесполезно: рецепт борща ему тоже удовлетворяет. Рабочее определение состоит из пяти требований — они восходят к Кнуту (The Art of Computer Programming, том 1, §1.1):

1. Конечность. Алгоритм завершается за конечное число шагов на любом допустимом входе. Процедура, которая для некоторых входов зацикливается, — не алгоритм, а полуалгоритм.
2. Определённость. Каждый шаг задан однозначно. «Выбери подходящий элемент» — не шаг.
3. Вход. Ноль или больше значений из заранее заданного множества.
4. Выход. Одно или больше значений, находящихся в заданном отношении со входом. Это отношение и есть спецификация — то, что мы потом доказываем.
5. Эффективность. Каждый шаг настолько элементарен, что его в принципе можно выполнить точно и за конечное время.

Из этого сразу следуют две вещи, которые новички обычно пропускают.

Алгоритм всегда существует относительно модели вычислений. «За O(n)» бессмысленно без ответа на вопрос «в какой модели и что считается одной операцией». Стандартная модель анализа — word RAM: память это массив ячеек по w бит, доступ по адресу и арифметика над машинным словом за O(1), причём w ≥ log n, чтобы индекс влезал в слово. Именно поэтому мы вправе говорить «сравнение двух чисел — одна операция», хотя на реальном железе сравнение 64-битных чисел и сравнение строк по 100 КБ стоят по-разному. Когда модель перестаёт описывать реальность (кэш-промахи, диск, сеть), её меняют — этому посвящены статьи о внешней памяти и о практической оптимизации.

Алгоритм и его реализация — разные объекты. Алгоритм доказывают, реализацию тестируют. Бинарный поиск был опубликован в 1946 году, первая корректная реализация для произвольного n — только в 1962-м; а знаменитый баг переполнения в (low + high) / 2 жил в java.util.Arrays.binarySearch до 2006 года (разбор Джошуа Блоха). Мы будем аккуратны и там, и там.

Карта трека

Трек устроен слоями: инструменты анализа, базовые техники на массивах, «большие идеи» (рекурсия, жадность, ДП), графы, специализированные области и, в конце, то, что отличает работающий код от красивого.

Маршрут по файлам — читать лучше по порядку, но после блока «Большие идеи» ветки можно брать в любом порядке:

Держите под рукой трек Структуры данных: алгоритм и структура данных — две стороны одной монеты. Дейкстра без кучи — это O(n²), с бинарной кучей — O(m log n), с фибоначчиевой — O(m + n log n). Алгоритм тот же.

Почему асимптотика — это не педантизм

Главная причина учить O(·) — не собеседования, а то, что константа железа растёт медленно, а разрыв между O(n) и O(n²) — квадратично. Современное ядро CPU выполняет 10^8–10^9 простых операций в секунду (интерпретируемый Python — около 10^7):

Обратите внимание на пересечения: O(n²) до n ≈ 8 идёт ниже O(n log n) — поэтому реальные сортировки переключаются на вставки на коротких отрезках. Асимптотика описывает поведение при больших n, на малых правят константы; это два разных вопроса.

А вот та же информация в форме, в которой она нужна при чтении условия задачи:

Практический приём: читай ограничения раньше, чем условие. n ≤ 20 — почти наверняка перебор подмножеств или ДП по битовой маске. n ≤ 500 — скорее всего O(n³): ДП на подотрезках или Флойд. n ≤ 10^5 — нужен O(n log n): сортировка, множество, бинпоиск или граф. n ≤ 10^18 — работать надо не с данными, а с математикой: двоичное возведение в степень, теория чисел, формула.

Метод: как условие превращается в решение

Самая частая ошибка — писать код сразу. Порядок должен быть другим, и он проверяем.

Ключевой узел здесь — «найти, что пересчитывается лишний раз». Почти все ускорения в алгоритмах сводятся к одной из пяти идей:

• Переиспользовать вычисленное — мемоизация, префиксные суммы, ДП.
• Не рассматривать заведомо плохое — отсечения, жадность, ветви и границы.
• Навести порядок — сортировка, куча, сбалансированное дерево; порядок сам по себе информация.
• Разделить — разделяй-и-властвуй, декомпозиция на независимые части.
• Сменить представление — хеш вместо строки, битовая маска вместо множества, граф вместо текста задачи.

Если застряли — пройдитесь по этому списку явно. Это не мистика, а конечный чек-лист.

Разбор: одна задача, четыре решения

Задача (классическая maximum subarray, Bentley, Programming Pearls, гл. 8): дан массив целых чисел a[0..n-1], возможно отрицательных. Найти максимальную сумму непустого непрерывного подотрезка, то есть max{ sum(a[i..j]) : 0 ≤ i ≤ j < n }.

Обратите внимание на слово непустого: разреши мы пустой отрезок, ответ на массиве из одних отрицательных чисел стал бы 0. Такие мелочи в спецификации дают половину неверных решений.

Шаг 0: наивное решение, O(n³)

Перебрать все пары (i, j) и честно просуммировать: пар O(n²), суммирование O(n). Итого O(n³) времени, O(1) памяти. В бою такое не пишут, а в тестах пишут обязательно: это наш эталон правды.

Шаг 1: префиксные суммы, O(n²)

Лишняя работа очевидна: сумма a[i..j] пересчитывается с нуля, хотя a[i..j-1] уже известна. Заводим префиксы pref[k] = a[0] + ... + a[k-1], тогда sum(a[i..j]) = pref[j+1] - pref[i] за O(1).

def max_sub_prefix(a: list[int]) -> int:
    """Префиксные суммы. Время O(n^2), память O(n)."""
    n = len(a)
    pref = [0] * (n + 1)
    for i, x in enumerate(a):
        pref[i + 1] = pref[i] + x      # pref[k] — сумма первых k элементов

    best = float("-inf")
    for i in range(n):
        for j in range(i, n):
            best = max(best, pref[j + 1] - pref[i])
    return best

Первый урок: мы убрали цикл, не придумав ничего умного — просто перестали пересчитывать уже посчитанное. Это самая частая техника ускорения вообще.

Шаг 2: разделяй-и-властвуй, O(n log n)

Делим массив пополам. Оптимальный отрезок лежит целиком слева, целиком справа либо пересекает середину; третий случай считается линейным проходом — лучший суффикс левой половины плюс лучший префикс правой.

from math import inf

def _max_cross(a: list[int], lo: int, mid: int, hi: int) -> int:
    """Лучший отрезок, обязательно содержащий границу mid|mid+1. Время O(hi-lo)."""
    s, left = 0, -inf
    for i in range(mid, lo - 1, -1):    # идём влево от середины
        s += a[i]
        left = max(left, s)
    s, right = 0, -inf
    for i in range(mid + 1, hi + 1):    # и вправо
        s += a[i]
        right = max(right, s)
    return left + right

def max_sub_dc(a: list[int], lo: int = 0, hi: int | None = None) -> int:
    """Разделяй-и-властвуй. Время O(n log n), память O(log n) на стек рекурсии."""
    if hi is None:
        hi = len(a) - 1
    if lo == hi:                        # база: один элемент, отрезок обязан быть непустым
        return a[lo]
    mid = (lo + hi) // 2
    return max(
        max_sub_dc(a, lo, mid),
        max_sub_dc(a, mid + 1, hi),
        _max_cross(a, lo, mid, hi),
    )

Рекуррентность T(n) = 2·T(n/2) + Θ(n) даёт Θ(n log n) по мастер-теореме (случай 2); подробный разбор — в статье о рекурсии.

Шаг 3: алгоритм Кадане, O(n)

Меняем вопрос: вместо «какой отрезок лучший вообще» спросим «какой лучший отрезок, оканчивающийся ровно в позиции i». Ответ выражается через ответ для i-1 за одну операцию — продолжаем предыдущий отрезок либо начинаем новый с a[i], и продолжать выгодно ровно тогда, когда накопленная сумма неотрицательна.

def kadane(a: list[int]) -> tuple[int, int, int]:
    """Максимальная сумма подотрезка и его границы. Время O(n), память O(1)."""
    best = cur = a[0]
    best_l = best_r = cur_l = 0

    for i in range(1, len(a)):
        if cur < 0:                     # тащить отрицательный хвост невыгодно
            cur, cur_l = a[i], i
        else:
            cur += a[i]
        if cur > best:
            best, best_l, best_r = cur, cur_l, i

    return best, best_l, best_r

Инвариант цикла (перед итерацией i): cur равно максимальной сумме отрезка, оканчивающегося в i-1, а best — максимальной сумме отрезка целиком внутри a[0..i-1]. Инициализация верна для i = 1; шаг сохраняет инвариант разбором двух случаев; после выхода i = n, значит best — ответ для всего массива. Полное доказательство корректности занимает три строки — потому что мы выбрали правильную формулировку подзадачи; техника разобрана в статье об анализе и доказательствах.

Сравнение: измеренные времена

Все четыре версии дают одинаковый ответ; вот сколько они на это тратят (CPython 3.11, одно ядро, случайные числа из [-100, 100]):

Рост n в 10 раз даёт рост времени в 100 раз у квадратичного решения и ровно в 10 раз у линейного. Никакая оптимизация констант — переписывание на C, векторизация, потоки — этот разрыв не закроет: 100× против 10× побеждает любую константу при достаточном n. В этом и состоит смысл фразы «сначала асимптотика, потом константы».

Как проверять, что вы правы: стресс-тест

Самый недооценённый инструмент обучения: генерируем случайные маленькие входы и сверяем быстрый алгоритм с наивным. Ошибка находится за секунды — вместе с контрпримером.

import random

def brute(a: list[int]) -> int:
    """Эталон O(n^3): медленно, зато очевидно правильно."""
    n = len(a)
    return max(sum(a[i:j + 1]) for i in range(n) for j in range(i, n))

random.seed(1)
for _ in range(20_000):
    n = random.randint(1, 8)            # маленькие входы: контрпример будет читаемым
    a = [random.randint(-5, 5) for _ in range(n)]

    expected = brute(a)
    got, l, r = kadane(a)

    assert got == expected, f"сумма: {a} -> {got}, ожидалось {expected}"
    assert sum(a[l:r + 1]) == got, f"границы: {a} -> [{l}, {r}]"

Три правила, без которых стресс-тест не работает:

1. Маленькие n. На n ≤ 8 контрпример помещается в голову. На n = 1000 вы получите массив, в котором ничего не разглядите.
2. Узкий диапазон значений. [-5, 5] вместо [-10^9, 10^9] — так чаще возникают совпадения, нули и повторы, то есть именно те краевые случаи, где ломаются решения.
3. Проверять не только ответ, но и свидетеля — здесь то, что найденные границы действительно дают заявленную сумму. Верное число при неверных индексах — коварный баг.

Тот же приём лежит в основе property-based тестирования в проде: Hypothesis (Python), QuickCheck (Haskell), fast-check (TypeScript) — индустриальная версия той же идеи с автоминимизацией контрпримера.

Как учиться: траектория навыка

Навык проходит через различимые состояния, и на каждом полезны разные действия. Главная ошибка — застрять в «узнаю решение» и счесть это пониманием.

Что из этого следует практически:

• Таймбокс перед подсказкой. 30–45 минут честной попытки, потом разбор. Меньше — не успевает включиться поиск; больше — время уходит в тупик, а не в обучение.
• После разбора — обязательно написать код самому. Прочитанное решение переводит вас только в «узнавание». Переход в «воспроизведение» стоит клавиатуры, а не глаз.
• Возвращаться к задаче через 3–7 дней. Интервальное повторение работает для алгоритмов так же, как для языков; см. обзор Dunlosky et al., 2013, где practice testing и distributed practice — единственные техники с высшим рейтингом.
• Вести журнал ошибок. Одна строка на задачу: «в чём была ошибка мышления». Через месяц вы увидите 3–4 повторяющихся паттерна — самый ценный документ в вашей учёбе.
• Решать вслух. Формулировка инварианта словами вскрывает дыру в рассуждении раньше, чем компилятор.

Что учить первым: приоритеты

Не все темы окупаются одинаково быстро. Если время ограничено — вот картина по двум осям: как часто техника встречается и сколько стоит её освоить.

Левый верхний квадрант окупается в первый же месяц и используется в продакшне ежедневно. Правый нижний — прекрасные темы, но браться за них раньше левого верха нерационально.

Типичные ошибки

• Оптимизировать константу вместо асимптотики. Переписать O(n²) цикл на C и получить 30× — приятно, но O(n log n) на Python даст 3000× при n = 10^6. Обратная ошибка тоже реальна: гнаться за O(n log n) там, где n ≤ 100, — трата времени и источник багов.
• Считать сложность только по времени. O(n) памяти при n = 10^9 — это 4–8 ГБ, то есть OOM. Память — такое же ограничение, и в потоковых задачах она главная.
• Путать «работает на моих примерах» с «корректно». Стресс-тест против наивной версии находит за 20 секунд то, на что уходит вечер отладки.
• Не проверять краевые случаи. Пустой вход, один элемент, все элементы равны, все отрицательные, максимумы типа, дубликаты, уже отсортированный вход и отсортированный в обратном порядке — это буквально чек-лист, пройдите его.
• Игнорировать переполнение. В Python его нет, в Go/Java/C# — есть: сумма 10^5 элементов по 10^9 не влезает в int32. Баг середины в бинпоиске — из этой же семьи.
• Считать амортизированную оценку худшей. list.append — O(1) амортизированно, но конкретный вызов может быть O(n). Для батча неважно, для p99-латентности критично.
• Учить решения, а не техники. Задач бесконечно много, техник — около двадцати. Правильный вопрос после разбора: «какое свойство задачи позволило это применить?»

Где это в реальном коде

Алгоритмы редко встречаются в виде «напишите Дейкстру». Они встречаются так:

• Базы данных. Планировщик запросов — динамическое программирование по порядку соединений (классика: Selinger et al., 1979, архитектура System R). Merge join — двухуказательный проход по отсортированным потокам. Индексы — B-деревья, то есть алгоритмы внешней памяти.
• Компиляторы и сборка. Топологическая сортировка для порядка сборки, раскраска графа при распределении регистров (NP-трудная, решается эвристикой), разрешение версий зависимостей — SAT-солвер, то есть прямое столкновение с NP-полнотой.
• Сеть и инфраструктура. OSPF — это Дейкстра поверх состояния каналов; балансировщики используют consistent hashing; rate limiting — скользящее окно.
• Диффы и контроль версий. git diff — алгоритм Майерса, вариация поиска кратчайшего пути на графе редактирования (оригинальная статья, 1986).
• Наблюдаемость и поиск. Подсчёт уникальных пользователей — HyperLogLog, приблизительные квантили — t-digest, ANN-индексы (HNSW) — навигация по графу малого мира, дедупликация документов — MinHash и LSH.

Общая закономерность: в проде вы почти никогда не пишете алгоритм с нуля, но постоянно выбираете его, оцениваете применимость к своим данным и объясняете коллегам, почему сервис лёг при росте нагрузки вдвое. Для этого нужна не память, а модель.

Источники

Книги, которые действительно стоит держать под рукой:

• Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ (CLRS), 4-е изд. — страница книги в MIT Press. Справочник и стандарт строгости.
• Роберт Седжвик, Кевин Уэйн. Algorithms, 4-е изд. — algs4.cs.princeton.edu. Лучший баланс кода и объяснений, весь код открыт.
• Стивен Скиена. The Algorithm Design Manual, 3-е изд. — algorist.com. Уникальная часть — «каталог задач»: как понять, какой алгоритм вам вообще нужен.
• Клейнберг, Тардос. Algorithm Design — сильнейшее изложение того, как придумывают алгоритмы, особенно жадные и потоки. Плюс MIT 6.006 — открытый курс с видео и конспектами.
• Практика: Codeforces, LeetCode, Project Euler (математический уклон), Advent of Code (реализация и аккуратность).

Если вы пришли из языкового трека — Go, TypeScript или C# — код здесь даётся на Python ради читаемости, но идеи переносятся дословно; отличаются константы и наличие переполнения целых.

Итог

• Алгоритм — это конечная, определённая процедура относительно модели вычислений, и он существует отдельно от реализации: первый доказывают, вторую тестируют.
• Асимптотика — не ритуал, а способ за секунду понять, влезет ли решение в бюджет. Читайте ограничения раньше условия.
• Ускорение почти всегда = устранение повторного вычисления, отсечение заведомо плохого, наведение порядка, разделение или смена представления.
• Понимание проверяется двумя вещами: инвариантом, который вы можете произнести вслух, и зелёным стресс-тестом. Учить надо техники и их предпосылки, а не готовые решения.

Что дальше

Следующий шаг — освоить язык, на котором сформулировано всё остальное: асимптотические обозначения без ручного махания, инварианты цикла, амортизационный анализ и рекуррентности.

→ Анализ алгоритмов: асимптотика, инварианты и доказательство корректности