Сложность алгоритмов: Big O

↑ 8.3 Алгоритмы и структуры данных · → Следующая

Желательно~3 мин чтенияУровень: senior

Зачем это на собесе

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

Нотация

Big O описывает, как растёт время или память при росте входа n, отбрасывая константы и младшие слагаемые.

Класс	Название	Пример
O(1)	константа	доступ по индексу, Map.get
O(log n)	логарифм	бинарный поиск
O(n)	линейная	обход массива
O(n log n)	линейно-логарифмическая	эффективные сортировки
O(n²)	квадрат	два вложенных цикла
O(2ⁿ)	экспонента	наивный перебор подмножеств, наивный Фибоначчи
O(n!)	факториал	перебор перестановок

Правила подсчёта

• последовательные блоки складываются: O(n) + O(n²) = O(n²);
• вложенные — умножаются;
• две разные переменные: O(a + b), O(a · b);
• рекурсия: считаем число вызовов и работу в каждом.

Сложности в JS

Операция	Сложность
arr[i], push, pop	O(1)
shift, unshift, splice в начале	O(n)
includes, indexOf	O(n)
Map/Set get, set, has	O(1) в среднем
sort	O(n log n)
concat, slice, spread	O(n)
Строковая конкатенация в цикле	O(n²) в худшем, но движки оптимизируют

Амортизированная сложность

push в динамический массив — O(1) амортизированно: редкие расширения дороги, но распределяются на много операций.

Память

Учитывайте дополнительную память: копия массива, стек рекурсии, хэш-таблица. «На месте» (in-place) — O(1) дополнительной памяти.

Best / Average / Worst

Быстрая сортировка: в среднем O(n log n), в худшем O(n²). Хэш-таблица: в среднем O(1), при коллизиях O(n).

Вопросы с ответами

Чему равна сложность вложенных циклов по одному массиву?

O(n²), если внутренний цикл выполняется до n. Если внутренний идёт от i до n, всё равно O(n²) (сумма n/2).

Почему Map быстрее массива для поиска?

Хэширование даёт доступ за O(1) в среднем, поиск в массиве — линейный O(n).