Какова оптимальная сложность по времени и памяти для задачи

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

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

Как отвечать

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

В JavaScript сложность портят вызовы, которые выглядят безобидно:

• includes, indexOf, find: линейный поиск. Внутри map или filter это уже O(n²), для проверок нужен Set;
• shift и unshift: сдвигают индексы всего массива, для очереди держат указатель на голову;
• спред в reduce: [...acc, x] на каждом шаге копирует аккумулятор, итог O(n²) и лишний мусор для сборщика;
• sort: O(n log n), с ES2019 обязан быть стабильным, в V8 это TimSort. По умолчанию сравнивает элементы как строки, числа сортируют с компаратором;
• slice, concat, structuredClone: копируют данные, в рекурсии это незаметная память.

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

Во фронтенде асимптотика напрямую связана с отзывчивостью: задача дольше 50 мс уже считается длинной и блокирует ввод. Тяжёлые вычисления уносят в Web Worker, а длинные списки рендерят с виртуализацией.

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

Путают средний и худший случай. O(1) у Map и Set это среднее для хеш-таблицы, а быструю сортировку записывают в O(n log n), забывая про худшие O(n²).

Приводят сложность только по времени. Копии массивов, промежуточные результаты цепочек filter().map() и замыкания тоже занимают память, и интервьюер обычно спрашивает о ней отдельно.

Не видят скрытый цикл в React: тяжёлый пересчёт на каждый рендер или поиск по массиву внутри рендера каждой строки таблицы. Здесь помогает useMemo или заранее построенный индекс в Map.