[20210906] 검색 알고리즘

검색 알고리즘을 정리한다.

 

1. 선형 검색: 처음부터 차례로 검색한다.

2. 제어 검색: 이분 검색, 보간 검색

3. 블록 검색: 검색 대상의 자료를 그룹별로 블록화한다.

4. 이진 트리 검색: 이진 트리 구조를 이용하여 검색한다.

5. 해싱 검색: 검색 대상의 자료를 키 변환 작업을 통해 검색한다.

 

시간 복잡도

선형 검색 - O(n)

이분 검색 - O(log₂n)

이진 트리 검색 - O(log₂n)

해싱 검색 - O(1)