Оценка сложности алгоритмов: O-большое
Что означает O(n), O(log n), O(n²), как считать сложность по коду, таблица сложностей типовых операций и структур данных.
O-большое отвечает на вопрос: как растёт время работы, если размер входа n растёт. Константы и младшие слагаемые отбрасываются — 3n² + 100n + 7 это O(n²), потому что при больших n квадрат съедает всё остальное.
Как считать по коду
- Последовательные блоки — берём максимум: O(n) + O(n²) = O(n²).
- Вложенные циклы — перемножаем: два цикла по n дают O(n²).
- Деление задачи пополам на каждом шаге — это log n (бинарный поиск).
- Рекурсия: считаем количество вызовов, а не строк кода.
# O(n) — один проход
for x in a:
s += x
# O(n^2) — вложенные циклы
for i in range(n):
for j in range(n):
m[i][j] = i * j
# O(log n) — область поиска сокращается вдвое
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
...Порядки роста от лучшего к худшему
| Сложность | Название | Пример |
|---|---|---|
| O(1) | Константная | Доступ к элементу массива по индексу |
| O(log n) | Логарифмическая | Бинарный поиск, вставка в сбалансированное дерево |
| O(n) | Линейная | Проход по массиву, поиск максимума |
| O(n log n) | Линейно-логарифмическая | Быстрая сортировка, сортировка слиянием |
| O(n²) | Квадратичная | Пузырёк, перебор всех пар |
| O(2ⁿ) | Экспоненциальная | Полный перебор подмножеств |
| O(n!) | Факториальная | Перебор всех перестановок (задача коммивояжёра в лоб) |
Сложность операций над структурами
| Структура | Поиск | Вставка | Удаление |
|---|---|---|---|
| Массив (неотсортированный) | O(n) | O(1) в конец | O(n) |
| Отсортированный массив | O(log n) | O(n) | O(n) |
| Связный список | O(n) | O(1) | O(1) при известном узле |
| Хеш-таблица | O(1) в среднем | O(1) в среднем | O(1) в среднем |
| Сбалансированное дерево | O(log n) | O(log n) | O(log n) |
| Куча (heap) | O(n) | O(log n) | O(log n) для минимума |
Лучший, средний и худший случай
У быстрой сортировки средний случай O(n log n), а худший — O(n²), когда опорный элемент каждый раз оказывается крайним. Поэтому на защите корректно говорить не «сложность quicksort», а «сложность в среднем/в худшем случае» — это как раз то различие, которое проверяют вопросом.
Память тоже считают
Пространственная сложность — сколько дополнительной памяти нужно сверх входных данных. Сортировка слиянием быстрая, но требует O(n) дополнительной памяти, а пирамидальная работает на месте с O(1). В задачах с ограничением по памяти это решающий аргумент.
Частые вопросы
Отбрасывать ли константу 1/2 в n²/2?
Да, в асимптотике константный множитель не влияет на порядок роста. Но в реальном сравнении двух O(n log n)-алгоритмов константа решает.
Что такое амортизированная сложность?
Средняя стоимость операции в длинной серии. У динамического массива вставка иногда стоит O(n) из-за перевыделения, но амортизированно — O(1).