[자료구조] Sequential access & Random access

Sequential access(순차 접근)

 Sequential access(순차 접근)은 컴퓨터 과학에서 데이터에 접근하는 방법중 하나로 순서가 정해진 원소 그룹을 접근하는 순차적으로 접근하는 방법이다. 데이터 구조에서 데이터 구조는 한 가지 특정 순서로만 포함된 값을 방문할 수 있는 경우 순차적 접근이 가능하다고 한다.

 대표적인 예로 연결 리스트 (Linked Lsit)가 있다. 리스트 (List)를 인덱싱하려면 $O(n)$ 시간이 필요하며 여기서 $n$은 인덱스다. 그 결과 퀵소트 (Quick Sort)나 이진 탐색 (Binary Search)과 같은 많은 알고리즘이 더욱 비효율적이게 된다.

 

Random access(비순차 접근)

 Random access(비순차 접근)은 집합 내의 요소의 주소를 알고 있다면 요소의 개수와 무관하게 모든 요소에 대하여 쉽고 효율적으로 동일한 시간에 접근할 수 있는 방식이다. 컴퓨터 과학에서 이것은 일반적으로 저장된 순서대로 데이터를 검색해야 하는 Sequential access(순차 접근)과 대비된다.

 처음에는 어떤 시퀀스가 요구되든 레코드를 찾을 수 있어야 하기 때문에 무작위 접속이라는 용어를 사용하였지만 그 위치와 무관하게 직접 레코드에 접근 할 수 있기 때문에 "직접 접속"이라는 용어가 인기를 얻게 되었다.

 자료 구조에서 직접 액세스는 목록의 어떤 항목에도 일정한 시간(목록의 위치와 목록 크기에 관계없이)에 접근할 수 있는 능력을 의미한다. 배열 이외에 이러한 기능을 할 수 있는 자료 구조는 거의 없다. Random access(비순차 접근)은 이진 탐색 (Binary Search), 일부 정렬 알고리즘과 같은 많은 알고리즘에서 요구되는 최소한의 조건이다.