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