Что такое алгоритм и сложность: интуиция Big-O для всех

В прошлой статье трека мы разложили данные по полкам — увидели, что массивы, списки, деревья и хеш-таблицы существуют потому, что у каждой формы хранения своя цена за поиск, вставку и удаление (Как хранят данные). Но структура данных сама по себе ничего не делает. Чтобы найти элемент, отсортировать список или проложить маршрут, нужен алгоритм — последовательность шагов, которая превращает вход в ответ. А как только появляется несколько способов решить одну задачу, встаёт главный вопрос всей практической информатики: какой из них лучше и на сколько.

Ответ на этот вопрос даёт не секундомер, а особый язык — анализ сложности, чья визитная карточка — загадочная запись O(n log n). Пугающая на вид, по сути она проще, чем кажется: это способ сказать «как быстро растёт стоимость решения, когда растёт объём данных». Понимать её — не привилегия олимпиадников. Это разница между приложением, которое отвечает мгновенно и на десяти, и на десяти миллионах пользователей, и приложением, которое «прекрасно работало на моей машине», а в проде легло. Эта статья — обзорная: интуиция и общая карта. За строгими доказательствами, конкретными алгоритмами сортировки, графами и динамическим программированием идите в глубокий трек (Алгоритмы: обзор).

Что такое алгоритм

Слово идёт от имени персидского математика IX века аль-Хорезми, чьи трактаты о вычислениях по шагам латинизировали как Algoritmi. Но сама идея древнее: алгоритм Евклида для наибольшего общего делителя (~300 г. до н. э.) — это уже алгоритм в полном современном смысле.

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

• Конечность. Алгоритм обязан завершиться. Рецепт «мешай, пока не устанешь» — не алгоритм.
• Однозначность (определённость). На каждом шаге ясно, что делать; никаких «посолить по вкусу». Компьютер не умеет интуичить.
• Выполнимость шагов. Каждый шаг элементарен настолько, что исполнитель заведомо его осилит («сложи два числа», а не «реши, есть ли жизнь на Марсе»).
• Вход и выход. Есть данные на входе и определённый результат на выходе.

Вопрос о том, всякую ли задачу вообще можно решить алгоритмом (спойлер: нет), — это уже теория вычислений (Теория вычислений для всех). Здесь нас интересует другое: среди задач, которые решить можно, как сравнивать способы по цене.

Возьмём детскую задачу — сложить числа от 1 до n. Вот два честных алгоритма:

# Способ А: сложить всё в лоб
def sum_loop(n: int) -> int:
    total = 0
    for i in range(1, n + 1):   # n итераций
        total += i
    return total

# Способ Б: формула Гаусса
def sum_formula(n: int) -> int:
    return n * (n + 1) // 2     # три арифметические операции, всегда

Оба возвращают один и тот же ответ. Но sum_loop при n = 1 000 000 делает миллион сложений, а sum_formula — три операции при любом n. Никакой процессор побыстрее не спасёт первый способ так, как спасает смена алгоритма: удвоили n — у А работы стало вдвое больше, у Б — ни на йоту. Вот это «как меняется работа при росте входа» и есть предмет анализа сложности.

Почему мы не меряем в секундах

Наивная идея — «запусти и засеки время» — обманчива по трём причинам. Секунды зависят от железа (на игровом ПК быстрее, чем на дешёвом телефоне), от языка и компилятора (тот же код на C и на Python отличается в десятки раз), от входных данных (на пустом списке всё мгновенно) и от соседей (антивирус проснулся — цифры поплыли). Замер в секундах описывает один запуск на одной машине, а не сам алгоритм.

Поэтому информатика меряет иначе: считает число элементарных операций как функцию от размера входа n, игнорируя, сколько наносекунд занимает одна операция на конкретном чипе. Размер входа n — это то, от чего зависит работа: длина массива, число вершин графа, количество бит в числе. Важна не абсолютная величина, а закон роста — во сколько раз вырастет работа, если вход вырастет вдвое, вдесятеро, в тысячу раз. Именно закон роста переживает смену железа: квадратичный алгоритм останется квадратичным и на суперкомпьютере — просто «стена» отодвинется чуть дальше по n, но никуда не денется.

Big-O простыми словами

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

1. Отбрасываем константы-множители. 3n и 100n — оба O(n): при росте n вдвое работа растёт вдвое в обоих случаях, а во сколько раз медленнее одна итерация — вопрос железа, не алгоритма.
2. Оставляем только старший член. n² + 5n + 900 — это O(n²): при больших n квадрат раздавит всё остальное, линейная добавка и константа теряются в его тени.
3. Смотрим на большие n (асимптотика). Big-O описывает поведение «в пределе». На крошечных входах он может врать (об этом ниже) — он про то, что будет, когда данных станет много.

Бытовая аналогия. Разница между «выехать на 5 минут раньше» и «поехать по шоссе вместо городских улиц» — это разница между константой и классом сложности. На соседнюю улицу и пешком дойдёшь быстрее, но чем дальше цель, тем сильнее решает выбор дороги, а не пятиминутная фора. Big-O описывает дорогу, а не фору. Формально f(n) = O(g(n)) значит «начиная с некоторого n функция f не превосходит g, умноженной на какую-то константу» — но для интуиции достаточно читать O(g(n)) как «работа растёт примерно как g».

Зоопарк сложностей

Практически все алгоритмы, что вы встретите, попадают в горстку классов роста. Вот они, от блаженно быстрых к безнадёжно медленным, с числом шагов на входах разного размера.

Чтобы цифры ожили, переведём их в секунды на условной машине, делающей миллиард (10⁹) операций в секунду. O(n) при миллионе элементов — тысячные доли секунды. O(n²) при том же миллионе — 10¹² операций — это около 17 минут. А O(2ⁿ) уже при n = 60 требует больше операций, чем секунд прошло с Большого взрыва. Отсюда практический водораздел: O(n log n) и лучше — «масштабируется», O(n²) — «терпимо на тысячах, боль на миллионах», O(2ⁿ) и хуже — «работает только на игрушечных входах, дальше нужна другая идея или приближённое решение». Именно поэтому огромный пласт информатики — это борьба за то, чтобы стащить задачу из экспоненциального класса в полиномиальный.

Два самых частых источника непонимания в этой таблице:

• Логарифм — это «сколько раз делить пополам, пока не останется один». log₂ 1000 000 ≈ 20 означает: миллион можно ополовинить всего 20 раз. Оттого O(log n) почти неотличим от константы на практике — и почему бинарный поиск и деревья так ценят. Основание логарифма в Big-O не пишут: смена основания — это множитель-константа, а их мы отбрасываем. Логарифмы, если подзабылись, — в математическом треке (Математика: обзор).
• O(n log n) — это «пройти данные, и на каждом уровне из log n уровней сделать линейную работу». Так устроены быстрые сортировки: log n раз ополовинить, каждый раз линейно собрать. Доказано, что сортировка сравнением быстрее O(n log n) в общем случае невозможна — это её теоретический предел скорости.

Худший, средний и лучший случай

Одна функция может работать по-разному на разных входах того же размера. Линейный поиск элемента в массиве из n штук: если искомое стоит первым — одна проверка (лучший случай), если последним или его нет — n проверок (худший случай), в среднем — около n/2. Все три — про один и тот же n.

По умолчанию, говоря O(...), обычно имеют в виду худший случай — гарантию «хуже не будет», важную для надёжности систем. Но не всегда: у быстрой сортировки худший случай O(n²) (на неудачном опорном элементе), а средний — O(n log n), и на практике полагаются именно на средний, потому что худший крайне маловероятен. Строго эти границы различают тремя буквами: O — «не быстрее чем» (верхняя граница), Ω (омега) — «не медленнее чем» (нижняя), Θ (тета) — «ровно такого порядка» (и сверху, и снизу). В быту почти всегда говорят O, подразумевая точную оценку; педантичность нужна, когда доказываешь оптимальность.

Пример: линейный против бинарного поиска

Ничто не объясняет Big-O лучше, чем две функции, решающие одну задачу с разной ценой. Задача: найти число в массиве. Наивный способ — идти подряд:

def linear_search(arr: list[int], target: int) -> int:
    for i in range(len(arr)):        # в худшем случае — n итераций
        if arr[i] == target:
            return i
    return -1
# Время: O(n) — в худшем случае проверяем каждый элемент.
# Память: O(1) — храним только счётчик, вход не в счёт.

Но если массив отсортирован, работает трюк «угадай число»: смотрим в середину, и одним сравнением отбрасываем целую половину. Это бинарный поиск. Псевдокод:

BinarySearch(arr, target):
    lo := 0; hi := len(arr) - 1
    while lo <= hi:
        mid := (lo + hi) / 2          # середина окна
        if arr[mid] == target: return mid
        if arr[mid] <  target: lo := mid + 1   # ответ правее — забыть левую половину
        else:                  hi := mid - 1   # ответ левее  — забыть правую половину
    return -1                         # не нашли

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
# Время: O(log n) — окно поиска каждый шаг ополовинивается.
# Память: O(1) — держим только границы lo и hi.

Логику удобно видеть как поток управления — что происходит на каждой итерации цикла:

А вот та же работа «в пространстве данных» — как окно поиска схлопывается на конкретном примере:

Разница ошеломляет именно на больших n. В массиве из миллиарда элементов линейный поиск в худшем случае делает миллиард сравнений; бинарный — тридцать (log₂ 10⁹ ≈ 30). Но обратите внимание на скрытую цену: бинарный поиск требует, чтобы массив был отсортирован. Сортировка стоит O(n log n) — дороже одного линейного прохода. Отсюда практическое правило: если искать предстоит один раз — линейный поиск дешевле (не надо сортировать); если много раз по одним данным — стоит один раз отсортировать (или построить индекс/хеш-таблицу) и потом искать дёшево. Ровно эту арифметику «заплатить за структуру сейчас, чтобы экономить на запросах потом» проделывают индексы в базах данных (БД и хранение).

Время против памяти: вечный размен

У сложности две оси: время (сколько операций) и память (сколько дополнительного места). Часто их можно менять одно на другое — это один из самых глубоких приёмов информатики. Классика — числа Фибоначчи. Наивная рекурсия пересчитывает одни и те же подзадачи заново:

def fib_naive(n: int) -> int:
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# Время: O(2ⁿ) — дерево вызовов ветвится, fib(40) — уже больше миллиарда вызовов.
# Память: O(n) — глубина стека рекурсии.

Стоит запомнить уже посчитанные значения (мемоизация) — и экспонента схлопывается в линию:

def fib_memo(n: int, cache: dict | None = None) -> int:
    if cache is None:
        cache = {}
    if n < 2:
        return n
    if n not in cache:                      # считаем каждое значение один раз
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]
# Время: O(n) — каждое fib(k) вычисляется ровно однажды.
# Память: O(n) — храним таблицу уже посчитанных значений.

Мы потратили немного памяти на кеш и обменяли O(2ⁿ) на O(n) — колоссальный выигрыш. Это идея динамического программирования, и она же — под капотом кеширования вообще: хранить результат, чтобы не пересчитывать. Обратный размен тоже бывает: алгоритм «на месте» (in-place) экономит память ценой лишней работы. Универсального ответа нет — что дороже, время или память, решает контекст (встроенная система с 64 КБ против облака с терабайтами оперативки). Почему «лишняя память» бывает почти бесплатной, а бывает разорительной — станет ясно, когда мы дойдём до иерархии памяти чуть ниже.

Как вообще придумывают алгоритмы

За зоопарком сложностей стоит горстка стратегий проектирования — типовых способов атаковать задачу. Узнавать их полезно: услышав «разделяй и властвуй», вы сразу ожидаете O(n log n).

Каждая из этих ветвей — большая тема с десятками конкретных алгоритмов и строгим анализом; всё это живёт в глубоком треке (Алгоритмы: обзор). Здесь важно другое: выбор стратегии определяет класс сложности, а класс сложности определяет, доживёт ли ваше решение до продакшн-объёмов. Поэтому инженеры мысленно раскладывают кандидатов по двум осям — насколько тяжело это написать и насколько хорошо оно масштабируется:

Смысл картинки: пузырьковая сортировка и линейный поиск живут в правом нижнем углу — их приятно писать, но они годятся лишь для малых данных; быстрая сортировка и хеш-таблицы стоят чуть большего труда, зато масштабируются. Правый нижний угол — не «плохо», а «уместно на своём масштабе»: на списке из десяти элементов пузырёк ничем не хуже, а кода в нём меньше.

Где абстракция Big-O протекает

Big-O — мощная и честная модель, но, как всякая абстракция в этом курсе, она протекает. Знать, где именно, — признак зрелого инженера, а не теоретика.

• Константы, которые мы выбросили, в реальности есть. O(n) с огромной константой может проиграть O(n log n) с крошечной на всех разумных n. Классический пример — сами сортировки: теоретически быстрый merge sort на маленьких массивах уступает «медленной» вставке, поэтому промышленные сортировки (Timsort в Python, introsort в C++) на коротких кусках переключаются на простой алгоритм. Big-O говорит про предел, а вы часто живёте не в пределе.
• Не все «операции» стоят одинаково — из-за памяти. Big-O считает шаги равноценными, а на железе обращение к кешу и к оперативной памяти отличаются в сотню раз, к диску — в миллионы. Алгоритм с худшим Big-O, но дружелюбный к кешу (линейный проход по массиву), легко обгоняет теоретически лучший, но прыгающий по памяти (обход связного списка). Это прямое следствие того, о чём говорит статья (Иерархия памяти): «одна операция» — миф, у памяти своя цена. Сюда же — предсказание ветвлений процессором (Как работает процессор): непредсказуемые if тормозят конвейер, и код с тем же числом операций работает по-разному.
• Малые n. Асимптотика — про большие данные. Если n всегда меньше сотни, разница между O(n) и O(n²) может быть несущественной, а простота кода — важнее. Не оптимизируйте то, что и так мгновенно.
• Амортизация прячет редкие дорогие шаги. У динамического массива вставка в конец — O(1) «в среднем» (амортизированно), но изредка массив переполняется и целиком копируется за O(n). Обычно это неважно, но в системе жёсткого реального времени (тормоза автомобиля) один такой всплеск недопустим — там смотрят на худший случай каждого шага, а не на среднее.
• Худший случай как оружие. Если алгоритм деградирует до O(n²) на специально подобранном входе, злоумышленник может это использовать: подсунуть данные, вызывающие лавину коллизий в хеш-таблице, и положить сервер (algorithmic complexity attack / Hash-DoS). Абстракция «в среднем быстро» протекает в область безопасности (Основы безопасности) — вот почему реальные хеш-функции рандомизируют.

И самая глубокая «протечка» — на уровне того, что вообще осуществимо. Для целого класса важных задач (комбинаторная оптимизация, планирование) не известно полиномиального алгоритма, и есть веские основания считать, что его нет — это знаменитый открытый вопрос P против NP. Для таких задач O(2ⁿ) — не лень программиста, а, возможно, фундаментальная стена, и на практике довольствуются приближёнными или эвристическими решениями. Где проходит граница вычислимого и разрешимого — тема теоретического трека (Теория вычислений).

Как это применяют на практике

• Оценивают «на салфетке» до написания кода. Прежде чем реализовывать, инженер прикидывает: сколько данных ожидается и какой класс сложности это выдержит. Вложенный цикл по всем парам пользователей? При миллионе пользователей это 10¹² операций — сразу нет, нужна другая идея.
• Читают Big-O в документации структур данных. Выбор «список против словаря против дерева» — это по сути выбор таблицы сложностей операций (Структуры данных: обзор). Нужен частый поиск по ключу — берут хеш-таблицу за её O(1); нужен упорядоченный обход — дерево за O(log n).
• Профилируют, а не гадают. Big-O показывает, что станет узким местом при росте, но какая из O(n)-функций реально съедает время здесь и сейчас — покажет только профайлер на настоящих данных. Правило: сперва измерь, потом оптимизируй то, что действительно горячо, и не раньше.
• Проходят собеседования. Задачи на алгоритмы и вопрос «а какая тут сложность?» — стандарт технических интервью именно потому, что это проверка на умение думать о цене решения.

Типичные заблуждения

• «Big-O — это про скорость в секундах». Нет, это про закон роста. O(1)-алгоритм может быть медленнее O(n)-алгоритма на конкретном малом входе — Big-O говорит лишь, кто победит, когда данных станет достаточно много.
• «Всегда нужен алгоритм с лучшим Big-O». Нет. На малых n и с учётом констант, читаемости и памяти простое O(n²)-решение часто предпочтительнее хитрого O(n log n). Оптимальность Big-O — не самоцель, а инструмент под масштаб задачи.
• «O(2n) хуже, чем O(n)». Это одно и то же: O(2n) = O(n), константу отбрасывают. Точно так же O(n/2) = O(n) и O(100) = O(1).
• «Быстрее железо решит проблему сложности». Апгрейд сдвигает стену на пару шагов по n; смена класса сложности отодвигает её на порядки. Против экспоненты никакое железо не помогает.
• «Big-O учитывает всё». Он молчит про константы, кеш, память и реальные данные — потому и нужен профайлер. Big-O — это первая, грубая, но незаменимая оценка, а не последнее слово.

Мини-итог

Алгоритм — это конечный однозначный рецепт превращения входа в ответ, а сложность — язык, на котором мы обсуждаем его цену, не привязываясь к железу. Вместо секунд считают, как растёт число операций с ростом входа n, и записывают закон роста через O(...), отбрасывая константы и младшие члены. Горстка классов — от блаженной O(1) и O(log n) через рабочие O(n) и O(n log n) к опасным O(n²) и безнадёжным O(2ⁿ) — покрывает почти всё, и переход между классами (бинарный поиск вместо линейного, мемоизация вместо голой рекурсии) решает несравнимо больше, чем ускорение процессора. Big-O — не академическая формальность, а рабочий прибор: он подсказывает, доживёт ли идея до продакшн-масштаба, ещё до того как написана первая строка. И он же честно протекает — на малых n, на константах, на памяти и кеше, — поэтому венчает анализ всегда измерение на настоящих данных.

Источники

• Thomas H. Cormen et al. «Introduction to Algorithms» (CLRS) — канонический учебник по анализу алгоритмов: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Donald Knuth. «The Art of Computer Programming» — истоки строгого анализа: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
• Steven Skiena. «The Algorithm Design Manual» — практичный взгляд с «зоопарком» задач: https://www.algorist.com/
• Big-O Cheat Sheet — таблицы сложностей структур данных и алгоритмов: https://www.bigocheatsheet.com/

Что дальше

Мы прошли путь снизу вверх: биты, логика, процессор, память, код, ОС, структуры данных и, наконец, алгоритмы — всё это пока происходило внутри одной машины. Но настоящая мощь появляется, когда машины начинают общаться. Следующая статья — про то, как они это делают: сети, модель OSI и стек протоколов TCP/IP, благодаря которым сообщение долетает с вашего ноутбука до сервера на другом континенте.

Как компьютеры общаются: сети, модель OSI, стек TCP/IP