[개념정리] 검색

※ 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택

1-1. 검색 알고리즘

배열 검색에 사용되는 알고리즘

- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행

- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행

            방법 1) 체인법 : 같은 해시 갑스이 데이터를 선형리스트로 연결하는 방법

            방법 2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

1-2. 선형 검색

선형 검색(순차 검색)이란?

배열에서의 검색 : 원하는 키 값을 갖는 요소와 만날 때까지 맨 앞부터 순서대로 요소를 검색

▷ 일반적으로 배열의 요소 개수가 n개일 때, 조건을 판단하는 횟수는 평균 n/2 회이다.

 

∵ 종료 조건을 검사하는 비용이 크다.

▷ 보초법 : 이 비용을 반으로 줄이는 방법

- 보초 : 검색하기 전에 검색하고자 하는 키 값 (반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할)

 

1-3. 이진 검색 

이진 검색이란?

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘으로 배열의 요소 중앙값과 원하는 키 값을 비교 후 남은 두 부분 중 한 부분을 다시 비교(그림 참고)

▷ 이진 검색을 검색을 반복할 때마다 검색 범위가 절반이 되므로 비교 횟수 평균 값은 log n 이다.

출처 : https://woodforest.tistory.com/32

복잡도란?

알고리즘의 성능을 객관적으로 평가하는 기준

1. 시간 복잡도 : 실행에 필요한 시간을 평가한 것

2. 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

선형 검색의 시간 복잡도 : O(n) (n에 비례하는 횟수만큼 실행하는 경우)

n/2로 표현하지 않는 이유는 n의 값이 무한히 커진다고 가정했을 때 그 값의 차이가 무의미해지기 때문.

 

이진 검색의 시간 복잡도 : O(log n)