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

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

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

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

Контент

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

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

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

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

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

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

Створення нового масиву найчастіше додає лінійні витрати: 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: передбачуваність і просте визначення змін.
- Чисті функції і тестованість: відсутність побічних ефектів важливіша за невеликі накладні витрати.
- Знімки, відкати, історія змін: потрібен незалежний зліпок даних.
- Паралельна/асинхронна обробка: щоб виключити гонки при зміні спільного стану.
- Обсяг малий чи операція рідкісна, а читабельність коду важливіша за мікрооптимізації.

## Практичні рекомендації

1. Не копіюйте масив на кожному кроці циклу; використовуйте push, акумулятори і попереднє виділення довжини.
2. Уникайте arr = arr.concat(x) у гарячих ділянках; перевага за push або push з операторами розповсюдження, якщо це один масив.
3. Об'єднуйте кілька проходів в один, якщо важливі ресурси: замість filter().map() - один цикл чи reduce.
4. Профілюйте для великих n: перевіряйте час, пікову пам'ять і активність збирача сміття.
5. Якщо потрібна незмінність, розгляньте персистентні структури даних зі структурним розділенням, щоб знизити ціну копіювання.
6. Пам'ятайте: spread і slice - це копії O(n), використовуйте їх свідомо.
7. Часті вставки/видалення в середині масиву все одно коштують O(n) за часом; для таких патернів подумайте про інші структури чи про зміну підходу.

## Підсумки

Створення нових масивів - це, як правило, лінійні витрати за часом і пам'яттю. Одноразова копія - це нормально, але регулярне копіювання в циклах і рекурсії швидко накопичує вартість і може перетворити алгоритм на квадратичний. Обирайте між незмінністю і продуктивністю свідомо: там, де важлива швидкість, - перевага одному проходу, in-place операціям і попередньому розподілу; там, де важлива передбачуваність, - незмінні підходи, але без зайвих копій.

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

Для рев’юера

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

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