[자료구조] 13장 Search

1. 탐색

: 여러 개의 자료 중에서 원하는 자료를 찾는 작업

 

2. Map dictionary

: 키-값 쌍을 테이블에 저장

 

3. 순차 탐색

: 정렬 안된 배열을 처음부터 마지막까지 하나씩 검사

  - 시간 복잡도: O(n)

  - 평균 비교 횟수: (n+1)/2

 

4. 이진 탐색

: 정렬된 배열 탐색에 적합. 탐색의 범위를 반으로 줄여가면서 탐색 진행.

  - 시간 복잡도: O(logn)

  

5. 색인 순차 탐색

: 인덱스 테이블을 사용. 모두 정렬되어 있어야함.

  - 시간 복잡도: O(m+n/m), m은 인덱스 테이블 크기, n은 주자료 크기

 

6. 보간 탐색

: 사전이나 전화번호부를 탐색하는 방법, 탐색키가 존재할 위치를 예측하여 탐색하는 방법

  이진 탐색과 유사하지만, 보간 탐색은 불균등 분할해 탐색

  - 시간 복잡도: O(logn)