Сложность алгоритмов в JavaScript: полное руководство по Big O

Когда код работает медленно или падает на больших данных, дело часто не в языке, а в выборе алгоритма. В JavaScript понимание сложности алгоритмов помогает писать предсказуемый код, который не тормозит даже при тысячах элементов. В этом материале разберём нотацию Big O, научимся оценивать время выполнения и память, а также посмотрим на реальную сложность встроенных методов JS.

Что такое сложность алгоритмов и зачем она в JavaScript

Сложность алгоритма — это характеристика того, как быстро растёт время выполнения или потребление памяти при увеличении входных данных. В веб-разработке это критично: если вы обрабатываете массив из 10 элементов, разница между O(n) и O(n²) незаметна. Но при 10 000 элементах один алгоритм выполнится за миллисекунды, а другой — за секунды или минуты.

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

Big O нотация: от O(1) до O(n!)

Big O описывает асимптотическую сложность — как ведёт себя алгоритм на больших объёмах данных. Рассмотрим основные классы с примерами на JS.

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

Время выполнения не зависит от размера входных данных. Примеры: доступ к элементу массива по индексу, вставка в Set, получение свойства объекта.

function getFirstElement(arr) {
  return arr[0]; // O(1) — всегда одна операция
}

const obj = { name: 'Ivan', age: 30 };
console.log(obj.age); // O(1)

O(n) — линейная сложность

Время растёт пропорционально размеру данных. Один проход по массиву, строке или коллекции.

function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) { // O(n)
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// Встроенные методы с линейной сложностью:
arr.map(fn);    // O(n)
arr.filter(fn); // O(n)
arr.reduce(fn); // O(n)

O(n²) — квадратичная сложность

Два вложенных цикла по одному и тому же массиву. Опасно для больших данных. Пример — пузырьковая сортировка или поиск дубликатов наивным способом.

function findDuplicates(arr) {
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {      // O(n²)
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j] && !duplicates.includes(arr[i])) {
        duplicates.push(arr[i]);
      }
    }
  }
  return duplicates;
}
// Улучшение до O(n) через Set

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

На каждом шаге алгоритм отбрасывает половину данных. Классика — бинарный поиск в отсортированном массиве.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {            // O(log n)
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

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

Типична для эффективных сортировок: sort() в движках JavaScript (Timsort) работает за O(n log n) в среднем.

const arr = [3, 1, 4, 1, 5, 9, 2];
arr.sort((a, b) => a - b); // O(n log n)

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

Крайне неэффективны. Примеры: рекурсивный расчёт чисел Фибоначчи без мемоизации (O(2ⁿ)), генерация всех перестановок массива (O(n!)). Такие алгоритмы неприменимы для n > 20–30.

function fib(n) { // O(2ⁿ) — ужасно для больших n
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Сложность методов массивов в JavaScript

Важно знать реальную сложность встроенных методов, чтобы не создавать скрытые квадратичные алгоритмы.

Метод	Временная сложность	Примечание
push(), pop()	O(1)	Амортизированная константа
shift(), unshift()	O(n)	Переиндексация всех элементов
slice()	O(n)	Копирует элементы
splice()	O(n)	Сдвигает элементы после точки вставки/удаления
concat()	O(n + m)	Где n и m — длины массивов
indexOf(), includes()	O(n)	Линейный поиск
forEach(), map(), filter(), reduce()	O(n)	Один проход
sort()	O(n log n)	Timsort в V8 и SpiderMonkey

Ошибка новичка: использование shift() в цикле — получается O(n²). Замените на pop() или дек через два стека.

Сложность объектов, Map и Set

Объекты JavaScript и Map/Set реализованы как хеш-таблицы (в большинстве движков). Это даёт ожидаемую сложность O(1) для вставки, удаления и поиска по ключу. Однако есть нюансы.

const map = new Map();
map.set('key', 'value'); // O(1) в среднем
map.get('key');          // O(1)
map.has('key');          // O(1)
map.delete('key');       // O(1)

const set = new Set();
set.add(42);             // O(1)
set.has(42);             // O(1)

Внимание: в редких случаях при коллизиях хешей сложность может деградировать до O(n), но на практике это маловероятно. Для строковых ключей в обычных объектах — аналогично.

Пространственная сложность: как оценить память

Кроме времени, важно учитывать дополнительную память. Пространственная сложность (space complexity) измеряется по тем же правилам Big O, но учитывает только дополнительное выделение, не считая входные данные.

// O(1) дополнительной памяти — меняем массив на месте
function reverseInPlace(arr) {
  for (let i = 0; i < Math.floor(arr.length / 2); i++) {
    [arr[i], arr[arr.length - 1 - i]] = [arr[arr.length - 1 - i], arr[i]];
  }
}

// O(n) дополнительной памяти — создаём новый массив
function reverseNewArray(arr) {
  const result = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    result.push(arr[i]);
  }
  return result;
}

Рекурсия без хвостовой оптимизации также даёт O(n) памяти под стек вызовов.

Сложность рекурсивных алгоритмов

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

function traverseTree(node) { // O(n) по времени, O(h) по памяти (h — высота)
  if (!node) return;
  console.log(node.value);
  traverseTree(node.left);
  traverseTree(node.right);
}

// Фибоначчи с мемоизацией — O(n) времени и O(n) памяти
const memo = new Map();
function fibMemo(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, result);
  return result;
}

Как улучшить сложность: практические приёмы

Частые способы снизить сложность в JavaScript:

• Заменить вложенные циклы на хеш-таблицу: если нужно найти пересечения двух массивов, используйте Set вместо двух циклов — O(n+m) вместо O(n*m).
• Избегать методов с O(n) внутри циклов: includes(), indexOf(), slice() в теле цикла создают квадратичную сложность.
• Использовать два указателя вместо вложенных циклов для задач на массивах (поиск пар с суммой, удаление дубликатов).
• Мемоизация для рекурсивных вычислений — превращает O(2ⁿ) в O(n).
• Разделяй и властвуй (бинарный поиск, сортировка слиянием) даёт O(log n) или O(n log n).

Типичные ошибки при оценке сложности

1. Игнорирование констант: O(2n) = O(n), но это не значит, что можно игнорировать множитель 2. В JS один цикл с двумя операциями всё же быстрее двух отдельных циклов по тем же данным.
2. Путаница между временной и пространственной сложностью: хороший алгоритм ищет баланс (time-memory trade-off).
3. Сложность встроенных методов: например, arr.includes() внутри цикла по arr даёт O(n²), хотя на первый взгляд кажется чистым кодом.
4. Забывать про рекурсию: красивое рекурсивное решение может съесть стек вызовов для больших n (максимальная глубина ~10 000 в движках JS).
5. Оценивать сложность по наилучшему случаю: всегда ориентируйтесь на средний или худший случай, если нет гарантий на входные данные.

Заключение

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

• Предсказывать, как поведёт себя код при 10 элементах и при 100 000.
• Выбирать правильные структуры данных (Map vs объект, Set vs массив).
• Избегать случайных квадратичных алгоритмов, особенно при работе с DOM или большими объёмами данных.
• Оптимизировать узкие места, не тратя время на бесполезный рефакторинг.

Начните с мысленного подсчёта операций в циклах и вложенности — это 90% успеха. Для сложных случаев используйте console.time() и профилировщик в DevTools, чтобы проверить свои предположения. Алгоритмическая грамотность окупается быстрым и отзывчивым интерфейсом, который любят пользователи.