Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Яка складність доступу до елемента за індексом?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)Складність **доступу до елемента за індексом** у зв'язаному списку - **O(n)** (лінійна). **Ключове:** щоб дістатися до вузла з індексом `i`, програма має почати з `head` і пройти всі попередні вузли, тому доступ до елемента за індексом виконується за O(n).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)ЗображенняСкладність **доступу до елемента за індексом** у зв'язаному списку - **O(n)** (лінійна). --- ### **Чому так** У зв'язаному списку елементи **не лежать поспіль у пам'яті**, як у масиві. Кожен елемент (вузол) зберігає тільки: - свої дані, - посилання на **наступний** вузол (або ще й на попередній - у двозв'язному списку). Тому, щоб дістатися до вузла з індексом `i`, програма має **почати з** `head` **і пройти всі попередні вузли**: ```javascript head → [0] → [1] → [2] → [3] ↑ потрібно пройти все до цього, щоб дістатися до [3] ``` --- ### **Приклад** Якщо список містить 1 000 елементів, і потрібно отримати елемент з індексом 900, алгоритм має пройти **900 кроків**. --- ### **Формально** | Операція | Складність | |---|---| | Доступ до першого елемента | **O(1)** | | Доступ до останнього (через tail) | **O(1)** - якщо `tail` зберігається окремо | | Доступ до елемента за індексом i | **O(n)** | | Середня складність | **O(n/2)** ≈ **O(n)** | --- ### **Порівняння з масивом** | Структура | Доступ за індексом | |---|---| | **Масив** | **O(1)** - миттєво (адреса обчислюється) | | **Зв'язаний список** | **O(n)** - потрібно пройти всі попередні вузли | --- **Підсумок:** > У зв'язаному списку доступ до елемента за індексом виконується за **O(n)**, > тому що потрібно пройти всі попередні вузли, починаючи з `head`.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.