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

> Алгоритм — конечная последовательность шагов для решения задачи; O-нотация описывает, как растут время работы и память алгоритма с ростом размера входных данных.

Источник: https://llmdocs.ru/wiki/big-o/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Алгоритм**: конечная последовательность однозначных шагов
- **Происхождение слова**: от имени аль-Хорезми (IX век)
- **O-нотация**: верхняя граница роста функции
- **Родственные обозначения**: Ω (нижняя граница), Θ (точная оценка)
- **Авторы нотации**: Пауль Бахман (1894), Эдмунд Ландау; в информатике популяризировал Дональд Кнут
- **Виды оценок**: худший, средний, лучший случай, амортизированная
**Алгоритм** — конечная последовательность однозначных шагов, которая по входным данным за конечное время получает результат: рецепт сортировки списка, поиска пути на карте или проверки пароля. Слово происходит от латинизированного имени персидского математика 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» часто говорят, имея в виду Θ.

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

| Сложность | Название | Пример | При n = 1 000 000 |
|---|---|---|---|
| O(1) | константная | доступ к элементу массива по индексу, поиск в [хеш-таблице](https://llmdocs.ru/wiki/hash-table.md) | 1 |
| O(log n) | логарифмическая | двоичный поиск, поиск в [сбалансированном дереве](https://llmdocs.ru/wiki/b-tree.md) | ≈ 20 |
| O(n) | линейная | проход по списку, поиск максимума | 10⁶ |
| O(n log n) | линейно-логарифмическая | эффективная [сортировка](https://llmdocs.ru/wiki/sorting.md) (слиянием, Timsort) | ≈ 2·10⁷ |
| O(n²) | квадратичная | вложенный цикл, сортировка пузырьком | 10¹² |
| O(2ⁿ) | экспоненциальная | перебор всех подмножеств | непосильно |
| O(n!) | факториальная | перебор всех перестановок (задача коммивояжёра) | непосильно |

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

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

```python
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](https://llmdocs.ru/wiki/python.md) проверка `x in list` — это O(n), а `x in set` — O(1) в среднем; вставка в начало списка `list.insert(0, x)` — O(n), а в `collections.deque` — O(1). Сложность операций стандартных структур данных Python сведена в таблицу на Python Wiki.[3] То же относится к базам данных: запрос без [индекса](https://llmdocs.ru/wiki/database-index.md) сканирует всю таблицу — O(n), — а с индексом на B-дереве — O(log n).

## Виды оценок

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

## Ограничения

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

## См. также

- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)
- [Сортировка](https://llmdocs.ru/wiki/sorting.md)
- [Хеш-таблица](https://llmdocs.ru/wiki/hash-table.md)
- [Рекурсия](https://llmdocs.ru/wiki/recursion.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)

## Источники

1. [D. Knuth — Big Omicron and big Omega and big Theta (SIGACT News, 1976)](https://dl.acm.org/doi/10.1145/1008328.1008329)
2. [T. Cormen et al. — Introduction to Algorithms, 4th ed. (MIT Press)](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
3. [Python Wiki — TimeComplexity](https://wiki.python.org/moin/TimeComplexity)
4. [MIT OpenCourseWare — Introduction to Algorithms (6.006)](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/)
5. [Big-O Cheat Sheet](https://www.bigocheatsheet.com/)