Какие сложности алгоритмов кроме линейной встречаются чаще всего и как с ними работать?

Сложности кроме линейной O(n): O(1) константная, O(log n) логарифмическая, O(n log n), O(n²) квадратичная, O(2ⁿ) экспоненциальная. Работают с ними, выбирая эффективные алгоритмы и структуры.

Классы сложности

O(1) — константная

Не зависит от размера (доступ по индексу, Map.get, Set.has). Идеал — стремиться к этому для частых операций.

O(log n) — логарифмическая

Деление задачи пополам (бинарный поиск). Очень эффективна (миллион → ~20 шагов).

O(n log n)

Эффективные сортировки (merge, quick), «разделяй и властвуй». Практичный предел для сортировок сравнением.

O(n²) — квадратичная

Вложенные циклы по данным. Проблема на больших данных — избегать/оптимизировать.

O(2ⁿ), O(n!) — экспоненциальная/факториальная

Перебор подмножеств, наивная рекурсия (Фибоначчи без мемоизации). Критично плохо — только для малых входов или с оптимизацией (DP).

Как работать с высокой сложностью

Заменить структуру данных

O(n²) вложенный поиск → O(n) через хеш-таблицу:

// O(n²): для каждого искать в массиве
// O(n): Map для O(1) доступа
const map = new Map(items.map((i) => [i.id, i]));

Мемоизация / DP

Экспоненциальную рекурсию → полиномиальную кешем:

const fib = memoize((n) => n < 2 ? n : fib(n-1) + fib(n-2)); // O(2ⁿ) → O(n)

Правильный алгоритм

Бинарный поиск (O(log n)) вместо линейного, эффективные сортировки.

Оценивать и профилировать

Знать сложность своего кода, находить узкие места.

Коротко для собеседования

Кроме O(n): O(1) (константа — идеал, Map/Set), O(log n) (бинарный поиск), O(n log n) (сортировки), O(n²) (вложенные циклы — избегать), O(2ⁿ)/O(n!) (перебор, наивная рекурсия — критично). Работают: заменяя структуры (хеш-таблица O(1) вместо вложенного поиска), мемоизацией/DP (экспонента → полином), правильными алгоритмами, профилированием.