순차 탐색의 비용과 선택 기준
순차 탐색의 평균·최악 시간 복잡도와 센티넬 최적화, 이분 탐색·해시 조회와의 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
정렬하지 않은 데이터를 처음부터 훑는 방식
순차 탐색은 배열이나 리스트의 앞쪽 원소부터 목표 값과 하나씩 비교한다. 일치하는 값을 만나면 그 인덱스를 반환하고, 끝까지 찾지 못하면 실패 코드인 -1을 돌려준다.
정렬이나 임의 접근은 필요하지 않다. 순차 접근이 가능한 자료구조라면 적용할 수 있으며, 중복 값이 있으면 처음 발견한 위치를 반환한다. 빈 컬렉션이나 None 입력도 실패로 처리한다.
비교 횟수로 보는 탐색 비용
목표 값이 마지막에 있거나 아예 없으면 모든 원소를 확인해야 하므로 최악 시간 복잡도는 O(n)이다. 반대로 첫 원소가 목표 값이면 비교는 1회로 끝나며 O(1)이다.
평균 시간 복잡도 역시 O(n)이다. 값을 찾을 확률을 q, 값이 존재할 때 위치가 균등하게 분포한다고 가정하면 기대 비교 횟수는 다음과 같다.
E[C] = q·(n+1)/2 + (1−q)·n = n − q·(n−1)/2
항상 존재(q=1)하는 경우는 (n+1)/2 ≈ 0.5n, 절반 확률로 존재(q=0.5)하면 (3n+1)/4 ≈ 0.75n이 된다. 입력 외에 필요한 메모리는 상수 크기이므로 공간 복잡도는 O(1)이다.
일치하는 순간 반환하므로 값이 앞쪽에 몰릴수록 기대 비용은 낮아진다. 반면 실패 탐색이 잦으면 매번 끝까지 검사하게 되어 평균 비용이 커진다.
준비 비용이 더 큰 상황에서의 선택
정렬과 인덱스를 만들 필요가 없다는 점은 작은 컬렉션이나 일시적인 데이터에서 유리하다. 설정 파라미터, 피처 플래그 목록, 환경 변수 맵의 키 목록처럼 초기화 단계에 한 번만 조회하는 대상이라면 정렬이나 인덱싱 비용을 피할 수 있다.
스트리밍과 파일 스캔처럼 순차 접근에 맞춰진 환경도 후보가 된다. 캐시와 프리페치의 이점을 얻을 수 있고, I/O 지연이 지배적인 상황에서는 선형 스캔 비용의 비중이 상대적으로 작을 수 있다. 추가 인덱스나 해시를 둘 메모리가 없는 고정 크기 버퍼에서도 같은 이유로 선택할 수 있다.
다만 n이 커질수록 성능은 선형으로 저하된다. 빈번한 검색이나 대규모 데이터셋에서는 정렬 후 이분 탐색을 적용하거나 해시 인덱스를 사용하는 편이 낫다.
경계 검사와 병렬 비교를 다루는 방법
센티넬 기법은 루프 안의 경계 검사 분기를 줄이는 방식이다. 블록 스캔과 SIMD 스캔은 고정 폭 비교를 병렬화해 상수 계수를 낮춘다. 어느 경우든 시간 복잡도의 차수는 O(n)으로 남는다.
입력은 컬렉션 A(길이 n)와 목표 값 x다. i=0부터 n-1까지 A[i] == x를 검사하며, 성공하면 인덱스를 반환한다. A가 None이거나 비시퀀스면 즉시 실패를 반환하고, 비교할 수 없는 타입이 섞인 경우에는 타입 예외를 처리해야 한다.
파이썬 구현에서 확인할 경계 처리
전제조건: CPython 3.10+, 표준 라이브러리만 사용.
from collections.abc import Sequence
from typing import Any
def linear_search(seq: Sequence, target: Any) -> int:
if not isinstance(seq, Sequence):
return -1
n = len(seq)
for i in range(n):
if seq[i] == target:
return i
return -1
def linear_search_sentinel(seq: list, target: Any) -> int:
# 센티넬 기법: 리스트 복사 없이 끝에 임시 값 삽입 후 복구
if not isinstance(seq, list):
return -1
n = len(seq)
if n == 0:
return -1
last = seq[-1]
seq[-1] = target # 센티넬
i = 0
while seq[i] != target:
i += 1
seq[-1] = last # 복구
if i < n-1 or last == target:
return i
return -1
# 사용 예시
data = [9, 3, 7, 3, 5]
print(linear_search(data, 7)) # 2
print(linear_search(data, 4)) # -1linear_search는 범용 시퀀스를 대상으로 O(n) 비교를 수행한다. linear_search_sentinel은 경계 비교 분기를 최소화하는 미세 최적화이며 리스트에만 적용한다.
이분 탐색과 해시 조회의 차이
| 항목 | 순차 탐색 (Linear) | 이분 탐색 (Binary) | 해시 조회 (Hash) |
|---|---|---|---|
| 성능 | O(n), 작은 n에서 상수 계수 유리 | O(log n), 정렬 필요 | 평균 O(1), 최악 O(n) |
| 확장성 | 낮음, n에 비례 성능 저하 | 중간, 정렬/리빌드 비용 | 높음, 메모리와 해시 품질 의존 |
| 일관성 | 데이터 순서 의존 없음, 결정적 | 정렬 유지 전제 | 해시 충돌 시 지연 변동 |
| 안정성 | 간단 로직, 오류 여지 적음 | 경계/중앙 계산 오류 가능 | 해시/리사이즈 복잡성 |
| 운영 편의 | 구현·디버깅 용이 | 정렬/업데이트 관리 필요 | 메모리 사용·튜닝 필요 |
전환 신호를 관측하며 쓰기
프로토타입이나 테스트 단계에서는 순차 탐색으로 기능을 빠르게 검증할 수 있다. 이후 부하를 관측하면서 이분 탐색이나 해시 조회로 단계적으로 바꾸면 된다.
구현 시간 단축과 결함 표면 축소는 초기 릴리스를 앞당기는 데 도움이 된다. n이 작거나 조회 빈도가 낮은 워크로드에서는 정렬과 인덱스 구축 비용도 피할 수 있다. 데이터 분포를 가정하면 평균 비교 횟수는 존재 시 ≈ n/2, 부재 시 n이므로 관측 기반 임계치를 설정하기 쉽다.
센티넬, 블록 스캔, SIMD를 적용하면 플랫폼과 데이터 패턴에 따라 상수 계수를 1.2~3배 수준으로 개선할 수 있다.