Що означає «час вставки»?
Час вставки - це показник того, скільки операцій (або часу) потрібно, щоб додати новий елемент у структуру даних.
Він показує, наскільки швидко структура здатна «рости» при додаванні нових даних.
1. Що відбувається під час вставки
Коли ти додаєш елемент, структура повинна:
- знайти відповідне місце (за індексом, ключем або правилом порядку);
- можливо, перемістити або зв'язати інші елементи;
- записати новий елемент у пам'ять.
Кількість цих кроків визначає часову складність вставки.
2. Приклади
| Структура даних | Час вставки | Коментар |
|---|---|---|
| Масив (Array) | O(n) | Якщо масив фіксований, може знадобитися копіювання або зсув елементів. |
| Зв'язний список (Linked List) | O(1), якщо відома позиція | Просто змінюються посилання між вузлами. |
| Хеш-таблиця (Hash Table) | O(1) у середньому | Елемент додається одразу в кошик за хешем ключа. |
| Бінарне дерево пошуку (BST) | O(log n) | Кожен крок ділить діапазон навпіл, поки не знайдеться місце. |
| Черга / стек | O(1) | Додавання йде в кінець або на початок, без обходу. |
3. Чому це важливо
Алгоритми, які часто додають елементи (наприклад, сортування, динамічні структури, потоки даних), напряму залежать від швидкості вставки. Якщо вставка дорога, уся програма сповільнюється при збільшенні кількості елементів.
4. Інтуїтивно
Уяви чергу в магазин:
- якщо просто стаєш у кінець - O(1);
- якщо потрібно влізти за алфавітом - O(n);
- якщо охоронець знає, де твоє місце за карткою (хеш) - O(1) у середньому.
Підсумок:
Час вставки - це міра того, наскільки швидко структура даних може прийняти новий елемент без перебудови або тривалого пошуку місця.
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.