Произвольный доступ: различия между версиями
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Patarakin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
В [[Информатика|информатике]] под '''произвольным доступом''' (также называемым '''случайным доступом''', понимают возможность обратиться к любому элементу [[Последовательность|последовательности]] за равные промежутки времени, не зависящие от размеров последовательности (в отличие от [[Последовательный доступ|последовательного доступа]], когда чем дальше расположен элемент, тем больше требуется времени для доступа). | |||
В [[Информатика|информатике]] под '''произвольным доступом''' (также называемым '''случайным доступом''', | |||
Говорят, что [[структура данных]] поддерживает произвольный доступ, если возможен доступ к любому элементу за константное время <math>O(1)</math> по отношению к количеству элементов в ней, равное вне зависимости от позиции элемента. Немногие структуры данных могут это обеспечить, только [[Индексный массив|массивы]] (и сходные структуры, такие как динамический массив). Поддержка произвольного доступа структурой данных является критичной для реализации многих [[алгоритм]]ов (например, для [[быстрая сортировка|быстрой сортировки]] и [[двоичный поиск|двоичного поиска]]). | Говорят, что [[структура данных]] поддерживает произвольный доступ, если возможен доступ к любому элементу за константное время <math>O(1)</math> по отношению к количеству элементов в ней, равное вне зависимости от позиции элемента. Немногие структуры данных могут это обеспечить, только [[Индексный массив|массивы]] (и сходные структуры, такие как динамический массив). Поддержка произвольного доступа структурой данных является критичной для реализации многих [[алгоритм]]ов (например, для [[быстрая сортировка|быстрой сортировки]] и [[двоичный поиск|двоичного поиска]]). | ||
| Строка 6: | Строка 5: | ||
Скорости последовательного и произвольного доступа могут различаться на 4 порядка. | Скорости последовательного и произвольного доступа могут различаться на 4 порядка. | ||
[[Категория:Структуры данных]] | [[Категория:Структуры данных]] | ||
Текущая версия на 16:22, 23 ноября 2022
В информатике под произвольным доступом (также называемым случайным доступом, понимают возможность обратиться к любому элементу последовательности за равные промежутки времени, не зависящие от размеров последовательности (в отличие от последовательного доступа, когда чем дальше расположен элемент, тем больше требуется времени для доступа).
Говорят, что структура данных поддерживает произвольный доступ, если возможен доступ к любому элементу за константное время [math]\displaystyle{ O(1) }[/math] по отношению к количеству элементов в ней, равное вне зависимости от позиции элемента. Немногие структуры данных могут это обеспечить, только массивы (и сходные структуры, такие как динамический массив). Поддержка произвольного доступа структурой данных является критичной для реализации многих алгоритмов (например, для быстрой сортировки и двоичного поиска).
Скорости последовательного и произвольного доступа могут различаться на 4 порядка.
