탐색의 분류
1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색
- 선형탐색 (linear search) 또는 순차탐색 (sequential search)
- 이분탐색 (binary search) : 분할정복을 이용한 탐색
- 해싱 (hashing)
2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색
- tree traversal
- DFS
- BFS
선형탐색, linear Search
- 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법
- 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다
- 단점 : 검색시간이 오래걸린다
- 시간복잡도
- worst : O(n)
- average : O(n)
- best : O(1) // 첫번째 인덱스의 값이 찾고자 하는 값인 경우
이분탐색, Binary Search
- 정의 : 데이터 집합의 범위를 반씩 나누어 가면서 분할정복하여 탐색하는 방법
- 장점 : 탐색 속도가 빠르다
- 단점 : 데이터집합 안의 값들이 정렬되어 있어야 한다.
- 시간복잡도
- worst : O(logn)
- average : O(logn)
- best : O(1) // 중간 인덱스의 값이 찾고자 하는 값인 경우
'Computer Science > algorithm' 카테고리의 다른 글
Tree, Traversal, Binary Search Tree (0) | 2020.07.19 |
---|---|
Hashing (0) | 2020.07.19 |
정렬3 : heap sort (0) | 2020.07.19 |
정렬2 : 분할정복을 이용한 정렬 (0) | 2020.07.19 |
정렬1 : selection, insertion, bubble sort (0) | 2020.07.19 |