O-нотация и оценка временной сложности

Когда говорят, что один алгоритм «быстрее» другого, обычно имеют в виду не конкретные секунды — они зависят от процессора, языка, компилятора. Имеют в виду то, как время растёт с ростом данных. Именно для этого и придумали O-нотацию.

O-нотация: формальный смысл и правила записи

Представь, что ты написал функцию и замерил: на 1 000 элементов она делает ровно 3 000 + 7 операций. На 1 000 000 — 3 000 007. Разница в 7 операций при таком масштабе уже не имеет смысла. И коэффициент 3 тоже: он зависит от того, что считать «операцией» — инструкцию процессора или строку Python.

O-нотация отвечает на другой вопрос: с какой скоростью растёт время выполнения при увеличении n? Формально, f(n) = O(g(n)) означает, что начиная с некоторого n₀ функция f не превышает c · g(n) для какой-то константы c. Это верхняя граница роста — не точный счёт операций, а гарантия того, что хуже определённого темпа не будет.

Отсюда сразу вытекают два правила записи.

Константы отбрасываются. Если алгоритм выполняет 5n операций — пишем O(n). Константа 5 поглощается той самой c из определения и не меняет класс роста.

Слагаемые меньшего порядка отбрасываются. Выражение 3n² + 5n + 12 записывается как O(n²). Когда n становится большим, вклад 5n и 12 относительно 3n² стремится к нулю. При n = 1 000: 3n² = 3 000 000, а 5n = 5 000, то есть примерно 0,17% от квадратичного члена. При n = 1 000 000 доля линейного члена составляет уже примерно 0,00017%.

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

Основные классы сложности и доминирующий член

Типичные скорости роста образуют ряд от константной до квадратичной.

O(1) — число элементарных действий не зависит от n. Обращение к элементу списка по индексу (a[i]) выполняется за O(1). Вставка в словарь имеет ожидаемую амортизированную сложность O(1), но в худшем случае одна операция может занять O(n), например из-за большого числа коллизий или изменения размера таблицы.

O(log n) — каждый шаг вдвое сокращает задачу. Классический пример — бинарный поиск: ищем в миллионе элементов не более 20 шагов, потому что 2²⁰ > 10⁶.

O(n) — один проход по данным. Найти максимум в несортированном списке, посчитать сумму — линейно.

O(n log n) — характерен для эффективных алгоритмов сортировки: merge sort, timsort (который использует Python по умолчанию). Например, у merge sort есть O(log n) уровней разбиения, а работа на каждом уровне занимает O(n).

O(n²) — два вложенных цикла по n. Часто встречается в наивных алгоритмах: сравнение каждого элемента с каждым.

Порядок типичных скоростей роста: O(1) < O(log n) < O(n) < O(n log n) < O(n²). Каждый следующий класс растёт принципиально быстрее предыдущего при больших n.

В сумме нескольких слагаемых итог определяет доминирующий член. Предположим, анализ алгоритма дал: 2n² + 8n + 15. Итоговая оценка — O(n²). Правило простое: берём слагаемое с наибольшим темпом роста и отбрасываем его коэффициент. Остальные слагаемые игнорируем.

Проверить интуицию можно числами. При n = 100: 2n² = 20 000, а сумма 8n + 15 = 815 — это чуть больше 4% от 2n². При n = 1 000 — уже около 0,4%. При росте n вклад 8n стремится к нулю относительно 2n². Поэтому мы и оставляем только доминирующий член — он и определяет асимптотическое поведение алгоритма при больших входах.

Процедура оценки сложности по коду Python

Шаг 1: определи переменную роста. Что такое n в конкретном контексте? Длина входного списка, количество строк в файле, размер числа — это нужно зафиксировать до начала анализа.

Шаг 2: одиночный цикл.

for i in range(n):
    # O(1) операции
    pass

Если тело цикла выполняется за константное время, весь цикл — O(n). Ровно n итераций, каждая стоит O(1).

Шаг 3: два последовательных цикла.

for i in range(n):
    pass  # O(1)

for j in range(n):
    pass  # O(1)

O(n) + O(n) = O(2n) = O(n). Константа 2 отбрасывается — это всё ещё линейный алгоритм. Последовательные циклы складываются, но доминирующий член остаётся тем же.

Шаг 4: вложенные циклы.

for i in range(n):
    for j in range(n):
        pass  # O(1)

Внутренний цикл выполняет n итераций для каждого значения i. Итого: n × n = n² выполнений тела — O(n²).

Шаг 5: логарифмический счётчик.

i = 1
while i < n:
    i *= 2  # удваиваем

Цикл останавливается, когда i впервые достигает или превышает n. При целочисленном n > 1 это ровно ⌈log₂ n⌉ удвоений; при n <= 1 итераций нет. Поэтому сложность — O(log n). Для цикла i = n; while i > 1: i //= 2 при целом n >= 1 точное число итераций равно ⌊log₂ n⌋.

Шаг 6: вложение разных классов.

i = 1
while i < n:        # O(log n) итераций
    for j in range(n):  # O(n) на каждой итерации
        pass
    i *= 2

При n > 1 внешний цикл делает ровно ⌈log₂ n⌉ итераций, на каждой — n работы. Перемножаем: O(n log n).

Если внутренний цикл на каждой итерации внешнего выполняет одинаковый объём работы, их сложности перемножаются. Последовательные блоки складываются, после чего берётся доминирующий член.

Линейный, квадратичный и логарифмический рост в коде

Фрагмент 1.

def find_max(a: list) -> int:
    max_val = a[0]
    for x in a:
        if x > max_val:
            max_val = x
    return max_val

n — длина непустого списка a. Цикл выполняется ровно n раз и делает n сравнений; инициализация, возможное присваивание на каждой итерации и возврат добавляют лишь константную работу на итерацию. Поэтому и в лучшем, и в худшем случае функция работает за линейное время O(n).

---

Фрагмент 2.

def has_duplicate(a: list) -> bool:
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

n = len(a). В лучшем случае первые два элемента равны и функция завершится после одного сравнения, то есть за O(1). В худшем случае дубликатов нет или совпадение проверяется последним. Тогда внутренний цикл при фиксированном i выполняет n - i - 1 сравнений, и их точное число равно:

(n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2

Доминирующий член n²/2, коэффициент 1/2 отбрасываем: сложность в худшем случае — O(n²).

---

Фрагмент 3.

def binary_search(a: list, target: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

n = len(a), а список a отсортирован по возрастанию. Если средний элемент сразу равен target, лучший случай занимает O(1). В худшем случае на каждой итерации диапазон поиска делится пополам: n → n/2 → n/4 → .... Для n >= 1 цикл выполнится не более ⌊log₂ n⌋ + 1 раз. Тело цикла — O(1), поэтому сложность в худшем случае — O(log n).

---

Фрагмент 4.

def demo(n: int) -> None:
    # Блок A: два последовательных цикла
    for i in range(n):
        pass  # абстрактное O(1)-тело
    for i in range(n):
        pass  # абстрактное O(1)-тело

    # Блок B: вложенные циклы
    for i in range(n):
        for j in range(i):
            pass  # абстрактное O(1)-тело

n — неотрицательный параметр функции. Здесь используется pass, потому что стоимость print нельзя в общем случае считать O(1): она зависит от длины представления значения и от системы вывода. Блок A выполняет абстрактное тело n + n = 2n раз, то есть имеет сложность O(n). Блок B при фиксированном i выполняет тело i раз. Сумма: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 — доминирующий член n²/2, коэффициент отбрасываем — O(n²).

Суммируем блоки: O(n) + O(n²). Доминирует n² → итоговая оценка функции O(n²).