순차탐색

순차 탐색(Sequential Search)

- 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘

  이다.

- 순차 탐색은 한쪽 방향으로만 탐색을 수행한다고 해서 선형 탐색이라고 부르기도한다.

 

순차탐색은 처음부터 끝까지 모든 요소를 검사하기 때문에 비효율적이다.

하지만 정렬되어 있지 않은 데이터 집합 속에서 원하는 데이터를 찾을 수 있는 유일한 방법이고 구현 또한 간단해서 버그를 만들 가능성이 적다는 장점이 있어서, 극적으로 높은 성능이 필요하지 않거나 데이터 집합의 크기가 작은 곳에서는 자주 사용된다.

 

자기 구성 순차 탐색

 

자기 구성법이란

- 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치함으로써, 순차 탐색의 검색 효율을 끌어올리는 것을 말한다.

- 자기 구성법은 자주 사용되는 항목을 어떻게 선별하는가에 따라서 세 가지 방법으로 나뉜다.

 

1. 전진 이동법(Move To Front)

2. 전위법(Transpose)

3. 빈도 계수법(Frequency Count)

 

전진 이동법(Move To Front)

 

- 어느 항목이 한번 탐색되어지면 그 항목을 데이터 집합의 가장 앞에 위치시키는 방법이다.

- 전진 이동법이 항상 모든 경우에 적합한 것은 아니다. 데이터 집합 내의 특정한 항목들이

  집중적으로 탐색 대상이 된다는 것은 흔한 일이 아니기 때문이다.

  따라서 전진 이동법은 한번 탐색된 항목이 이어서 또 다시 검색될 가능성이 높은 데이터 집합

  에서만 사용해야 한다.

 

전위법(Transpose)

 

- 탐색된 항목을 바로 이전 항목과 교환하는 알고리즘이다.

- 이전 항목과 교환한다는 점 말고는 기본적으로 전진 이동법과 같은 전략을 취하는 알고리즘..

- 자주 탐색되는 항목들이 데이터 집합의 앞쪽으로 모이게 되고, 이로 인해서 자주 탐색되는

  항목들은 빠르게 찾을 수 있게 된다.

 

계수법(Frequency count method)

 

- 데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고,,