Последовательный доступ: различия между версиями
Patarakin (обсуждение | вклад) |
|||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
В [[Информатика|информатике]] '''последовательный доступ''' означает, что доступ к группе элементов (например, данные в памяти, на диске или на [[Магнитная лента|магнитной ленте]]) осуществляется в заранее заданном порядке. Последовательный доступ иногда является единственным способом обратиться к данным, как, например, к записям на магнитной ленте. Кроме того, иногда это может быть всего лишь одним из методов доступа к данным, например, мы можем предпочесть этот способ если мы хотим обработать последовательность элементов данных по порядку. | В [[Информатика|информатике]] '''последовательный доступ''' означает, что доступ к группе элементов (например, данные в памяти, на диске или на [[Магнитная лента|магнитной ленте]]) осуществляется в заранее заданном порядке. Последовательный доступ иногда является единственным способом обратиться к данным, как, например, к записям на магнитной ленте. Кроме того, иногда это может быть всего лишь одним из методов доступа к данным, например, мы можем предпочесть этот способ если мы хотим обработать последовательность элементов данных по порядку. | ||
Что касается [[Структура данных|структур данных]], то она (структура данных) подразумевает последовательный доступ, если за каждый конкретный момент времени можно обратиться лишь к одному элементу структуры, причем доступ к элементам происходит в определённом порядке. Каноническим примером служит [[связанный список]]. Индексация в списке с последовательным доступом требует [[«O» большое и «o» малое|O]](''k'') времени, где ''k'' — индекс. В результате, многие алгоритмы, такие как [[быстрая сортировка]] и [[двоичный поиск]] вырождаются в малопригодные алгоритмы, которые ещё менее эффективны, чем их упрощенные альтернативы; эти алгоритмы бесполезны без [[Произвольный доступ|произвольного доступа]]. С другой стороны, некоторые алгоритмы, обычно те, которые не выполняют индексацию, требуют только последовательный доступ, как например, [[сортировка слиянием]], что позволяет избавиться от указанных проблем. | Что касается [[Структура данных|структур данных]], то она (структура данных) подразумевает последовательный доступ, если за каждый конкретный момент времени можно обратиться лишь к одному элементу структуры, причем доступ к элементам происходит в определённом порядке. Каноническим примером служит [[связанный список]]. Индексация в списке с последовательным доступом требует [[«O» большое и «o» малое|O]](''k'') времени, где ''k'' — индекс. В результате, многие алгоритмы, такие как [[быстрая сортировка]] и [[двоичный поиск]] вырождаются в малопригодные алгоритмы, которые ещё менее эффективны, чем их упрощенные альтернативы; эти алгоритмы бесполезны без [[Произвольный доступ|произвольного доступа]]. С другой стороны, некоторые алгоритмы, обычно те, которые не выполняют индексацию, требуют только последовательный доступ, как например, [[сортировка слиянием]], что позволяет избавиться от указанных проблем. | ||
---- | |||
[[Категория:Структуры данных]] | [[Категория:Структуры данных]] | ||
Текущая версия на 12:33, 19 октября 2022
В информатике последовательный доступ означает, что доступ к группе элементов (например, данные в памяти, на диске или на магнитной ленте) осуществляется в заранее заданном порядке. Последовательный доступ иногда является единственным способом обратиться к данным, как, например, к записям на магнитной ленте. Кроме того, иногда это может быть всего лишь одним из методов доступа к данным, например, мы можем предпочесть этот способ если мы хотим обработать последовательность элементов данных по порядку.
Что касается структур данных, то она (структура данных) подразумевает последовательный доступ, если за каждый конкретный момент времени можно обратиться лишь к одному элементу структуры, причем доступ к элементам происходит в определённом порядке. Каноническим примером служит связанный список. Индексация в списке с последовательным доступом требует O(k) времени, где k — индекс. В результате, многие алгоритмы, такие как быстрая сортировка и двоичный поиск вырождаются в малопригодные алгоритмы, которые ещё менее эффективны, чем их упрощенные альтернативы; эти алгоритмы бесполезны без произвольного доступа. С другой стороны, некоторые алгоритмы, обычно те, которые не выполняют индексацию, требуют только последовательный доступ, как например, сортировка слиянием, что позволяет избавиться от указанных проблем.
