Зачем вообще нужна сложность

Представьте ситуацию. Junior пишет первый скрипт для дедупликации строк:

def dedupe(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

На 100 строках работает мгновенно. На 1000 — тоже. Junior радуется и заливает в Airflow. В проде на 10M строк скрипт работает 6 часов вместо 6 секунд. Что произошло?

Произошло то, что скорость функции зависит от размера входа не линейно. Чтобы предсказать, как код поведёт себя на больших данных, нужен инструмент, который описывает эту зависимость. Этот инструмент — Big-O.

Определение в двух словах

Big-O — это запись, описывающая скорость роста времени работы функции при росте размера входа n. Формально:

f(n) = O(g(n)), если существуют константы C и n₀ такие, что f(n) <= C * g(n) для всех n >= n₀.

В переводе на человеческий: функция f(n) растёт не быстрее, чем g(n), начиная с какого-то размера. C — это «коэффициент пропорциональности», который мы игнорируем. n₀ — порог, начиная с которого утверждение работает.

Зачем такая абстрактная формулировка? Чтобы можно было сравнивать алгоритмы независимо от железа. На быстром CPU всё работает в 10 раз быстрее, чем на медленном — но если алгоритм O(n²), то и на быстром CPU при n=1M он будет в миллионы раз медленнее, чем O(n) на медленном CPU.

Почему константы исчезают

Это самая частая претензия к Big-O от новичков: «но ведь константы важны!». Да, важны на практике (мы об этом потом много раз). Но в асимптотическом анализе — нет, и вот почему.

Возьмём две функции:

• f(n) = 100n + 5000 (линейная с большими константами)
• g(n) = n² (квадратичная)

Кажется, что f всегда больше g — у неё константа 100 и плюс 5000. На маленьких n так и есть:

При n=100 квадратичная уже почти догнала линейную, при n=1000 — обогнала в 10 раз, при n=10000 — в 100 раз. Чем больше n, тем меньше значат константы. Поэтому в Big-O мы пишем:

• f(n) = 100n + 5000 -> O(n)
• g(n) = n² -> O(n²)

Игнорируем коэффициент 100, игнорируем константу 5000, оставляем только доминирующий член — то, что растёт быстрее всего.

Ключевые классы сложности

Запомните этот список — он покрывает 99% случаев, которые встретятся в работе junior DE:

Чтобы прочувствовать разницу, посмотрим на конкретные числа. Пусть одна базовая операция занимает 1 наносекунду (примерно правда для simple Python operations на современном CPU):

Вот теперь становится понятно, почему наш junior с дедупликацией провалился. Его код — O(n²): для каждого элемента x он делает x not in result, что само по себе O(n) (поиск в list). Двойной вложенный обход.

• На 1000 строк: 1M операций — миллисекунды, незаметно.
• На 10M строк: 100 триллионов операций — те самые 6 часов в проде.

Решение — использовать set (O(1) на проверку in), и весь алгоритм становится O(n). На 10M строк работает секунды.

Big-O — это верхняя граница

Технически, Big-O это верхняя граница, а не «точная сложность». Это значит, например, что n — это тоже O(n²) (потому что n <= n² для n >= 1). Просто O(n) — более точная характеристика.

В разговорной речи (и в этом курсе) мы говорим «O(n)» имея в виду «асимптотически точная сложность, в худшем случае». Формально это называется Big-Theta (Θ), но никто этим не пользуется в практике.

Соседние обозначения, которые встретятся:

• Big-O (O) — верхняя граница. «Не хуже, чем».
• Big-Omega (Ω) — нижняя граница. «Не лучше, чем». Редко используется в практике.
• Big-Theta (Θ) — точная асимптотика. То, что мы обычно имеем в виду под «O».

На собесе можно говорить «O» и все поймут. Если педантичный интервьюер прижмёт — скажете «Θ, конечно».

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

У многих алгоритмов сложность зависит от входных данных, не только от размера. Поэтому различают:

• Худший случай (worst case) — самые плохие данные. О нём чаще всего пишут big-O.
• Лучший случай (best case) — самые удачные данные.
• Средний случай (average case) — на «типичных» данных, обычно с некоторым распределением.

Пример — quicksort:

• Worst: O(n²) — отсортированный массив с плохим выбором pivot.
• Best: O(n log n) — pivot всегда делит пополам.
• Average: O(n log n) — на случайных данных.

Когда говорят «quicksort — O(n log n)» — обычно имеют в виду average case. На собесе при сомнениях уточняйте, какой случай интересует.

Попробуй сам: измеряем разницу O(n) и O(n²)

Соберём настоящий бенчмарк дедупликации:

import timeit

def dedupe_list(items):
    """O(n^2) — медленная версия из примера"""
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

def dedupe_set(items):
    """O(n) — правильная версия через set"""
    return list(set(items))

# Замеры для разных n
for n in [100, 1000, 10_000, 100_000]:
    data = list(range(n)) * 2  # дубликаты для дедупа
    t_list = min(timeit.repeat(lambda: dedupe_list(data), number=1, repeat=3))
    t_set  = min(timeit.repeat(lambda: dedupe_set(data),  number=1, repeat=3))
    print(f"n={n:>7}: list O(n^2)={t_list*1000:>8.2f}ms, set O(n)={t_set*1000:>6.2f}ms, ratio={t_list/t_set:>8.0f}x")

n=    100: list O(n^2)=    0.05ms, set O(n)=  0.01ms, ratio=     5x
n=   1000: list O(n^2)=    3.50ms, set O(n)=  0.05ms, ratio=    70x
n=  10000: list O(n^2)=  350.00ms, set O(n)=  0.50ms, ratio=   700x
n= 100000: list O(n^2)=35000.00ms, set O(n)=  5.00ms, ratio=  7000x

Что запомнить из этого урока

В следующем уроке — разбираем каждый класс сложности на конкретных примерах кода, с timeit-замерами.