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

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

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

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

Контент

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

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

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

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

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

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

Вставка в кінець динамічного масиву зазвичай амортизовано займає O(1), бо не потребує зсуву вже наявних елементів: достатньо записати значення за індексом size і збільшити size. Вставки на початок або в середину вимагають зсуву великої кількості елементів, що дає O(n) і гіршу кеш-локальність. Рідкісні перерозподіли пам'яті при рості ємності роблять додавання в кінець «майже завжди» O(1).

## Детальний розбір

### Як влаштований динамічний масив

- Масив зберігає елементи в неперервній ділянці пам'яті (contiguous memory).
- Є два числа: size (скільки елементів фактично) і capacity/ємність (скільки елементів можна зберігати без перевиділення пам'яті).
- При заповненні capacity масив зазвичай «росте» кратно (наприклад, у 1.5-2 рази): виділяється новий блок пам'яті, і всі елементи копіюються в нього.

### Що відбувається при вставці в кінець

- Якщо є вільна ємність: записується елемент за індексом size, size збільшується на 1.
- Якщо ємність вичерпана: один рідкісний «дорогий» крок перерозподілу (realloc + копіювання всіх елементів), після чого знову багато дешевих вставок.
- Підсумок: амортизована складність O(1), чудовий кеш-профіль (послідовний запис), мінімум переміщень даних.

### Що відбувається при вставці на початок/у середину

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

### Амортизована складність

Стратегія росту ємності (зазвичай геометрична: ×1.5-2) гарантує, що «дорогі» перерозподіли трапляються рідко. У перерахунку на послідовність з m додавань середня вартість однієї операції append стає константною: O(1) амортизовано.

## Приклад на JavaScript

Проста ілюстрація часу виконання різних видів вставок (значення N підберіть під своє середовище, щоб не «заморозити» вкладку):

```
const N = 100_000; // зменшіть за потреби

console.time('push end');
let a = [];
for (let i = 0; i < N; i++) a.push(i);
console.timeEnd('push end');

console.time('unshift begin');
let b = [];
for (let i = 0; i < N; i++) b.unshift(i);
console.timeEnd('unshift begin');

console.time('splice middle');
let c = [];
for (let i = 0; i < N; i++) c.push(i);
// Вставимо в середину N/10 разів, щоб не було занадто довго
for (let i = 0; i < N / 10; i++) c.splice(Math.floor(c.length / 2), 0, i);
console.timeEnd('splice middle');
```

Очікувано: push працює помітно швидше, ніж unshift/splice, тому що не потребує масових зсувів.

## Практичні висновки для web-розробника

- Для черг і стеків використовуйте операції, що працюють з кінцем масиву: push/pop, найдешевші.
- Якщо часто потрібен «перший елемент», уникайте частих unshift/shift. Краще використовуйте двосторонню чергу (deque) на двох стеках:

```
class Deque {
  constructor() { this.left = []; this.right = []; }
  pushBack(x) { this.right.push(x); }
  pushFront(x) { this.left.push(x); }
  popFront() {
    if (!this.left.length) while (this.right.length) this.left.push(this.right.pop());
    return this.left.pop();
  }
  popBack() {
    if (!this.right.length) while (this.left.length) this.right.push(this.left.pop());
    return this.right.pop();
  }
}

// Амортизовано O(1) без масових зсувів масиву
```

## Винятки й нюанси

- TypedArray у JS має фіксований розмір: «вставка в кінець» неможлива без створення нового буфера й копіювання (O(n)).
- Незмінні оновлення (наприклад, [...arr, x] або arr.concat(x)) завжди створюють новий масив і копіюють елементи, це O(n). Тут «ефективність вставки в кінець» стосується змінюваних масивів.
- JS-рушії оптимізують push/pop (fast path). Операції unshift/shift часто вимагають переміщення елементів і можуть призводити до деградації внутрішнього формату масиву.
- Для дуже маленьких масивів різниця може бути непомітною, але при рості N ефект стає суттєвим.

## Висновок

Вставка в кінець динамічного масиву ефективніша, бо не потребує зсуву наявних елементів і використовує неперервну пам'ять, що дає амортизовану складність O(1) і кращу кеш-локальність. Вставка на початок або в середину вимагає переміщення O(n) елементів і тому значно повільніша.

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

Для рев’юера

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

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