Яка складність доступу до елемента в масиві?

Складність доступу до елемента в масиві - O(1) (постійна).

---

#Чому так

Масив зберігається у безперервній області пам'яті, і кожен елемент має фіксований розмір. Щоб знайти елемент з індексом i, процесор просто обчислює його адресу за формулою:

[ \text{адреса} = \text{адреса_початку} + i \times \text{розмір_елемента} ]

Тобто доступ не потребує обходу чи пошуку - лише одна арифметична дія і одне звернення до пам'яті.

---

#Що це означає

• Неважливо, скільки елементів у масиві - 10 чи 10 мільйонів, час отримання будь-якого елемента однаковий.
• Тому операції на кшталт arr[i] виконуються за постійний час.

---

#Важливо

• O(1) - це ідеальний випадок для доступу.
• Але пошук за значенням (наприклад, "знайти число 42 в масиві") - це вже O(n), тому що потрібно перевірити всі елементи.

---

Підсумок:

Доступ до елемента масиву за індексом виконується за O(1) - миттєво, незалежно від розміру масиву.