43. python - 검색 알고리즘

검색 알고리즘

• 선형 검색
• 이진 검색
• 보간 검색

선형검색

가장 단순한 검색 전략은 데이터를 하나씩 살펴보는 것이다. 조회한 데이터가 우리가 찾는 대상이라면 해당 데이터를 반환하고 루프를 종료한다. 검색 조건에 부합하지 않는다면 모든 데이터를 확인할 때까지 검색을 계속 이어간다. 단점은 느린속도이다. 

선형 검색의 성능 분석

선형 검색의 시간 복잡도는 최악의 경우 O(N)이다.

 

이진 검색

이진 검색의 전제 조건은 데이터가 정렬되어 있어야한다. 이 알고리즘은 반복적으로 검색 대상을 반으로 줄이면서 최저와 최고 인덱스를 갱신하는 방식을 사용한다.

이진 검색의 성능 분석

이 알고리즘은 반복적으로 검색 대상 데이터를 절반씩 줄이기 때문에 '이진' 검색이라는 이름이 붙었다. 검색 대상 데이터가 N개라면 이진 검색 알고리즘의 시간 복잡도는 최악의 경우 O(logN)이다.

 

보간검색

이진 검색은 데이터의 중간을 확인하는 방법을 사용한다. 보간 검색은 조금 더 정교한 방식으로 동작한다. 이 알고리즘은 정렬된 배열 속에서 검색할 대상의 위치를 추정한다. 

 

보간검색의 성능 분석

검색 대상 데이터의 분포가 고르지 않다면 보간 검색은 제 성능을 발휘하기 힘들다. 최악의 경우 시간 복잡도는 O(N)이다. 그러나 데이터가 고르게 분포되어 있는 최상의 경우 시간 복잡도는 O(log(log(N)))이다.