Як створення нових масивів впливає на складність?
Коротка відповідь
Створення нового масиву найчастіше додає лінійні витрати: O(n) за часом через копіювання елементів і O(n) за пам'яттю під новий буфер. Порожній масив можна створити за O(1), але щойно ви копіюєте чи заповнюєте його даними, з'являється лінійна вартість. Часте створення нових масивів усередині циклів і рекурсії може перетворювати спочатку лінійний алгоритм на квадратичний через багаторазові копіювання.
Детальний розбір
- Що означає «створити новий масив»:
- Порожній масив чи з наперед заданою довжиною: створення оболонки зазвичай O(1); заповнення n елементів - O(n).
- Копія наявного масиву: O(n) час і O(n) дод. пам'ять (копіювання посилань/значень - найчастіше поверхневе копіювання).
- Операції, що повертають новий масив (map, filter, slice, concat, оператор spread): зазвичай O(n) за часом і O(n) за пам'яттю; для concat двох масивів довжиною n і m - O(n + m).
- Вплив на часову складність алгоритму:
- Один раз скопіювати масив - це додатковий лінійний крок (O(n)).
- Якщо копіювання відбувається на кожній ітерації циклу чи кожному рівні рекурсії, сумарна складність може зрости до O(n²) через багаторазове копіювання дедалі довших масивів.
- Вплив на просторову складність:
- Новий масив потребує O(n) додаткової пам'яті.
- Композиції на кшталт filter().map() створюють проміжні масиви, збільшуючи пікове споживання пам'яті.
- Реалокації і амортизація:
- Додавання в кінець вихідного масиву зазвичай амортизовано O(1) завдяки запасу ємності.
- Якщо ж ви щоразу створюєте новий масив (наприклад, через concat), амортизаційні переваги втрачаються: відбувається копіювання всіх елементів.
- Попереднє виділення довжини допомагає уникнути багаторазових розширень.
- GC і кеш-пам'ять:
- Багато тимчасових масивів посилюють тиск на збирач сміття.
- Копіювання великих блоків даних погіршує локальність і може призводити до кеш-промахів на рівні CPU.
- Незмінність і функціональний стиль:
- У незмінному (immutable) стилі нові масиви - нормальна ціна за передбачуваність і відсутність побічних ефектів.
- Звичайні масиви в JavaScript не використовують структурного розділення, тому копіювання коштує O(n). Персистентні структури даних згладжують цю ціну, але це вже інші структури.
Приклади і порівняння
Копіювання і конкатенація: час і пам'ять.
const n = 100000;
const a = Array.from({ length: n }, (_, i) => i);
// O(n): копія
const b = a.slice();
// O(n): копія
const c = [...a];
// O(n + m): копія обох масивів
const d = a.concat(c);
// O(n) час, O(n) додаткова пам'ять через проміжний масив після filter
const res = a.filter(x => x % 2 === 0).map(x => x * 2);Незмінне нарощування через concat у циклі призводить до квадратичної складності.
const n = 100000;
const items = Array.from({ length: n }, (_, i) => i);
// Погано: O(n^2) через копіювання масиву на кожному кроці
let out = [];
for (const x of items) {
out = out.concat([x]); // кожен concat копіює out цілком
}
// Добре: O(n) амортизовано
let out2 = [];
for (const x of items) {
out2.push(x); // амортизовано O(1) на крок
}Видалення елемента: in-place проти створення нового масиву.
const a = [1, 2, 3, 4, 5];
const target = 3;
// In-place: O(n) час (зсув), O(1) дод. пам'ять
const i = a.indexOf(target);
if (i !== -1) a.splice(i, 1);
// Незмінно: O(n) час, O(n) пам'ять (новий масив)
const a2 = a.filter(x => x !== target);Копіювання в рекурсії: як лінійне перетворюється на квадратичне.
// Погано: на кожному кроці створюється новий масив через concat => сумарно O(n^2)
function recBuild(n, acc = []) {
if (n === 0) return acc;
return recBuild(n - 1, acc.concat(n));
}
// Краще: мутуємо акумулятор (якщо це допустимо) => O(n)
function recBuildBetter(n, acc = []) {
if (n === 0) return acc;
acc.push(n);
return recBuildBetter(n - 1, acc);
}Попереднє виділення і заповнення без зайвих копій.
const n = 100000;
const arr = new Array(n); // виділяємо довжину
for (let i = 0; i < n; i++) {
arr[i] = i * 2; // O(n) без проміжних масивів
}
// Альтернатива без проміжних копій: один прохід замість filter().map()
const src = Array.from({ length: n }, (_, i) => i);
const doubledEvens = [];
for (let i = 0; i < src.length; i++) {
const x = src[i];
if ((x & 1) === 0) doubledEvens.push(x * 2);
}Коли створення нових масивів виправдане
- Незмінні оновлення стану в UI: передбачуваність і просте визначення змін.
- Чисті функції і тестованість: відсутність побічних ефектів важливіша за невеликі накладні витрати.
- Знімки, відкати, історія змін: потрібен незалежний зліпок даних.
- Паралельна/асинхронна обробка: щоб виключити гонки при зміні спільного стану.
- Обсяг малий чи операція рідкісна, а читабельність коду важливіша за мікрооптимізації.
Практичні рекомендації
- Не копіюйте масив на кожному кроці циклу; використовуйте push, акумулятори і попереднє виділення довжини.
- Уникайте arr = arr.concat(x) у гарячих ділянках; перевага за push або push з операторами розповсюдження, якщо це один масив.
- Об'єднуйте кілька проходів в один, якщо важливі ресурси: замість filter().map() - один цикл чи reduce.
- Профілюйте для великих n: перевіряйте час, пікову пам'ять і активність збирача сміття.
- Якщо потрібна незмінність, розгляньте персистентні структури даних зі структурним розділенням, щоб знизити ціну копіювання.
- Пам'ятайте: spread і slice - це копії O(n), використовуйте їх свідомо.
- Часті вставки/видалення в середині масиву все одно коштують O(n) за часом; для таких патернів подумайте про інші структури чи про зміну підходу.
Підсумки
Створення нових масивів - це, як правило, лінійні витрати за часом і пам'яттю. Одноразова копія - це нормально, але регулярне копіювання в циклах і рекурсії швидко накопичує вартість і може перетворити алгоритм на квадратичний. Обирайте між незмінністю і продуктивністю свідомо: там, де важлива швидкість, - перевага одному проходу, in-place операціям і попередньому розподілу; там, де важлива передбачуваність, - незмінні підходи, але без зайвих копій.
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.