순차 탐색

순차 탐색(sequential search)은 정렬되지 않은 레코드들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법으로 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법이다.

시간복잡도

순차 탐색의 시간복잡도는 두 가지 경우로 나누어볼 수 있다. 탐색이 성공하는 경우에는 리스트에 있는 키의 위치에 따라 비교 횟수가 결정되는데ㅣ, 모든 키가 탐색될 확률이 동일하다고 가정하면 평균 비교 횟수는 다음과 같다.

${1+2+3+\cdots +n \over n}={n+1 \over 2}$

따라서 순차 탐색은 탐색에 성공할 경우 평균 ${n+1 \over 2}$번 비교하고, 탐색이 실패한 경우 n번 비교한다. 순차 탐색의 시간 복잡도는 $O(n)$이 된다.