Algorithm
[개념] 탐색(검색) 알고리즘
욜스터
2021. 1. 25. 22:39
728x90
선형 탐색/순차 탐색(Linear Search/Sequential Search)
순서대로 하나하나씩 찾기
왼쪽에서부터 순서대로 하나씩 확인해 나가는 것...
찾는 대상이 앞쪽에 있으면 짧은 시간에 탐색할 수 있지만,
뒤쪽에 있거나 결과가 없거나 탐색 대상이 많으면 많은 시간이 걸리고 비효율적일 수 있다
시작 복잡도: O(n)
이진 탐색/이분 검색(Binary Search)
반씩 제외시키면서 찾기
미리 오름차순이나 내림차순으로 정렬되어 있는 경우 사용할 수 있다.
가운데 있는 요소보다 큰지 작은지 보고 범위를 좁힌다.
예) 술자리에서 했던 소주 뚜껑 숫자 업다운으로 맞추기
평균적으로 이진 탐색법이 선형 탐색보다 빠르다.
시작 복잡도: O(logN)
해시법 (Hash)
728x90
반응형