Почему доступ к элементу массива по индексу выполняется за константное время O(1)?

Прямой доступ за O(1) возможен благодаря непрерывному расположению элементов в памяти и арифметике указателей.

Механизм:

1. Базовый адрес: При создании массива выделяется непрерывный блок памяти. Адрес первого элемента (array[0]) известен.
2. Одинаковый размер: Все элементы имеют идентичный размер в байтах (sizeof(type)), известный на этапе компиляции.
3. Вычисление адреса: Адрес любого элемента вычисляется по простой формуле: Адрес array[i] = Базовый адрес + (i * sizeof(тип_элемента))

Это вычисление — простая арифметическая операция, не требующая обхода структуры данных.

Пример на Java:

int[] numbers = {10, 20, 30, 40, 50}; // Базовый адрес, допустим, 0x1000
// Размер int в Java обычно 4 байта.
// numbers[2] находится по адресу: 0x1000 + (2 * 4) = 0x1008
System.out.println(numbers[2]); // 30 - доступ мгновенный

Сравнение со списком (LinkedList):

// LinkedList: для доступа к элементу с индексом n
// требуется последовательный обход n узлов через ссылки (next).
// Это операция O(n).
LinkedList<Integer> list = new LinkedList<>();
// list.get(1000) может потребовать 1000 переходов по ссылкам.

Итог: Массивы жертвуют гибкостью (фиксированный размер) в пользу максимальной скорости произвольного доступа, что делает их фундаментальной структурой для алгоритмов, чувствительных к производительности.