Яка складність вставки в середину масиву?
Складність вставки елемента в середину масиву - O(n) (лінійна).
Чому так
Масив зберігається у безперервній області пам'яті, тому при додаванні нового елемента посередині потрібно:
- Зсунути всі елементи справа від позиції вставки на одну комірку вправо, щоб звільнити місце для нового елемента.
- Записати новий елемент у звільнену позицію.
Кожен зсув - це копіювання значення з однієї комірки в іншу, і таких операцій може бути до n (у гіршому випадку, якщо вставка майже на початку масиву).
Приклад
javascript
Початковий масив: [1, 2, 3, 4, 5]
Вставляємо 99 у позицію 2:
→ [1, 2, 99, 3, 4, 5]Щоб вставити 99, довелося зсунути [3, 4, 5] - 3 елементи.
Якби масив мав 1 000 000 елементів, довелося б зсунути майже всі.
Формально
- Найкращий випадок (у кінець) - O(1)
- Найгірший випадок (на початок або в середину) - O(n)
- Середній випадок - теж приблизно O(n/2), що за асимптотикою = O(n)
Підсумок
Вставка в середину масиву вимагає зсуву елементів і виконується за O(n). Це одна з причин, чому масиви неефективні для частих вставок і видалень.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.