Асимптотика: O-нотация и оценка «уложусь ли по времени»

Главный навык олимпиадника: по размеру входа предсказать, какой алгоритм пройдёт по времени, не написав ни строчки.

O-большое (асимптотическая сложность) — оценка того, как растёт число операций алгоритма с ростом размера входа n, без учёта констант и младших слагаемых.

Зачем это нужно

Представь, что ты придумал решение и уже хочешь его кодить. Стоп. Сначала ответь на один вопрос: сколько примерно операций оно сделает на максимальном тесте? Если ответ больше, чем процессор успеет за 1–2 секунды, ты напишешь правильный, но бесполезный код и получишь TLE. Умение в уме оценить сложность до написания кода экономит часы и отделяет сильных участников от слабых. Асимптотика — это не теория ради теории, а инструмент принятия решений «какой алгоритм здесь вообще имеет смысл».

Идея «на пальцах»

O-большое отвечает на вопрос «как быстро растёт время?», игнорируя детали. Если алгоритм делает 3n + 5 операций — это O(n): при удвоении n время примерно удваивается. Если 2n^2 + 100n — это O(n^2): при удвоении n время вырастает вчетверо. Константы (3, 2, 100) отбрасываются, потому что на больших n решает именно форма роста, а не множители. Нам не важно, 2 секунды или 4 — важно, что O(n^2) при n=10^6 — это 10^12 операций, и это безнадёжно.

Лестница сложностей

Запомни этот порядок от лучшего к худшему — это твоя шкала.

Посмотрим на конкретные числа для n = 10^6 — разница огромна.

import math

n = 1_000_000
print("O(1):       ", 1)
print("O(log n):   ", round(math.log2(n)))
print("O(n):       ", n)
print("O(n log n): ", round(n * math.log2(n)))
print("O(n^2):     ", n * n)

Здесь видно, что O(n log n) для миллиона — всего ~2·10^7 операций (мгновенно), а O(n^2) — 10^12 (часы). Логарифм же превращает миллион в каких-то двадцать шагов — поэтому бинарный поиск так быстр.

Вывод:

O(1):        1
O(log n):    20
O(n):        1000000
O(n log n):  19931569
O(n^2):      1000000000000

Главное правило прикидки

За 1–2 секунды современный судья выполняет порядка 10^8–10^9 простых операций на C++. На Python считай скромнее — 10^7–10^8, потому что язык интерпретируемый. Отсюда рабочая эвристика: число операций твоего алгоритма должно быть примерно ≤ 10^8. Подставь максимальное n в формулу сложности — и сравни.

Что значит «растёт быстрее»

Чтобы прочувствовать разницу классов, посмотрим, как меняется объём работы при увеличении n. Линейная сложность растёт пропорционально, квадратичная — как квадрат, а экспонента взрывается так, что при n=40 опережает всё на порядки. Эта таблица — наглядное «почему» за всеми правилами урока.

print(f'{"n":>6}{"O(n)":>12}{"O(n^2)":>16}{"O(2^n)":>18}')
for n in [10, 20, 40]:
    print(f'{n:>6}{n:>12}{n * n:>16}{2 ** n:>18}')

Обрати внимание на последнюю колонку: при переходе от n=20 к n=40 значение O(n) просто удвоилось, O(n^2) выросло вчетверо, а O(2^n) — в миллион раз. Вот почему экспоненциальные решения годятся лишь для крошечных n, а для больших нужен полиномиальный алгоритм.

Вывод:

     n        O(n)          O(n^2)            O(2^n)
    10          10             100              1024
    20          20             400           1048576
    40          40            1600     1099511627776

Обратный приём: читаем сложность из ограничений

Самое мощное — это идти от ограничений к алгоритму. Размер n в условии почти всегда подсказывает нужную асимптотику. Эту таблицу полезно знать наизусть.

Видишь n ≤ 20 — почти наверняка ждут перебор подмножеств за O(2^n). Видишь n = 10^5 — квадрат не пройдёт, нужен O(n log n). Это сужает поиск идеи в разы.

Тонкости, на которых ошибаются

• Сложность — про худший случай. «Обычно быстро» не считается: судья найдёт злой тест.
• Память тоже имеет асимптотику. Массив n×n при n=10^5 — это 10^10 ячеек, никакой памяти не хватит (MLE).
• Константа иногда решает. Два алгоритма O(n log n) могут отличаться в 5 раз по скорости; на грани TLE это важно, особенно в Python.
• Логарифм почти бесплатен. Домножить алгоритм на log n (например, обернуть в бинпоиск) — обычно не страшно: log n ≈ 20 даже для миллиона.

Попробуй сам

Дано n ≤ 2·10^5 и нужно для каждого элемента массива найти ближайший справа больший. Прикинь: квадрат — это (2·10^5)^2 = 4·10^10, не пройдёт. Значит, нужно O(n) или O(n log n) — здесь работает стек за O(n) (мы вернёмся к этому в разделе про структуры данных). Видишь, как ограничение само подсказало класс решения?

Итог

• O-большое описывает скорость роста времени, отбрасывая константы и младшие члены.
• Ориентир: алгоритм должен делать ≤ ~10^8 операций (на Python — скромнее).
• Ограничение на n подсказывает нужную сложность: n=20 → 2^n, n=5000 → n^2, n=10^5 → n log n.
• Оценивай сложность до кодинга — это экономит время и спасает от TLE.