📚 검색 알고리즘
검색의 종류에는 크게 1) 배열 검색, 2) 연결 리스트 검색, 3) 이진 검색 트리 검색으로 나눌 수 있다.
오늘은 배열 검색 알고리즘에 대해 공부해보자!
복잡도
알고리즘 성능을 객관적으로 평가하는 기준
- 시간 복잡도 (Time Complexity) : 실행하는데 필요한 시간 평가
- 공간 복잡도 (Space Complexity) : 메모리와 파일 공간이 얼마나 필요한지 평가
검색 알고리즘 종류
- 선형 검색
- 이진 검색
- 해시법 (+ 체인법, 오픈 주소법)
1) 선형 검색
선형 배열에서 검색하는 경우, 원하는 키 값의 원소를 찾을 때까지 맨앞부터 순서대로 스캔하여 검색하는 알고리즘
💻 종료 조건
① 원하는 키값을 가진 원소를 찾은 경우
② 원소를 찾지 못하고 배열의 끝에 도달한 경우
2) 이진 검색
원소가 정렬되어 있는 배열에서 선형 검색보다 빠른 검색이 가능한 알고리즘으로, 검색을 수행할 때마다 검색 범위가 절반으로 줄어든다.
검색 범위
검색 범위의 맨앞, 맨끝, 중앙 인덱스를 각각 lt, mid, rt라고 한다.
배열 a에서 key를 검색하기 위해 이진 검색을 수행한다.
- a[mid] < key : 검색 범위의 왼쪽 끝 lt를 mid + 1로 변경하여 검색 범위를 오른쪽 절반으로 줄인다.
- a[mid] > key : 검색 범위의 오른쪽 끝 rt를 mid - 1로 변경하여 검색 범위를 왼쪽 절반으로 줄인다.
💻 종료 조건
① 원하는 키값을 가진 원소를 찾은 경우 (a[mid] = key)
② 더이상 검색할 범위가 없는 경우
선형 검색과 이진 검색의 시간 복잡도
- 선형 검색 시간 복잡도는 O(n)이다.
- 이진 검색 시간 복잡도는 O(log ₂ n)이다.
💻 이진 검색 시간 복잡도
전체 데이터 개수가 n이면
- 첫 번째 검색 후, 탐색할 데이터 개수는 (½ * n)이 된다.
- 두 번째 검색 후, 탐색할 데이터 개수는 (½ * ½ * n)이 된다.
...- k 번째 검색 후, 탐색할 데이터 개수는 (½)^k * n이 된다.
최악의 경우 남은 데이터가 1개가 될 때까지 검색을 수행한다.
이때 (½)^k * n = 1이 되므로, k = log ₂ n 이다.
k가 검색 횟수라고 하면 최악의 경우 시간 복잡도는 O(log ₂ n) 이다.
3) 해시법
데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 알고리즘으로, 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있다.
해시값
원소의 key(데이터)를 배열의 원소 개수로 나눈 나머지해시 테이블
해시값을 인덱스로 하여 원소를 새로 저장한 배열해시 함수
key를 해시값으로 변환하는 연산 과정
해시 충돌
해시 테이블에 데이터를 추가할 때 저장할 버킷이 중복되는 현상
해시 충돌 대처 방법
1) 체인법 : 해시 값이 같은 원소를 연결 리스트로 관리
2) 오픈 주소법 : 빈 버킷을 찾을 때까지 해시 반복 (=선형 탐색법)
해시의 trade-off
해시 충돌이 전혀 발생하지 않는다는 가정 하에 해시 테이블에서 원소를 검색, 추가, 삭제하는 연산의 시간 복잡도는 O(1)이다.
해시 충돌이 발생하지 않게 하기 위해서는 해시 테이블을 충분히 크게 만들면 되지만 메모리가 낭비되기 때문에 시간과 공간의 트레이드 오프 문제가 발생한다.
충돌을 피하려면 해시 함수가 해시 테이블보다 작거나 같은 정수를 고르게 생성해야 한다. 따라서 해시 테이블의 크기 소수로 하는 방법을 선호한다.
