Сложность алгоритмов: время, память и сложность методов JS

О проверке кода. Оценки сложности — математика, а не замер; конкретные времена не измерялись. Бейджа «проверено» поэтому нет — в отличие от материалов по Node.js с фактическим выводом.

Нотация «большое O» отвечает на вопрос «как быстро». Но у сложности есть второе измерение, о котором забывают, и практический слой, который в туториалах почти не разбирают: сколько стоят встроенные методы языка.

Два измерения сложности

Временна́я сложность — как растёт время работы. Это то, о чём обычно и думают.

Пространственная сложность — как растёт объём памяти. И вот здесь начинается интересное: улучшая одно, вы почти всегда ухудшаете другое.

Вернёмся к поиску дубля из разбора Big O:

// вариант A: медленно, но без лишней памяти
function hasDupSlow(arr) {          // время O(n²), память O(1)
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

// вариант B: быстро, но с памятью
function hasDupFast(arr) {          // время O(n), память O(n)
  const seen = new Set();           // ← вот эта память
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Вариант B быстрее в тысячи раз — но держит в памяти копию всех уникальных элементов. На массиве из миллиона это мегабайты.

Тот же размен мы видели в чтении файлов: readFile держит файл в памяти целиком (быстро, но +169 МБ), поток читает кусками (память постоянна, но с накладными расходами). Это одно и то же решение на другом уровне.

Практический вывод: «сделать быстрее» и «сделать экономнее» — обычно разные задачи. Прежде чем оптимизировать, поймите, чего у вас не хватает — времени или памяти.

Сложность встроенных методов JavaScript

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

Две строки здесь — источник большинства скрытых тормозов.

shift — это не «дешёвый pop с другой стороны». Он сдвигает весь массив на позицию:

// ❌ очередь через массив: O(n) на каждое извлечение
while (queue.length) {
  const item = queue.shift();   // сдвигает всё, что осталось
}

На большой очереди это незаметно превращается в O(n²). Для очереди в горячем коде берут другую структуру или индекс-указатель вместо shift.

includes в цикле — классический скрытый квадрат:

// ❌ O(n²): для каждого элемента — линейный поиск по другому массиву
const common = a.filter((x) => b.includes(x));

// ✅ O(n): b превращаем в Set, поиск за O(1)
const bSet = new Set(b);
const common = a.filter((x) => bSet.has(x));

Выглядит одинаково, работает по-разному в тысячи раз на больших данных. Замена массива на Set для повторяющихся проверок вхождения — самая недооценённая оптимизация в JavaScript.

Скрытая ловушка: копирование в цикле

// ❌ выглядит O(n), на деле O(n²)
let result = [];
for (const item of items) {
  result = [...result, item];   // копирует ВЕСЬ result каждый раз!
}

// ✅ O(n)
const result = [];
for (const item of items) {
  result.push(item);
}

Спред [...result] копирует накопленное на каждой итерации. Тот же паттерн с Object.assign в цикле, с конкатенацией строк через += на больших объёмах. Красиво выглядящий иммутабельный код незаметно становится квадратичным.

Это ровно та мысль, что проходит через весь раздел Node.js: дорого не действие, дорого повторение — будь то запись в файл, команды Redis или копирование массива в цикле.

Что действительно нужно помнить

Для обычной веб-разработки глубокая теория не нужна. Достаточно четырёх интуиций:

1. перебор — O(n), вложенный перебор одного набора — O(n²), и второе почти всегда сводится к первому через Set/Map;
2. поиск по ключу — O(1): Set, Map, объект. Ищете вхождение часто — не держите данные в массиве;
3. shift/unshift дороже, чем кажутся: сдвигают весь массив;
4. копирование стоит O(n): [...x] в цикле — красный флаг.

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

Что было на этой странице в 2017 году

Первая версия вышла 30 июля 2017 года и разбирала теорию сложности классически: типы сложностей, как отличить хороший алгоритм от плохого. Корректно и по делу — для теоретического введения.

Чего не хватало — двух практических слоёв:

• Пространственной сложности как равноправной темы. Память упоминалась вскользь, а размен «время против памяти» — то, с чем реально сталкиваются, — не разбирался вовсе.
• Сложности встроенных методов. Это самое полезное для веб-разработчика знание: includes — O(n), Set.has — O(1). Без него теория остаётся теорией, а с ним — превращается в конкретное «замени массив на Set».

Академическая часть не устарела. Мы добавили к ней то, что превращает её в инструмент ежедневной работы.

Смежные темы: нотация «большое O» — основы с примерами; массивы в JavaScript — методы и их поведение; потоки в Node.js — размен память/время на практике. Полный список — в уроках JavaScript.