Skip to main content

Яка складність вставки елемента в середину масиву?

АлгоритмиJunior~2 хв читання
Запропонувати правку

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

Вставка елемента в середину масиву з неперервним розміщенням (статичний масив, динамічний масив, JS Array, C++ vector, Java ArrayList) має часову складність O(n) і додаткову пам'ять O(1). Причина - необхідність зсуву всіх елементів правіше позиції вставки.

Детальне пояснення

Чому O(n):

  • Масив зберігає елементи в суміжній пам'яті. Щоб звільнити «дірку» в середині, всі елементи справа від позиції i (їх k штук) потрібно зсунути на одну позицію: переміщень буде k, де в найгіршому випадку k ≈ n.
  • Навіть якщо динамічний масив має запас за capacity (ємністю) і не робить реалокацію, зсув елементів лишається необхідним, тому вставка в середину все одно O(n).
  • За пам'яттю алгоритм вимагає O(1) дод. пам'яті (крім можливої рідкісної реалокації при переповненні capacity, яка копіює всі n елементів і сама по собі коштує O(n)).

Межі та окремі випадки

  • Вставка на початок: O(n) (зсув усіх елементів).
  • Вставка в кінець: амортизовано O(1) за наявності вільної ємності; за її відсутності відбувається реалокація, O(n).
  • Відсортований масив: пошук позиції двійковим пошуком O(log n) + зсув O(n), сумарно O(n).
  • Точна оцінка через k: якщо справа від позиції вставки k елементів, час = Θ(k). У середньому при рівномірній позиції k ≈ n/2, але асимптотика лишається O(n).

Порівняння з іншими структурами

  • Зв'язний список: вставка за вже знайденим вузлом - O(1), але доступ за індексом і пошук позиції - O(n); гірша локальність і кешованість.
  • Deque/двостороння черга: швидкі вставки на кінцях, але вставка в середину зазвичай теж O(n).
  • Спеціалізовані структури (gap buffer, rope, B-дерева, списочні вектори) можуть покращувати вставки в середину ціною інших компромісів, але звичайний масив, ні.

Практичні зауваження

  • Якщо потрібно багато вставок у середину, масив - не найкраща структура. Розгляньте структури з дешевшими вставками, або змінюйте алгоритм (накопичуйте зміни і застосовуйте пакетно).
  • Якщо вставки рідкісні, а читання за індексом важливе, масив лишається оптимальним вибором.

Приклади коду

JavaScript (Array):

js
// Вставка в середину, O(n) через зсув елементів const arr = [1, 2, 3, 4, 5]; const index = Math.floor(arr.length / 2); // позиція вставки const value = 99; arr.splice(index, 0, value); // → [1, 2, 99, 3, 4, 5]

C++ (std::vector):

cpp
#include <vector> #include <cstddef> int main() { std::vector<int> v{1, 2, 3, 4, 5}; std::size_t index = v.size() / 2; int value = 99; // O(n): переміщення/копіювання елементів справа від index v.insert(v.begin() + index, value); return 0; }

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

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

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