Як вимірюється обсяг пам'яті алгоритму?

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

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

Обсяг пам'яті алгоритму вимірюється як просторова складність S(n) - функція від розміру входу n. Зазвичай вказують асимптотичну оцінку в O-нотації для пікового обсягу додаткової (auxiliary) пам'яті, яку алгоритм одночасно використовує: змінні, тимчасові структури даних і рекурсивний стек. За потреби розрізняють загальну пам'ять (вхід + вихід + додатково) і уточнюють, для якого випадку (найгірший, середній, амортизований) дана оцінка.

Розгорнута відповідь

Що саме вимірюємо

Загальна пам'ять: S_total(n) = S_input(n) + S_output(n) + S_aux(n).
Додаткова (auxiliary) пам'ять: усе, що алгоритм виділяє понад зберігання входу і результату. На співбесідах зазвичай питають саме про неї.
Пікове значення: максимальний одночасний обсяг пам'яті за весь час роботи, а не сумарно виділене/звільнене.
Випадок: найгірший (worst-case), середній (average-case) чи амортизований. Не забудьте уточнити це у відповіді.

Модель і одиниці вимірювання

Зазвичай використовують модель RAM/word-RAM: рахуємо пам'ять у машинних словах (чи байтах), а потім спрощуємо до функції від n і беремо асимптотику.

Скалярні змінні: O(1).
Масив довжини k: O(k). Матриця n×m: O(n·m).
Хеш-таблиця/словник з k елементами: O(k).
Рекурсивний виклик глибини h: O(h) додаткової пам'яті під стек.

Як оцінювати на практиці (алгоритм дій)

Визначте, що рахувати: загальну чи додаткову пам'ять; пікову чи сумарно виділену.
Розбийте алгоритм на фази і перелічіть одночасно живі структури даних.
Врахуйте стек рекурсії чи внутрішній стек/черги при обходах.
Складіть розміри (у словах/байтах) і виразіть як S(n); спростіть до O(·), Θ(·) чи Ω(·).
Уточніть випадок (найгірший/середній/амортизований) і залежності від додаткових параметрів (k - кількість унікальних, V/E - розмір графа тощо).
За потреби дайте точну оцінку в байтах для конкретної реалізації (наприклад, 4 байти на 32-бітне ціле).

Типові складові пам'яті

Зберігання вхідних даних (часто не включають в auxiliary).
Пам'ять під вихід (часто рахують окремо; наприклад, повернення нового масиву довжини k - O(k)).
Тимчасові структури: масиви, хеш-таблиці, черги/стеки, буфери.
Стек рекурсії чи глибина ітеративного стека при обходах.
Накладні витрати структур (заголовки об'єктів, вказівники) - враховуються при точних підрахунках, але опускаються в асимптотиці.

Короткі приклади оцінок

Пошук максимуму в масиві одним проходом: O(1) auxiliary.
Підрахунок частот за допомогою Map по n елементах: O(k), де k - кількість унікальних значень (k ≤ n).
BFS у графі: черга O(V), масив visited O(V) → auxiliary O(V).
Merge sort: O(n) додаткової пам'яті; Quick sort: O(log n) стек у середньому, O(n) у найгіршому.
ДП з таблицею n×m: O(nm), але іноді можна оптимізувати до O(min(n, m)) за пам'яттю, зберігаючи лише потрібний рядок/стовпець.

Приклади коду

Два підходи до задачі two-sum показують відмінності в додатковій пам'яті.

// Приклад 1: пошук пари із сумою target - різні профілі пам'яті
// Варіант A: хеш-таблиця - O(n) додаткової пам'яті
function twoSumHash(nums, target) {
  const map = new Map(); // до n записів ⇒ O(n)
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return null;
}

// Варіант B: два вказівники після сортування - O(1) дод. пам'яті (якщо сортування in-place)
// Важливі застереження:
// - Якщо сортування швидке (in-place), стек рекурсії ≈ O(log n) у середньому.
// - Якщо сортування стабільне merge-sort, дод. пам'ять може бути O(n).
function twoSumTwoPointers(nums, target) {
  nums.sort((a, b) => a - b); // потенційно O(1) auxiliary + O(log n) стек, залежить від реалізації
  let l = 0, r = nums.length - 1; // кілька скалярів ⇒ O(1)
  while (l < r) {
    const sum = nums[l] + nums[r]; // O(1)
    if (sum === target) return [nums[l], nums[r]]; // повертаємо результат (вихідна пам'ять)
    if (sum < target) l++; else r--;
  }
  return null;
}

Рекурсія проти ітерації: і там, і там O(h), де h - максимальна глибина.

// Приклад 2: обхід дерева - пам'ять через глибину
// Рекурсивний DFS: O(h) через стек викликів
function dfsRec(node) {
  if (!node) return;          // O(1)
  // ... обробка node
  dfsRec(node.left);          // глибина зростає ⇒ пам'ять O(h)
  dfsRec(node.right);
}

// Ітеративний DFS зі своїм стеком: теж O(h), але стек контролюємо ми
function dfsIter(root) {
  if (!root) return;
  const stack = [root]; // на піку до h елементів ⇒ O(h)
  while (stack.length) {
    const node = stack.pop(); // O(1)
    // ... обробка node
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

Часті помилки

Рахувати сумарно виділену пам'ять замість пікового одночасного використання.
Забувати про стек рекурсії (навіть якщо структури даних явно не створюються).
Не уточнювати, чи включається вхід і вихід в оцінку (auxiliary vs total).
Плутати in-place операції з тими, що створюють копії (наприклад, методи, що повертають новий масив).
Ігнорувати параметри, крім n (наприклад, k - кількість унікальних значень, діапазон значень, V і E у графах).
Давати середню оцінку там, де важлива найгірша поведінка.

Підсумок

Щоб виміряти обсяг пам'яті алгоритму, перелічіть одночасно живі об'єкти, порахуйте їхній сумарний розмір, виразіть його як функцію від параметрів входу, а потім наведіть асимптотичну оцінку (зазвичай для пікового auxiliary-використання). Не забувайте про стек рекурсії, уточнюйте, чи включаються вхід і вихід, і вказуйте, для якого випадку дана оцінка.

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

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

Premium

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