Какова временная сложность записи значения по индексу в массиве?

Временная сложность записи по индексу в массиве

Массив — это структура данных, которая хранит элементы в последовательных ячейках памяти. Каждый элемент имеет фиксированный размер, и адрес элемента вычисляется по формуле: базовый_адрес + индекс * размер_элемента. Это позволяет получить доступ к любому элементу напрямую, без необходимости проходить по всем предыдущим элементам.

Почему это O(1)?

Операция записи по индексу включает в себя только вычисление адреса и запись значения в память. Время выполнения этих шагов не зависит от количества элементов в массиве. Даже если массив содержит миллион элементов, запись по индексу 0 и по индексу 999999 займет одинаковое время.

Пример на JavaScript

const arr = [10, 20, 30, 40, 50];
arr[2] = 100; // Запись по индексу 2 — O(1)
console.log(arr); // [10, 20, 100, 40, 50]

В этом примере мы изменяем третий элемент массива. Операция выполняется мгновенно, независимо от длины массива.

Где это применяется?

• В алгоритмах сортировки, где требуется часто менять элементы местами.
• В реализации динамических массивов (например, ArrayList в Java или list в Python), где запись по индексу также O(1).
• В любых задачах, где нужен быстрый доступ к данным по позиции.

Вывод

Запись по индексу в массиве — одна из самых быстрых операций в программировании. Используйте массивы, когда требуется частый доступ к элементам по их позиции, и избегайте их, если нужно часто вставлять или удалять элементы в середине (это O(n)).