Пространственная сложность

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

Зачем нужно

Быстрый алгоритм, потребляющий O(n^2) памяти, может быть неприменим на реальных данных из-за ограничений RAM. Знание пространственной сложности позволяет оценить применимость алгоритма, найти компромисс между временем и памятью (time-space tradeoff) и предотвратить out-of-memory ошибки.

Где используется

Встраиваемые системы с ограниченной памятью
Обработка больших данных (big data): алгоритмы обязаны работать в памяти
Конкурентное программирование: строгие ограничения по памяти (256 MB)
Выбор между in-place и not-in-place алгоритмами

Основной контент

Что считается пространственной сложностью

Обычно считается дополнительная (auxiliary) память, не включая место под входные данные.

// O(1) по памяти — только переменные
function sum(arr) {
  let total = 0;    // O(1) — одна переменная
  for (const x of arr) total += x;
  return total;
}

// O(n) по памяти — создаём новый массив
function doubled(arr) {
  return arr.map(x => x * 2); // новый массив размера n
}

// O(n) по памяти — рекурсия: стек вызовов глубиной n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // n кадров на стеке
}

// O(log n) по памяти — рекурсия бинарного поиска
function bsRec(arr, lo, hi, target) {
  if (lo > hi) return -1;
  const mid = (lo + hi) >> 1;
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return bsRec(arr, mid+1, hi, target);
  return bsRec(arr, lo, mid-1, target);
}

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

Алгоритм	Доп. память
Bubble Sort	O(1) — in-place
Insertion Sort	O(1) — in-place
Merge Sort	O(n) — вспомогательный массив
Quick Sort	O(log n) — стек рекурсии (средний случай)
Heap Sort	O(1) — in-place
Hash Table	O(n) — хранение элементов
BFS	O(V) — очередь
DFS рекурсивный	O(V) — стек
DP (Knapsack)	O(n·W) или O(W) оптимизированно

Компромисс время-память (time-space tradeoff)

// Наивный поиск дубликатов: O(n²) время, O(1) память
function hasDupSlow(arr) {
  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;
}

// Быстрый поиск дубликатов: O(n) время, O(n) память
function hasDupFast(arr) {
  const seen = new Set(); // O(n) памяти
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}
// Пожертвовали O(n) памятью ради O(n) vs O(n²) времени

Хвостовая рекурсия (tail recursion)

// Обычная рекурсия: O(n) стек
function sum(n) {
  if (n === 0) return 0;
  return n + sum(n - 1); // результат нужен после возврата → стек
}

// Хвостовая рекурсия: компилятор/интерпретатор может оптимизировать до O(1)
function sumTail(n, acc = 0) {
  if (n === 0) return acc;
  return sumTail(n - 1, acc + n); // хвостовой вызов
}
// В JS TCO не гарантирован (кроме Safari с ES2015 strict mode)

Частые ошибки

Учитывать только временную сложность и игнорировать память — особенно опасно в DP, где таблица может занимать гигабайты.
Забывать стек рекурсии при анализе рекурсивных алгоритмов — DFS в глубоком графе = O(V) памяти.
Думать, что in-place сортировка = O(0) памяти — Quick Sort in-place занимает O(log n) стека рекурсии.
Путать общую и дополнительную память — обычно анализируется вспомогательная.