Массив — это непрерывный блок памяти, содержащий элементы одного типа, индексируемые с 0. Поскольку элементы располагаются рядом друг с другом, адрес элемента i вычисляется прямо как base + i * elementSize, что обеспечивает O(1) случайный доступ.
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Операция | Время |
|---|---|
| Доступ по индексу | O(1) |
| Поиск (неотсортированный) | O(n) |
| Добавление (динамический) | O(1) амортизированная |
| Вставка/удаление в начале/середине | O(n) |
Массивы — это основание, на котором строятся большинство других структур — строки, хеш-таблицы, кучи и динамические списки все построены на них.
Их локальность кэша часто делает массив с "более медленной" сложностью O(n) быстрее структуры на основе указателей с "более быстрой" асимптотикой в реальных бенчмарках.