Что такое сложность

Что проверяют

Умеете ли вы оценивать стоимость кода до того, как он попадёт в браузер, и говорить об этом на общем языке. Вопрос базовый, поэтому ценится точность формулировок: что именно измеряется, относительно чего и в каких единицах.

Как отвечать

Сложность это оценка того, как растут затраты алгоритма при росте размера входа n. Осей две: время и память. Записывается O-нотацией: O(1), O(log n), O(n), O(n log n), O(n²). O задаёт верхнюю границу скорости роста, а не время в секундах; константы и слагаемые младшего порядка отбрасываются, поэтому на маленьких входах квадратичный алгоритм спокойно обгоняет линейно-логарифмический.

Лучший, средний и худший случаи это отдельная ось. У быстрой сортировки средний случай O(n log n), худший O(n²), и называть её сложность стоит с этой оговоркой.

Типичный фронтендовый пример: поиск вложенным циклом на каждый введённый символ даёт O(n·m), замена на индекс по ключу даёт O(1) на проверку.

const bySlug = new Map(items.map((i) => [i.slug, i]));
const found = ids.map((id) => bySlug.get(id));

Отдельно стоит сказать, что в браузере к алгоритмической цене добавляется цена работы с DOM: тысяча точечных вставок дороже одной вставки фрагмента, хотя порядок роста одинаковый.

Где спотыкаются

Называют O оценкой худшего случая. Это разные вещи: нотация описывает рост функции, а лучший, средний и худший случаи задают, какую именно функцию мы оцениваем.

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

Переносят вывод на реальные данные без замера. На размерах входа, типичных для интерфейса, решает не порядок роста, а константа: лишний проход по массиву заметен меньше, чем один принудительный пересчёт стилей.