가장 단순한 탐색 방법

위치 KEY에서 명령어 LDA KEY는 이제 원하는 정보를 rA로 가져올 것이다.

이 프로그램의 분석은 직접적이며, 알고리즘 S의 실행 시간이 두 가지에 의존함을 보여준다.

프로그램 S는 5C - 2S + 3 단위의 시간이 걸린다. 탐색이 K = Kᵢ를 성공적으로 찾으면, C = i, S = 1이다; 따라서 총 시간은 (5i + 1)u이다. 반면에 탐색이 실패하면, C = N, S = 0이므로 총 시간은 (5N + 3)u이다. 모든 입력 키가 동일한 확률로 발생하면, 성공적인 탐색에서 C의 평균값은

프로그램 S는 5C - 2S + 3 단위의 시간이 걸린다. 탐색이 K = Kᵢ를 성공적으로 찾으면, C = i, S = 1이다; 따라서 총 시간은 (5i + 1)u이다. 반면에 탐색이 실패하면, C = N, S = 0이므로 총 시간은 (5N + 3)u이다. 모든 입력 키가 동일한 확률로 발생하면, 성공적인 탐색에서 C의 평균값은

이며, 표준편차는 물론 상당히 크다, 약 0.289N (연습문제 1 참조).

위의 알고리즘은 분명히 모든 프로그래머에게 익숙하다. 그러나 너무 적은 사람들이 이것이 순차 탐색을 하는 항상 올바른 방법은 아니라는 것을 알고 있다! 레코드 목록이 상당히 짧지 않은 한, 간단한 변경이 알고리즘을 더 빠르게 만든다:

위의 알고리즘은 분명히 모든 프로그래머에게 익숙하다. 그러나 너무 적은 사람들이 이것이 순차 탐색을 하는 항상 올바른 방법은 아니라는 것을 알고 있다! 레코드 목록이 상당히 짧지 않은 한, 간단한 변경이 알고리즘을 더 빠르게 만든다:

알고리즘 Q (빠른 순차 탐색). 이 알고리즘은 알고리즘 S와 같지만, 파일 끝에 더미 레코드 Rₙ₊₁이 있다고 가정한다.

- Q1. [초기화] i ← 1로 설정하고, Kₙ₊₁ ← K로 설정한다.