Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як вимірюється обсяг пам'яті алгоритму?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Обсяг пам'яті алгоритму вимірюється як просторова складність 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) додаткової пам'яті під стек.

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

1. Визначте, що рахувати: загальну чи додаткову пам'ять; пікову чи сумарно виділену.
2. Розбийте алгоритм на фази і перелічіть одночасно живі структури даних.
3. Врахуйте стек рекурсії чи внутрішній стек/черги при обходах.
4. Складіть розміри (у словах/байтах) і виразіть як S(n); спростіть до O(·), Θ(·) чи Ω(·).
5. Уточніть випадок (найгірший/середній/амортизований) і залежності від додаткових параметрів (k - кількість унікальних, V/E - розмір графа тощо).
6. За потреби дайте точну оцінку в байтах для конкретної реалізації (наприклад, 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-використання). Не забувайте про стек рекурсії, уточнюйте, чи включаються вхід і вихід, і вказуйте, для якого випадку дана оцінка.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати828 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.