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

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

Почти любая задача заканчивается вопросом «какая сложность?». Интервьюер проверяет, понимаешь ли ты, как решение поведёт себя на больших данных, и умеешь ли выбрать подход до написания кода.

Big O за минуту

O(f(n)) это верхняя оценка роста числа операций. Константы и младшие слагаемые отбрасываем: 3n + 100 это O(n), n²/2 + n это O(n²).

Шкала от быстрого к медленному:

Класс	Пример	n = 10⁵
O(1)	доступ по индексу, Map.get	1
O(log n)	бинарный поиск	~17
O(n)	один проход	10⁵
O(n log n)	сортировка	~1.7·10⁶
O(n²)	два вложенных цикла	10¹⁰
O(2ⁿ)	все подмножества	нереально

Правило большого пальца: за секунду JS делает порядка 10⁷-10⁸ простых операций. По ограничениям задачи можно угадать нужную сложность: n ≤ 20 разрешает перебор 2ⁿ, n ≤ 10³ разрешает O(n²), n ≤ 10⁵-10⁶ требует O(n log n) или O(n).

Как считать

1. Последовательно складываем: два прохода подряд это O(n + n) = O(n).
2. Вложенно перемножаем: цикл в цикле O(n · m).
3. Деление пополам даёт log n.
4. Рекурсия: число вызовов × работа в вызове. fib(n-1) + fib(n-2) это O(2ⁿ), с мемоизацией O(n).

for (const x of a) {          // n
  if (b.includes(x)) { ... }  // m внутри: итого O(n · m)
}

const set = new Set(b);       // O(m)
for (const x of a) {          // n
  if (set.has(x)) { ... }     // O(1) в среднем: итого O(n + m)
}

Скрытые циклы

Встроенные методы не бесплатны: includes, indexOf, find, slice, concat, [...arr], Object.keys линейны. sort это O(n log n). shift и unshift сдвигают весь массив, O(n), поэтому очередь на shift в BFS превращает O(n) в O(n²). Строки в JS неизменяемы: s += ch в цикле обычно оптимизируется движком, а s.slice() в цикле честно копирует.

Память

Считается дополнительная память: новые массивы, Map, Set и стек рекурсии. Рекурсия глубины n стоит O(n) памяти даже без структур, а при глубине порядка 10⁴ и больше можно упереться в лимит стека.

Средний, худший, амортизированный

• Map.get O(1) в среднем, худший случай теоретически хуже.
• push O(1) амортизированно: иногда массив расширяется за O(n), но суммарно n вставок стоят O(n).
• Быстрая сортировка O(n log n) в среднем и O(n²) в худшем.

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

• Называть O(2n) или O(n/2) как отдельный класс: это O(n).
• Сводить два входа к одному n.
• Забывать память стека и скрытые циклы.
• Говорить «O(1) по памяти», создав копию массива.

Что спросят на собесе

• Какая сложность твоего решения по времени и памяти?
• Можно ли быстрее и чем за это заплатим (обычно памятью)?
• Почему push O(1), а shift O(n)?
• Какая сложность у наивного Фибоначчи и как её улучшить?
• Какие ограничения на n сделали бы твоё решение слишком медленным?