Реалізація АТД (кортежі, множини, словники, звʼязні списки) та складність операцій

📌 Про що ця тема

Тут перевіряють, чи розумієш ти абстрактні типи даних (АТД) — кортежі, множини, словники, звʼязні списки — і наскільки «швидко» працюють їх основні операції. Ключове поняття — обчислювальна складність (нотація O-велике): як час роботи операції залежить від кількості елементів n.

📖 Головне

• АТД — це опис структури через набір дозволених операцій, без прив’язки до реалізації. Ти працюєш з «інтерфейсом», а не з внутрішнім устроєм.

• Кортеж (tuple) — упорядкований НЕзмінний набір елементів. Доступ за індексом — O(1). Змінити елемент не можна (у Python).

• Множина (set) — колекція УНІКАЛЬНИХ елементів без порядку. Типово реалізується через хеш-таблицю.

• Операції множини: додати, видалити, перевірити належність (in) — у середньому O(1) завдяки хешуванню. У найгіршому разі (колізії) — O(n).

• Операції над множинами: обʼєднання (|), перетин (&), різниця (-), симетрична різниця (^).

• Словник (dict) — набір пар «ключ–значення». Ключі унікальні. Теж на хеш-таблиці.

• Доступ, вставка, видалення за ключем у словнику — у середньому O(1), у найгіршому — O(n).

• Хеш-таблиця: хеш-функція перетворює ключ на номер комірки (bucket). Колізія — коли різні ключі дають один номер; вирішується ланцюжками або відкритою адресацією.

• Звʼязний список — елементи (вузли), кожен зберігає дані й посилання на наступний (однозвʼязний) або ще й на попередній (двозвʼязний).

• Вставка/видалення на початку списку — O(1). Доступ до i-го елемента чи пошук — O(n), бо треба йти по посиланнях.

• Для порівняння: у масиві (list) доступ за індексом — O(1), а вставка в середину — O(n) через зсув елементів.

• O(1) — стала складність (не залежить від n); O(log n) — логарифмічна; O(n) — лінійна; O(n²) — квадратична.

🔢 Як це працює на прикладі

Задача: перевірити, чи є число X серед n чисел.

• Якщо дані у множині (set): X in S — одна операція хешування, O(1). Для n=1 000 000 — практично миттєво.

• Якщо дані у звʼязному списку: доводиться переглядати вузли по черзі, поки не знайдемо X або не дійдемо до кінця — O(n), до 1 000 000 кроків.

Висновок: для частих перевірок належності обирають множину, а не список.

Другий приклад: словник d = {"Київ": 3, "Львів": 7}. Звернення d["Львів"] — хеш від "Львів" дає номер комірки, звідти одразу беремо 7 — O(1).

⚠️ Типові помилки

• Плутають кортеж і список: кортеж НЕзмінний, список — змінний.

• Вважають, що множина/словник зберігають порядок додавання — за класичним визначенням порядок не гарантований (хоча в сучасному Python dict зберігає порядок вставки — на іспиті орієнтуйся на АТД).

• Пишуть, що пошук у множині O(n): у середньому це O(1), помилка саме тут.

• Думають, що вставка в звʼязний список завжди O(1): швидка лише якщо вузол уже знайдено; пошук місця — O(n).

• Плутають доступ за індексом (масив — O(1)) із доступом у звʼязному списку (O(n)).

🎯 Що завчити напамʼять

• set і dict: пошук/вставка/видалення — у середньому O(1).

• Звʼязний список: доступ/пошук — O(n), вставка на початку — O(1).

• Масив: доступ за індексом O(1), вставка в середину O(n).

• Кортеж — незмінний, список — змінний.

• Множина зберігає лише унікальні елементи.

🧠 Перевір себе

1. Яка середня складність перевірки in для множини?

2. Чим кортеж відрізняється від списку?

3. Чому пошук i-го елемента у звʼязному списку повільніший, ніж у масиві?

4. Що таке колізія в хеш-таблиці?

Відповіді: 1 — O(1); 2 — кортеж незмінний, список змінний; 3 — у списку немає індексного доступу, треба йти по посиланнях O(n), у масиві адреса обчислюється одразу O(1); 4 — коли різні ключі дають однаковий номер комірки.