Урок

Сложность: O-нотация на пальцах

Зачем вообще считать сложность

Представь: ты написал решение, оно работает на примере из трёх чисел. Интервьюер спрашивает: «А если чисел будет миллион?» Вопрос не в том, сколько миллисекунд займёт программа. Его интересует, как растёт работа, когда растёт вход.

Для этого и нужна O-нотация. Она не считает точное время. Она описывает форму роста: если вход вырос в 10 раз, во сколько раз выросла работа?

У алгоритма две главные мерки:

Время: сколько элементарных шагов он делает (сравнений, присваиваний, обращений к массиву).
Память: сколько дополнительного места он занимает сверх входа (новые массивы, словари, глубина рекурсии).

Константы и мелочи отбрасываем. 3n + 5 превращается в O(n), а n² + n в O(n²). При больших n важен только самый быстрорастущий член.

Главные сложности на бытовых примерах

Сложность	Аналогия	n = 10⁶ → примерно шагов
O(1)	Открыть книгу на закладке. Неважно, сколько в ней страниц	1
O(log n)	Искать слово в словаре: открыл посередине, отбросил половину, повторил	~20
O(n)	Пролистать всю книгу и найти опечатку	10⁶
O(n log n)	Разложить колоду карт по порядку умным способом (хорошая сортировка)	~2·10⁷
O(n²)	Каждый гость на вечеринке жмёт руку каждому другому	10¹² 😬
O(2ⁿ)	Перебрать все наборы начинок для пиццы: каждую либо кладёшь, либо нет	невозможно

Запомни по одной картинке на каждую строку. На собесе этого хватит, чтобы с ходу прикинуть оценку.

Как считать: цикл

Один проход по массиву означает, что каждый элемент посещается один раз. Шагов столько же, сколько элементов, то есть O(n).

152

i ↓ 163

234

425

Линейный проход: указатель i идёт слева направо, каждый элемент смотрим один раз → O(n)

Классический пример такого прохода — линейный поиск:

def linear_search(arr, target):
    # смотрим каждый элемент по очереди — O(n) времени, O(1) памяти
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # не нашли

Два цикла друг за другом дают O(n) + O(n) = O(2n), а это всё ещё O(n). Складывать нужно последовательные шаги.

Как считать: вложенные циклы

Если цикл находится внутри другого цикла, шаги умножаются. Для каждого i внутренний цикл пробегает до n элементов: n · n = O(n²). Это и есть «рукопожатия на вечеринке». Пример: подсчитать пары одинаковых элементов.

def count_equal_pairs(arr):
    n = len(arr)
    count = 0
    for i in range(n):            # n раз
        for j in range(i + 1, n): # до n раз для каждого i
            if arr[i] == arr[j]:
                count += 1
    return count  # O(n²) времени, O(1) памяти

j начинается с i + 1, поэтому шагов примерно n²/2. Но константу ½ мы отбрасываем, и остаётся всё равно O(n²).

Как считать: рекурсия

Формула простая: число вызовов × работа в одном вызове.

Делим задачу пополам и идём только в одну половину, как в бинарном поиске. Вызовов будет log n, значит O(log n).
Делим пополам, решаем обе половины и делаем O(n) работы на слияние, как в сортировке слиянием. Получаем log n уровней, на каждом O(n) работы, итого O(n log n).
Два рекурсивных вызова почти того же размера, как в наивных числах Фибоначчи f(n-1) + f(n-2). Дерево вызовов удваивается на каждом уровне, получается O(2ⁿ).

Память рекурсии считается по глубине стека вызовов. У бинарного поиска она O(log n), у Фибоначчи O(n). Об этом часто забывают.

Размер входа подсказывает решение

Ориентир: компьютер делает примерно 10⁸ простых операций в секунду. Посмотри на ограничения в условии, и ты сразу поймёшь, какой сложности от тебя ждут:

Размер n	Допустимая сложность
n ≤ 10–12	O(n!), перебор перестановок
n ≤ 20–25	O(2ⁿ), перебор подмножеств
n ≤ 500	O(n³)
n ≤ 5 000	O(n²)
n ≤ 10⁵–10⁶	не хуже O(n log n)
n ≤ 10⁸	O(n)
ещё больше	O(log n) или O(1)

Видишь n ≤ 10⁵? Двойной цикл почти наверняка не пройдёт. Ищи сортировку, хеш-таблицу или два указателя.

Как это звучит на собесе

Называй сложность сам и сразу, не дожидаясь вопроса:

«Я прохожу массив один раз и храню значения в хеш-множестве. Время O(n), дополнительная память O(n). Наивный вариант с двумя циклами был бы O(n²), при n до 10⁵ это слишком медленно».

В такой фразе есть время, память, сравнение с наивным решением и привязка к ограничениям. Интервьюеры очень это ценят.

Частые ошибки

Забыть про память. Новый массив, словарь или стек рекурсии тоже стоят места.
Не заметить скрытый цикл. x in list, arr.indexOf, slice, substring и конкатенация строк в цикле сами работают за O(n). Если такой вызов стоит внутри цикла, получается O(n²).
Перемножать последовательные циклы. Если циклы идут друг за другом, их сложности складываются, а не перемножаются.
Путать «цикл до n» и «цикл, где i удваивается». i *= 2 даёт O(log n), а не O(n).
Считать сортировку бесплатной. sort() стоит O(n log n), и это нужно учитывать в итоговой оценке.

Ты уже умеешь главное: посмотреть на код и сказать, как он растёт. Дальше в каждой задаче проговаривай сложность вслух, и через пару десятков задач это станет привычкой.