Произвольный доступ

Сравнение произвольного доступа с последовательным доступом.

В информатике под произвольным доступом (также называемым случайным доступом, англ. random access) понимают возможность обратиться к любому элементу последовательности за равные промежутки времени, не зависящие от размеров последовательности (в отличие от последовательного доступа, когда чем дальше расположен элемент, тем больше требуется времени для доступа).

Говорят, что структура данных поддерживает произвольный доступ, если возможен доступ к любому элементу за константное время $O(1)$ по отношению к количеству элементов в ней, равное вне зависимости от позиции элемента. Немногие структуры данных могут это обеспечить, только массивы (и сходные структуры, такие как динамический массив). Поддержка произвольного доступа структурой данных является критичной для реализации многих алгоритмов (например, для быстрой сортировки и двоичного поиска).

Скорости последовательного и произвольного доступа могут различаться на 4 порядка.

См. также

• Запоминающее устройство с произвольным доступом