Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає просторова складність?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Просторова складність** - це оцінка того, як обсяг пам'яті, що використовується алгоритмом, зростає зі збільшенням розміру вхідних даних n, зазвичай у нотації O(·). Часто розрізняють повну (включно з входом і виходом) і допоміжну (тільки додаткова понад вхід/вихід) пам'ять. **Ключове:** на співбесідах найчастіше запитують саме про допоміжну пам'ять - усе, що понад сам вхід і обов'язковий вихід.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Просторова складність - це оцінка того, як обсяг пам'яті, що використовується алгоритмом, зростає зі збільшенням розміру вхідних даних 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²) дод. пам'яті, можуть бути неприйнятні на великих даних. - Рекурсія: може непомітно «з'їсти» пам'ять через стек викликів. ### Як оцінювати на практиці (покроково) 1. Позначте розмір входу: n (або n і m для двовимірних випадків). 2. Порахуйте додаткові структури: масиви/колекції та їх розміри відносно n. 3. Врахуйте рекурсію: глибина стека × розмір кадру дає O(глибина). 4. Підсумуйте і залиште домінуючий член (O(n) + O(1) → O(n)). 5. Уточніть: допоміжна чи повна пам'ять потрібна у відповіді. ### Типові приклади та їхня 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) 1) Розворот масиву: 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; } ``` 2) Рекурсія і стек: 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; } ``` 3) Перевірка дублікатів із 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, перелічіть дод. структури і стек рекурсії, оберіть домінуючий порядок і поясніть компроміси між часом і пам'яттю.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.