Оценка сложности алгоритма позволяет понять, как изменится время работы программы при росте объёма входных данных. Без этого инструмента невозможно сравнивать алгоритмы между собой и предсказывать поведение кода на больших наборах данных.
Что такое O-нотация
O-нотация (или «О большое») — это математический способ описать, как растёт количество операций алгоритма при увеличении размера входных данных n. Она показывает асимптотическое поведение функции, то есть тенденцию при стремлении n к бесконечности.
Важно понимать: O-нотация описывает верхнюю границу роста, а не точное число операций. Если алгоритм выполняет 3n + 5 операций, мы говорим, что его сложность O(n) — константы и младшие члены отбрасываются, потому что при больших n они становятся незначимыми.
Различают три вида сложности:
- Временная — сколько операций выполняется
- Пространственная — сколько дополнительной памяти требуется
- По лучшему / среднему / худшему случаю — обычно интересует худший
Формула и основные правила
Формальное определение: функция f(n) принадлежит классу O(g(n)), если существуют константы c > 0 и n₀, такие что:
0 ≤ f(n) ≤ c · g(n) для всех n ≥ n₀
На практике используют несколько правил упрощения:
1. Отбрасывание констант: O(2n) → O(n)
2. Отбрасывание младших: O(n² + n) → O(n²)
3. Сложение (последовательно): O(n) + O(n²) → O(n²)
4. Умножение (вложенно): O(n) · O(log n) → O(n log n)
Основные классы сложности от лучшего к худшему:
| Нотация | Название | Пример алгоритма |
|---|---|---|
| O(1) | Константная | Доступ к элементу массива по индексу |
| O(log n) | Логарифмическая | Бинарный поиск |
| O(n) | Линейная | Поиск в неотсортированном массиве |
| O(n log n) | Линейно-логарифмическая | Сортировка слиянием |
| O(n²) | Квадратичная | Сортировка пузырьком |
| O(2ⁿ) | Экспоненциальная | Перебор всех подмножеств |
| O(n!) | Факториальная | Перебор всех перестановок |
Пример
Разберём конкретный код и определим его сложность:
def find_pairs(arr, target):
result = []
for i in range(len(arr)): # цикл 1
for j in range(i+1, len(arr)): # цикл 2
if arr[i] + arr[j] == target:
result.append((arr[i], arr[j]))
return result
Шаг 1. Внешний цикл выполняется n раз.
Шаг 2. Внутренний цикл выполняется (n−1), (n−2), ..., 1, 0 раз.
Шаг 3. Считаем общее число операций:
T(n) = (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 = (n² - n)/2
Шаг 4. Применяем правила: отбрасываем константу 1/2 и младший член n. Остаётся O(n²).
Сравним, как это работает на разных n:
| n | Точное число операций | Время при 10⁹ оп/сек |
|---|---|---|
| 100 | 4 950 | ~0,000005 с |
| 1 000 | 499 500 | ~0,0005 с |
| 10 000 | ~50 000 000 | ~0,05 с |
| 100 000 | ~5 000 000 000 | ~5 с |
| 1 000 000 | ~5 · 10¹¹ | ~8 минут |
Видно, что при увеличении n в 10 раз время растёт примерно в 100 раз — это и есть характерная черта квадратичной сложности.
Если бы мы решили эту задачу через хеш-таблицу:
def find_pairs_fast(arr, target):
seen = set()
result = []
for x in arr: # O(n)
if (target - x) in seen: # O(1) благодаря хешу
result.append((x, target - x))
seen.add(x) # O(1)
return result
Сложность стала O(n). Для n = 1 000 000 алгоритм отработает за доли секунды вместо 8 минут.
Типичные ошибки
Путают O-нотацию с реальным временем работы. Алгоритм O(n) не всегда быстрее O(n²) — на малых n константы и накладные расходы могут перевернуть картину. O-нотация говорит о тенденции, а не о конкретных секундах.
Забывают про сложность встроенных операций. Например,
x in listв Python — это O(n), а не O(1). Если внутри цикла O(n) использовать поиск по списку, получится O(n²), хотя на первый взгляд код выглядит линейным.Складывают вложенные сложности вместо умножения. Если внутри цикла длиной n есть операция O(log n), общая сложность — O(n log n), а не O(n + log n).
Игнорируют пространственную сложность. Алгоритм может быть быстрым по времени, но требовать O(n²) памяти. Для больших данных это критично — программа просто упадёт по нехватке памяти.
Когда стоит обратиться за помощью
Анализ сложности алгоритмов — тема, где теория быстро упирается в практику. Бывает трудно увидеть скрытые вложенные циклы, корректно оценить рекурсию через основную теорему или разобрать амортизированную сложность динамического массива. Если задача из лабораторной или курсовой не поддаётся, а до сдачи мало времени — наш сервис Solvr поможет получить разобранный пример с пошаговым выводом O-оценки. Это удобный способ проверить собственное решение или разобраться в логике на готовом образце, чтобы потом самостоятельно решать аналогичные задачи на экзамене.