10.6 요약
1. 핵심 정리
- 이진 탐색은 데이터가 정렬되어 있다는 성질을 이용하여 반복할 때마다 탐색 구간을 절반씩 줄인다. 입력 데이터가 정렬되어 있어야 하며, 배열이나 배열 기반 자료 구조에만 적합하다.
- 완전 탐색은 자료 구조를 순회하여 데이터를 찾는다. 선형 탐색은 배열과 연결 리스트에, 너비 우선 탐색과 깊이 우선 탐색은 그래프와 트리에 적합하다. 범용성이 좋고 전처리가 필요하지 않지만, 시간 복잡도가 \(O(n)\)으로 비교적 높다.
- 해시 탐색, 트리 탐색, 이진 탐색은 특정 자료 구조에서 목표 원소를 빠르게 찾는 효율적인 탐색 방법이다. 시간 복잡도가 \(O(\log n)\) 또는 \(O(1)\)에 이를 만큼 효율적이지만, 보통 추가 자료 구조가 필요하다.
- 실제로는 데이터 규모, 요구되는 탐색 성능, 데이터 조회와 갱신 빈도 등을 구체적으로 분석하여 적합한 탐색 방법을 골라야 한다.
- 선형 탐색은 작거나 자주 갱신되는 데이터에, 이진 탐색은 크고 정렬된 데이터에 적합하다. 해시 탐색은 높은 조회 효율이 필요하면서 범위 조회는 필요 없는 데이터에, 트리 탐색은 순서 유지와 범위 조회가 필요한 대규모 동적 데이터에 적합하다.
- 선형 탐색을 해시 탐색으로 바꾸는 것은 실행 시간을 최적화하는 흔한 전략으로, 시간 복잡도를 \(O(n)\)에서 \(O(1)\)로 줄일 수 있다.