Послідовний доступ

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Порівняння послідовного доступу з довільним доступом.

В інформатиці послідовний доступ означає, що доступ до групи елементів (наприклад, дані в пам'яті, на диску або на магнітній стрічці) здійснюється в заздалегідь заданому порядку. Послідовний доступ іноді є єдиним способом звернутися до даних, як, наприклад, до записів на магнітній стрічці. Крім того, іноді це може бути всього лише одним з методів доступу до даних, наприклад, ми можемо віддати перевагу цьому способу, якщо хочемо опрацювати послідовність елементів даних по порядку.

Що стосується структур даних, то вона (структура даних) має на увазі послідовний доступ, якщо за кожен конкретний момент часу можна звернутися лише до одного елементу структури, причому доступ до елементів відбувається в певному порядку. Канонічним прикладом служить зв'язаний список. Індексація в списку з послідовним доступом вимагає O (k) часу, де k - індекс. У результаті, багато алгоритмів, таких як швидке сортування і двійковий пошук вироджуються в малопридатні алгоритми, які ще менш ефективні, ніж їх спрощені альтернативи; ці алгоритми марні без довільного доступу. З іншого боку, деякі алгоритми, зазвичай ті, які не виконують індексацію, вимагають тільки послідовний доступ, як наприклад, сортування злиттям, що дозволяє позбавитися від зазначених проблем.

Див. також[ред.ред. код]