[검색 알고리즘] 이진 검색 , 선형 검색 , 해시 탐색 , 완전 탐색 ?

이진검색, 선형 검색, 해시 탐색, 완전 탐색에 대해 알아보자.

 

1/ 이진 검색

이진 검색은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다. 배열의 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 반씩 줄여나가는 방식으로 작동한다. 이 알고리즘은 검색 속도가 빠르며, 최악의 경우에도 O(log n)의 시간 복잡도를 가지는 효율적인 방법이다. 하지만, 배열이 정렬되어 있어야만 제대로 동작한다 

 

2/ 선형 검색

선형 검색은 배열이나 리스트와 같은 구조에서 처음부터 끝까지 차례로 요소를 비교하여 원하는 값을 찾는 방법이다. 배열이 정렬되어 있지 않아도 사용할 수 있지만, 최악의 경우 모든 요소를 다 확인해야 하므로 검색 속도가 느릴 수 있다. 선형 검색의 시간 복잡도는 O(n)이다. 

 

3/ 해시 탐색

해시 탐색은 해시 함수를 사용하여 데이터를 저장하고 검색하는 방법이다. 해시 함수는 입력값을 특정한 해시 코드로 변환해주며, 이 해시 코드를 인덱스로 사용하여 데이터를 저장하거나 검색한다. 해시 함수의 좋은 설계에 따라 매우 빠른 검색 속도를 가질 수 있다. 하지만, 해시 충돌과 같은 문제를 처리해야 할 수도 있다. 

 

4/ 완전 탐색

완전 탐색은 가능한 모든 경우의 수를 하나씩 시도해보면서 정답을 찾는 방법이다. 이 방법은 항상 정확한 결과를 얻을 수 있지만, 경우에 따라 매우 많은 연산이 필요할 수 있다. 보통 작은 입력 크기에 대해서 사용되며, 시간 복잡도는 경우에 따라 다양하다