[개념] 탐색(검색) 알고리즘

선형 탐색/순차 탐색(Linear Search/Sequential Search)

순서대로 하나하나씩 찾기

왼쪽에서부터 순서대로 하나씩 확인해 나가는 것...

 

찾는 대상이 앞쪽에 있으면 짧은 시간에 탐색할 수 있지만,

뒤쪽에 있거나 결과가 없거나 탐색 대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다

 

시작 복잡도: O(n)

 

이진 탐색/이분 검색(Binary Search)

반씩 제외시키면서 찾기

미리 오름차순이나 내림차순으로 정렬되어 있는 경우 사용할 수 있다.

 

가운데 있는 요소보다 큰지 작은지 보고 범위를 좁힌다.

예) 술자리에서 했던 소주 뚜껑 숫자 업다운으로 맞추기 

 

평균적으로 이진 탐색법이 선형 탐색보다 빠르다. 

시작 복잡도: O(logN)

 

해시법 (Hash)