Сложность алгоритмов в JS

Big-O никуда не делся — но в JS постоянная при операциях с массивом/объектом может различаться в 100 раз из-за внутренних режимов V8. Алгоритмическая сложность важнее, но константы тоже.

Когда константа важнее асимптотики

  • N меньше 1000-10000 — линейный обход чаще быстрее сложной структуры.
  • Array.indexOf на 100 элементах быстрее Set.has, потому что Array — кэш-френдли.
  • Map дороже Object на хороших ключах, потому что Object использует inline caches.

Типичные подмены

Заменили На что Когда выиграл
Вложенный for O(n²) Hashmap O(n) n > ~50
arr.includes в цикле Set n > ~100
Сортировка через .sort() + бинарный поиск Map поиск по ключу — всегда Map
Рекурсия Цикл глубина > ~10⁴ (стек)

Array.from и вложенные циклы

«Если ты создаёшь Array.from({length: n}, () => ...) и потом обходишь его в двойном цикле — ты платишь дважды: за аллокацию и за обход.»

Лучше — pre-allocated typed array и заполнение в одном проходе.

Аллокация как часть теста

«Тесты Array Allocation» (отдельный стрим) — большинство «алгоритмических» бенчмарков на самом деле измеряют аллокатор массивов, а не алгоритм.

Изолируй: создание данных вынеси в setup, цикл замера прогоняй на готовых данных.

Подводные камни

  • sort сравнивает строки по умолчанию. Числа: .sort((a,b)=>a-b).
  • В V8 sort стабилен с 2019 (TimSort).
  • Array.prototype.shift() — O(n), потому что сдвигает все элементы.
  • Object.keys()/values/entries создают новые массивы — дорого в цикле.

Источники

См. также