Алгоритм и O-нотация

Алгоритм — конечная последовательность однозначных шагов, которая по входным данным за конечное время получает результат: рецепт сортировки списка, поиска пути на карте или проверки пароля. Слово происходит от латинизированного имени персидского математика IX века аль-Хорезми. O-нотация («О большое», англ. Big O) — способ описать, как растут время работы или потребление памяти алгоритма при увеличении размера входных данных n, отбрасывая константы и несущественные слагаемые.

O-нотация — общий язык программистов для сравнения решений: «поиск по хеш-таблице — O(1), сортировка — O(n log n), вложенный цикл по списку — O(n²)».

Зачем нужна асимптотическая оценка

Время работы программы зависит от процессора, языка и данных, поэтому сравнивать алгоритмы в секундах неудобно. Важнее, как время растёт: алгоритм O(n²) на 1000 элементах может работать быстрее алгоритма O(n log n), но на миллионе элементов разница составит десятки тысяч раз. O-нотация отвечает на вопрос «что будет, когда данных станет в 10 или в 1000 раз больше».

Определение

Говорят, что функция f(n) есть O(g(n)), если начиная с некоторого n₀ она не превосходит c·g(n) для некоторой константы c. Иными словами, g — верхняя граница роста f с точностью до константы. Поэтому 3n² + 5n + 100 — это O(n²): при больших n старшее слагаемое доминирует, а константы не важны.

Родственные обозначения: Ω (омега) — нижняя граница, Θ (тета) — точная оценка сверху и снизу. Их строгое использование в информатике предложил Дональд Кнут в 1976 году.^[1] В обиходе «O» часто говорят, имея в виду Θ.

Типичные классы сложности

Как оценивать код

• Последовательные шаги складываются, и остаётся самый тяжёлый: O(n) + O(n²) = O(n²).
• Вложенные циклы перемножаются: цикл по n внутри цикла по n даёт O(n²).
• Деление задачи пополам на каждом шаге даёт логарифм.
• Рекурсивные алгоритмы оцениваются через рекуррентные соотношения, например T(n) = 2T(n/2) + O(n) даёт O(n log n) для сортировки слиянием.^[2]

def has_duplicates_slow(items):          # O(n²): каждый с каждым
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicates_fast(items):          # O(n) по времени, O(n) по памяти
    seen = set()
    for x in items:
        if x in seen:                    # проверка в множестве — O(1) в среднем
            return True
        seen.add(x)
    return False

Второй вариант — классический обмен памяти на время: дополнительное множество позволяет избавиться от вложенного цикла.

Скрытая сложность

Операции, выглядящие как один шаг, могут быть дорогими. В Python проверка x in list — это O(n), а x in set — O(1) в среднем; вставка в начало списка list.insert(0, x) — O(n), а в collections.deque — O(1). Сложность операций стандартных структур данных Python сведена в таблицу на Python Wiki.^[3] То же относится к базам данных: запрос без индекса сканирует всю таблицу — O(n), — а с индексом на B-дереве — O(log n).

Виды оценок

• Худший случай — гарантия: быстрая сортировка в худшем случае O(n²).
• Средний случай — ожидаемое время на типичных данных: быстрая сортировка в среднем O(n log n).
• Амортизированная оценка — среднее по последовательности операций: добавление в динамический массив иногда требует копирования, но в среднем стоит O(1).
• Сложность по памяти — сколько дополнительной памяти требуется, оценивается так же.

Ограничения

O-нотация игнорирует константы, а на практике они важны: для небольших n простой алгоритм O(n²) часто быстрее сложного O(n log n), поэтому, например, Timsort сортирует короткие участки вставками. Влияют также кэши процессора (Кэш (вычисления)), распределение данных и ввод-вывод. Асимптотика подсказывает, где искать проблему, а окончательный ответ даёт измерение. Систематически алгоритмы изучают по учебнику Кормена и соавторов и курсам вроде MIT 6.006.^[4] Краткая шпаргалка по сложности популярных алгоритмов — Big-O Cheat Sheet.^[5]

См. также

• Структуры данных
• Сортировка
• Хеш-таблица
• Рекурсия
• Дерево и граф

Источники

1. D. Knuth — Big Omicron and big Omega and big Theta (SIGACT News, 1976)
2. T. Cormen et al. — Introduction to Algorithms, 4th ed. (MIT Press)
3. Python Wiki — TimeComplexity
4. MIT OpenCourseWare — Introduction to Algorithms (6.006)
5. Big-O Cheat Sheet