Сложность алгоритмов O(n)

Зачем измерять скорость алгоритма

Два решения могут давать одинаково правильный ответ, но одно работает мгновенно, а другое «думает» минутами на больших данных. Чтобы сравнивать решения, не запуская их, придумали язык оценки скорости — сложностьОценка роста числа операций/памяти при увеличении размера входа. Записывается как O(n). (Big O).

Big O — язык скорости

Сложность показывает, как растёт число операций при увеличении размера входных данных n. Записывается как «O от чего-то». Аналогия: неважно, насколько быстрый у вас компьютер — важно, во сколько раз больше работы появится, если данных станет вдвое больше. Это главный критерий, по которому на LeetCode оценивают решение.

Как считать на практике

Простое правило для начала:

• Один цикл по данным → O(n).
• Цикл внутри цикла по тем же данным → O(n²).
• Доступ к элементу спискаИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. по индексу или поиск в словареКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict./множестве → O(1).

Наглядно: при n = 1000 алгоритмЧёткая последовательность шагов для решения задачи за конечное число действий. O(n) сделает ~1000 шагов, а O(n²) — миллион. Разница колоссальная.

Разберём разницу: в «медленной» версии для каждого элемента мы ещё раз пробегаем по оставшимся — это два вложенных цикла, O(n²). В «быстрой» версии мы один раз проходим по списку и спрашиваем у множестваКоллекция уникальных элементов без порядка: {1, 2, 3}. По-английски set. «видели ли мы это число?» — проверка в set мгновенна, O(1). Итого один проход — O(n).

Около миллиона (1000 × 1000). Именно поэтому вложенные циклы по большим данным опасны — и почему так ценится умение свести задачу к одному проходу.

⚠️ Частые ошибки новичков

Ошибка. Использовать x in list внутри цикла для поиска дубликатов — это незаметно превращает решение в O(n²), потому что каждая такая проверка сама по себе перебор. Для частых проверок наличия используйте set, и проверка станет O(1).