Big-O и сложность алгоритмов
Шпаргалка по Big-O: временная и пространственная сложность, классы O(1)…O(n!) с примерами кода, правила оценки, таблицы по структурам данных и сортировкам.
Big-O — это язык, на котором программисты описывают, как быстро растёт время работы или потребление памяти алгоритма при увеличении объёма входных данных. Эта шпаргалка собирает основные классы сложности, правила оценки, таблицы по структурам данных и алгоритмам сортировки, а также наглядное сравнение «n против числа операций».
Что такое сложность алгоритма
Временная сложность описывает, как растёт количество операций (а значит, и время работы) алгоритма при увеличении размера входа n. Пространственная сложность описывает, как растёт объём дополнительной памяти, которую алгоритм запрашивает помимо самих входных данных.
Главная идея: нас интересует не точное число операций на конкретной машине, а скорость роста. Алгоритм, делающий 2n + 100 операций, и алгоритм, делающий 5n операций, оба линейны — при больших n они ведут себя одинаково «по характеру роста». Именно эту «форму роста» и фиксирует нотация O().
Обычно различают три случая:
- Худший случай (worst case) — верхняя граница, гарантия «не медленнее». Чаще всего именно его и записывают через O().
- Средний случай (average case) — ожидаемое поведение на типичных данных.
- Лучший случай (best case) — нижняя граница, когда всё складывается идеально.
Нотация O(): что она означает
Запись O(f(n)) читается как «порядка f от n» и означает, что начиная с некоторого размера входа число операций не превосходит C · f(n) для какой-то константы C. То есть O() задаёт асимптотическую верхнюю границу роста.
Рядом с «большим O» существуют и другие обозначения, но на практике чаще всего нужно именно O():
| Нотация | Смысл | Аналогия |
|---|---|---|
| O(f(n)) | Верхняя граница («не хуже, чем») | ≤ |
| Ω(f(n)) | Нижняя граница («не лучше, чем») | ≥ |
| Θ(f(n)) | Точная граница (и сверху, и снизу) | = |
Когда говорят «алгоритм за O(n²)», почти всегда имеют в виду худший случай и асимптотику при больших n.
Основные классы сложности
Ниже — основные классы от самого быстрого к самому медленному, с примерами кода и пояснением.
O(1) — константная
Время не зависит от размера входа. Сколько бы элементов ни было, выполняется фиксированное число операций.
def get_first(arr):
# Доступ к элементу по индексу — всегда одна операция
return arr[0]
def is_even(n):
return n % 2 == 0Примеры: доступ к элементу массива по индексу, вставка/чтение в хеш-таблице, добавление в конец стека.
O(log n) — логарифмическая
На каждом шаге задача уменьшается в несколько раз (обычно вдвое). Чтобы дойти до ответа, нужно примерно log₂(n) шагов. Для миллиона элементов это всего около 20 шагов.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # делим диапазон пополам
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Примеры: бинарный поиск в отсортированном массиве, операции в сбалансированном дереве поиска.
O(n) — линейная
Число операций растёт пропорционально размеру входа: вдвое больше данных — вдвое больше работы.
def find_max(arr):
best = arr[0]
for x in arr: # один проход по всем элементам
if x > best:
best = x
return bestПримеры: линейный поиск, подсчёт суммы элементов, один проход по списку.
O(n log n) — линейно-логарифмическая
Типичная сложность хороших алгоритмов сортировки: линейный проход, повторённый log n раз. Практически это «потолок» для эффективной сортировки сравнением.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # log n уровней рекурсии,
right = merge_sort(arr[mid:]) # на каждом — слияние за O(n)
return merge(left, right)Примеры: быстрая сортировка (в среднем), сортировка слиянием, сортировка кучей.
O(n²) — квадратичная
Вложенный цикл по тем же данным. Для 1 000 элементов это уже миллион операций — заметно медленно.
def has_duplicate(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)): # вложенный цикл
if arr[i] == arr[j]:
return True
return FalseПримеры: пузырьковая сортировка, сортировка вставками/выбором, наивное сравнение всех пар.
O(2ⁿ) — экспоненциальная
Каждый дополнительный элемент удваивает объём работы. Применимо только для очень маленьких n.
def fib(n):
# Наивная рекурсия: дерево вызовов растёт экспоненциально
if n < 2:
return n
return fib(n - 1) + fib(n - 2)Примеры: перебор всех подмножеств, наивный рекурсивный Фибоначчи, полный перебор в задачах с экспоненциальным деревом решений.
O(n!) — факториальная
Самый тяжёлый из распространённых классов. Растёт ещё быстрее экспоненты — уже при n=13 значение превышает миллиард.
def permutations(arr):
# Генерация всех перестановок — их ровно n!
if len(arr) <= 1:
return [arr]
result = []
for i in range(len(arr)):
rest = arr[:i] + arr[i + 1:]
for p in permutations(rest):
result.append([arr[i]] + p)
return resultПримеры: перебор всех перестановок, наивное решение задачи коммивояжёра.
Как оценивать сложность: правила
Чтобы получить итоговую оценку O(), пользуются несколькими простыми правилами.
1. Отбрасывание констант
Константные множители не влияют на класс сложности. O(2n), O(100n), O(n/2) — это всё O(n). Нас интересует форма роста, а не коэффициент.
def example(arr):
for x in arr: # n операций
print(x)
for x in arr: # ещё n операций
print(x)
# Итого 2n -> O(n), а не O(2n)2. Доминирующий (старший) член
При сложении слагаемых остаётся только самое быстрорастущее. O(n² + n + 100) упрощается до O(n²), потому что при больших n остальные члены пренебрежимо малы.
def example(arr):
print(arr[0]) # O(1)
for x in arr: # O(n)
print(x)
for i in range(len(arr)): # O(n^2)
for j in range(len(arr)):
print(i, j)
# O(1) + O(n) + O(n^2) -> O(n^2)3. Последовательность и вложенность
- Последовательные блоки складываются: O(a) затем O(b) даёт O(a + b).
- Вложенные циклы перемножаются: цикл на n внутри цикла на n даёт O(n · n) = O(n²).
- Разные входы не схлопывают: два цикла по разным массивам — это O(n + m), а вложенные — O(n · m).
Сложность операций по структурам данных
Усреднённая сложность типичных операций (в скобках — худший случай, если он отличается). «Поиск» означает поиск элемента по значению.
| Структура | Доступ по индексу | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив (array) | O(1) | O(n) | O(n) | O(n) |
| Динамический массив (конец) | O(1) | O(n) | O(1)* | O(1)* |
| Связный список | O(n) | O(n) | O(1)** | O(1)** |
| Хеш-таблица | — | O(1) / O(n) | O(1) / O(n) | O(1) / O(n) |
| Сбалансированное дерево поиска | — | O(log n) | O(log n) | O(log n) |
| Стек (stack) | — | O(n) | O(1) | O(1) |
| Очередь (queue) | — | O(n) | O(1) | O(1) |
* — амортизированно O(1); при переполнении буфера происходит дорогое расширение. ** — O(1), если ссылка на нужный узел уже есть; иначе придётся сначала дойти до него за O(n). Для хеш-таблицы в среднем O(1), но при множестве коллизий — до O(n).
Сложность алгоритмов сортировки
Сравнение популярных алгоритмов сортировки. Стабильность — сохраняется ли исходный порядок равных элементов.
| Алгоритм | Лучший | Средний | Худший | Память | Стабильный |
|---|---|---|---|---|---|
| Пузырьком (bubble sort) | O(n) | O(n²) | O(n²) | O(1) | Да |
| Вставками (insertion sort) | O(n) | O(n²) | O(n²) | O(1) | Да |
| Выбором (selection sort) | O(n²) | O(n²) | O(n²) | O(1) | Нет |
| Быстрая (quick sort) | O(n log n) | O(n log n) | O(n²) | O(log n) | Нет |
| Слиянием (merge sort) | O(n log n) | O(n log n) | O(n log n) | O(n) | Да |
| Кучей (heap sort) | O(n log n) | O(n log n) | O(n log n) | O(1) | Нет |
На практике: для больших данных выбирают быструю сортировку (быстрая на практике, но боится «плохих» опорных элементов), сортировку слиянием (гарантированная O(n log n) и стабильность ценой памяти) или кучей (O(n log n) и константная память). Простые квадратичные сортировки хороши только для очень маленьких массивов или почти отсортированных данных.
Сложность поиска
Два базовых алгоритма поиска элемента в коллекции.
| Алгоритм | Условие | Лучший | Средний / худший |
|---|---|---|---|
| Линейный поиск | Любой массив | O(1) | O(n) |
| Бинарный поиск | Только отсортированный массив | O(1) | O(log n) |
def linear_search(arr, target):
for i, x in enumerate(arr): # O(n): проверяем подряд
if x == target:
return i
return -1
# Бинарный поиск требует отсортированного массива,
# зато находит элемент за O(log n) (см. пример выше).Вывод: если массив придётся искать многократно, выгоднее один раз отсортировать его за O(n log n) и затем искать бинарно за O(log n), чем каждый раз делать линейный проход.
Амортизированная сложность
Амортизированная сложность — это средняя стоимость операции, усреднённая по длинной последовательности операций, даже если отдельные операции иногда дорогие.
Классический пример — добавление в динамический массив (как list.append в Python). Обычно это O(1), но когда внутренний буфер заполняется, массив выделяет новый буфер большего размера и копирует все элементы за O(n). Однако такие «дорогие» расширения происходят редко: размер удваивается, поэтому на длинной серии добавлений средняя стоимость одной операции остаётся O(1) амортизированно.
result = []
for i in range(1_000_000):
result.append(i) # почти всегда O(1);
# изредка — дорогое расширение буфера,
# но в среднем O(1) на операциюВажно отличать амортизированную O(1) от «настоящей» O(1): отдельная операция может быть медленной, но в сумме поведение остаётся эффективным.
Как сравнивать алгоритмы
Несколько практических ориентиров при выборе алгоритма:
- Сначала смотрите на класс сложности. O(n log n) почти всегда лучше O(n²) на больших данных — независимо от констант.
- Помните про размер входа. На маленьких n «медленный» алгоритм с малыми константами может обогнать асимптотически лучший. Бинарный поиск не имеет смысла на массиве из 5 элементов.
- Учитывайте память. Иногда выигрыш по времени оплачивается ростом пространственной сложности (как в сортировке слиянием).
- Различайте средний и худший случай. Быстрая сортировка в среднем O(n log n), но в худшем — O(n²); для гарантий выбирают сортировку слиянием или кучей.
- Не оптимизируйте вслепую. Если код выполняется один раз на 10 элементах, разница между O(n) и O(n²) несущественна — важнее читаемость.
Наглядно: n против числа операций
Эта таблица показывает, почему класс сложности так важен. В ячейках — приблизительное число операций для разных n (значения для O(2ⁿ) и O(n!) при больших n астрономически велики).
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | O(n!) |
|---|---|---|---|---|---|---|---|
| 10 | 1 | ≈3 | 10 | ≈33 | 100 | 1 024 | ≈3.6·10⁶ |
| 20 | 1 | ≈4 | 20 | ≈86 | 400 | ≈10⁶ | ≈2.4·10¹⁸ |
| 100 | 1 | ≈7 | 100 | ≈664 | 10 000 | ≈10³⁰ | ≈10¹⁵⁸ |
| 1 000 | 1 | ≈10 | 1 000 | ≈9 966 | 10⁶ | огромно | огромно |
| 1 000 000 | 1 | ≈20 | 10⁶ | ≈2·10⁷ | 10¹² | огромно | огромно |
Обратите внимание: при росте n от 10 до миллиона O(1) и O(log n) почти не меняются, O(n) растёт пропорционально, а O(n²) становится практически неподъёмной. Экспоненциальные и факториальные алгоритмы применимы лишь для крошечных входов.
