Що означає просторова складність?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Просторова складність - це оцінка того, як обсяг пам'яті, що використовується алгоритмом, зростає зі збільшенням розміру вхідних даних n, зазвичай у нотації O(·). Часто розрізняють повну (включно з входом і виходом) і допоміжну (тільки додаткова понад вхід/вихід) пам'ять.

Докладний розбір

Що таке просторова складність

Просторова складність (space complexity) - це функція, що описує верхню оцінку пам'яті, яку алгоритм використовує залежно від розміру входу n. Виражається в O(1), O(log n), O(n), O(n log n), O(n²) тощо.

Допоміжна пам'ять (auxiliary space): змінні, тимчасові структури даних, стек рекурсії - все понад сам вхід і обов'язковий вихід. Найчастіше на співбесідах запитують саме про це.
Повна пам'ять (total space): вхід + вихід + допоміжна пам'ять. Уточнюйте, що саме потрібно оцінити.

Що враховується при оцінці

Кількість і розмір додаткових структур даних: масивів, списків, хеш-таблиць, дерев тощо.
Глибина стека викликів при рекурсії (кожен кадр стека зберігає локальні змінні і адресу повернення).
Розмір вихідних даних (якщо рахують повну пам'ять). Наприклад, генерація всіх підмножин вимагає O(2^n) місця для результату.

Чому це важливо

Обмеження за пам'яттю: мобільні пристрої, безсерверні функції, контейнери з лімітами.
Масштабування: алгоритми, що вимагають O(n) або O(n²) дод. пам'яті, можуть бути неприйнятні на великих даних.
Рекурсія: може непомітно «з'їсти» пам'ять через стек викликів.

Як оцінювати на практиці (покроково)

Позначте розмір входу: n (або n і m для двовимірних випадків).
Порахуйте додаткові структури: масиви/колекції та їх розміри відносно n.
Врахуйте рекурсію: глибина стека × розмір кадру дає O(глибина).
Підсумуйте і залиште домінуючий член (O(n) + O(1) → O(n)).
Уточніть: допоміжна чи повна пам'ять потрібна у відповіді.

Типові приклади та їхня O-складність

Алгоритм/структура	Допоміжна пам'ять	Примітка
Лінійний прохід зі сталою кількістю змінних	O(1)	Без дод. структур, тільки лічильники/вказівники
Копіювання масиву/фільтрація в новий масив	O(n)	Новий масив пропорційний розміру входу
Сортування злиттям (merge sort)	O(n)	Потрібні буфери для злиття
Швидке сортування (quicksort) рекурсивно, in-place	O(log n) у середньому	За рахунок стека рекурсії; у найгіршому випадку O(n)
DFS/BFS по графу з множиною відвіданих	O(V + E)	Зберігання черги/стека і «visited»
Бінарний пошук (рекурсія)	O(log n)	Глибина рекурсії логарифмічна; ітеративно - O(1)

Приклади коду (JavaScript)

Розворот масиву: O(1) vs O(n) за пам'яттю

// O(1) допоміжна пам'ять: міняємо елементи на місці
function reverseInPlace(arr) {
  let i = 0, j = arr.length - 1;
  while (i < j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++; j--;
  }
  return arr;
}

// O(n) допоміжна пам'ять: створюємо новий масив
function reverseWithCopy(arr) {
  const res = [];
  for (let i = arr.length - 1; i >= 0; i--) res.push(arr[i]);
  return res;
}

Рекурсія і стек: O(n) проти O(1) ітеративно

// Рекурсивна сума: O(n) за стеком
function sumRec(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sumRec(arr, i + 1);
}

// Ітеративна сума: O(1) дод. пам'яті
function sumIter(arr) {
  let s = 0;
  for (let x of arr) s += x;
  return s;
}

Перевірка дублікатів із Set: O(n) за пам'яттю

function hasDuplicate(arr) {
  const seen = new Set(); // до n елементів → O(n)
  for (const x of arr) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

Підрахунок на прикладі: Two Sum - обмін «пам'ять ↔ час»

Підхід із множиною: O(n) за часом і O(n) за пам'яттю (Set для вже побачених чисел).
Підхід із сортуванням і двома вказівниками: після сортування - O(1) дод. пам'яті і O(n) часу; але сортування коштує O(n log n) часу і може вимагати O(log n)-O(n) пам'яті залежно від реалізації.

// O(n) пам'яті: Set
function twoSumSet(arr, target) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(target - x)) return true;
    seen.add(x);
  }
  return false;
}

// O(1) дод. пам'яті після сортування (якщо сортування in-place)
function twoSumTwoPointers(arr, target) {
  arr.sort((a, b) => a - b); // насправді може вимагати дод. пам'яті
  let i = 0, j = arr.length - 1;
  while (i < j) {
    const s = arr[i] + arr[j];
    if (s === target) return true;
    s < target ? i++ : j--;
  }
  return false;
}

Практичні поради для співбесід

Завжди уточнюйте: оцінюємо допоміжну чи повну пам'ять.
Говоріть про стек рекурсії: «Рішення рекурсивне, отже O(depth) за пам'яттю».
Відзначайте обміни: «Використовую Set - O(n) пам'яті, зате час O(n). Без Set - пам'ять O(1), але час гірший».
Стала пам'ять - це не «0 пам'яті», а пам'ять, що не залежить від n (наприклад, кілька змінних або фіксований буфер).

Підсумок

Просторова складність описує, скільки додаткової пам'яті вимагає алгоритм у міру зростання входу. Для впевненої відповіді на співбесіді: чітко позначте n, перелічіть дод. структури і стек рекурсії, оберіть домінуючий порядок і поясніть компроміси між часом і пам'яттю.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.