검색 알고리즘
검색 알고리즘은 자료 집합에서 목표 키를 가진 원소의 존재 여부·위치를 탐색한다 알고리즘의 자료 검색 알고리즘에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.
| 분류 | 알고리즘 · 자료 검색 알고리즘 |
|---|---|
| 해결 문제 | 자료 집합에서 목표 키를 가진 원소의 존재 여부·위치를 탐색한다 |
| 핵심 동작 | 순서 없는 배열은 선형 탐색, 정렬된 배열은 이진 탐색, 해시 테이블은 해시 기반 접근을 사용한다 |
| 시간 복잡도 | 자료구조·방법별 상이 |
| 추가 공간 | 인덱스별 상이 |
| 주요 전제 | 자료의 정렬 여부와 중복 키, 질의 유형·갱신 빈도를 정의해야 한다 |
| 대표 활용 | 데이터베이스 인덱스·파일 시스템·메모리 자료구조에 사용하며 전처리와 업데이트 비용을 함께 평가한다 |
| 참고 자료 | MIT 강의 노트 |
검색 알고리즘은 자료 집합에서 목표 키를 가진 원소의 존재 여부·위치를 탐색한다 알고리즘의 자료 검색 알고리즘에 속하며, 데이터의 순서를 정하거나 특정 조건을 만족하는 값을 찾는 문제를 다룬다. 올바른 구현에서는 비교·키 표현과 알고리즘이 유지해야 하는 불변식을 먼저 정의한다.[1]
동작 원리는 다음과 같다. 순서 없는 배열은 선형 탐색, 정렬된 배열은 이진 탐색, 해시 테이블은 해시 기반 접근을 사용한다. 검색 성능은 탐색 절차뿐 아니라 자료를 어떤 인덱스로 표현했는지에 좌우된다. 구현에서 각 단계의 선택이 최종 결과의 올바른 순서·위치를 유지하는지 확인해야 한다. 반복 또는 재귀의 경계와 동일한 키를 가진 원소의 처리 역시 실행 결과에 영향을 준다.
시간·메모리 성질은 선형 O(n), 정렬 배열의 이진 탐색 O(log n), 해시 평균 O(1) 등 적용하려면 자료의 정렬 여부와 중복 키, 질의 유형·갱신 빈도를 정의해야 한다 따라서 계산 복잡도는 원소 수뿐 아니라 입력의 정렬 상태, 키 범위 또는 비교·이동 비용처럼 알고리즘이 가정하는 자료 특성과 함께 분석해야 한다.
데이터베이스 인덱스·파일 시스템·메모리 자료구조에 사용하며 전처리와 업데이트 비용을 함께 평가한다. 동일한 목적의 다른 알고리즘과 비교할 때에는 안정성, 원소 이동의 양, 캐시 접근 패턴, 전처리 필요성과 최악 입력에서의 시간 비용을 함께 검토한다. 구체적인 계산 모델은 대상 자료구조 및 구현에 따라 달라진다.[2]