[Algorithm] 복잡도 - 탐색 알고리즘(선형, 이진, 해싱)

탐색 알고리즘

: n개의 데이터가 등록되어있는 테이블에서 어떤 특정 키를 가지는 데이터를 찾아내는 처리

1. 선형 탐색

: 가장 단순한 탐색 알고리즘/ 배열의 처음부터 마지막까지 읽어 들이면서 순서대로 키와 요소 비교

eclipse-workspace - algorithm_uni/src/algorithm_uni/LinearSearch.java

-> while 루프의 한번 실행 시 복잡도는2,3,5 행의 복잡도를 합한 것

: O(1) + O(1) + O(1) = O(max(1,1,1)) = O(1)

 

-> while 루프는 평균 n/2반복, 전체 복잡도는

: O(1) ∙ (n/2) = O(1) ∙ O(n) = O(n)

 

-> 따라서 search 메서드의 (선형 탐색) 전체 복잡도

: O(1) + O(n) + O(1) + O(1) = O(max(1,n,1,1)) = O(n)

 

=> 즉, 선형 탐색을 사용하면 탐색을1회 실행하는데 테이블에 등록되어있는 데이터의 개수에 비례한 시간이 걸림

2. 이진 탐색(Binary Search , 바이너리 서치)

: 미리 키를 오름차순으로 정렬해 둔 배열에서, 특정 키를 가진 데이터를 찾는 알고리즘

: 최소값을 low, 최대값을 high, 중간값을 middle 로 두고

: key 와 middle 을 비교하여 같으면 찾은 것,

key<middle 이라면 high를 앞쪽 최대 값으로 변경

key>middle 이라면, low를 뒤쪽 최소 값으로 변경

eclipse-workspace - algorithm_uni/src/algorithm_uni/LinearSearch.java

이진 탐색은 한번 루프가 반복될 때마다 찾을 범위가 반으로 줄어들기 때문에 while루프가 실행되는 횟수는 대략 번

-> 따라서 while 루프의 복잡도

: 루프 내부의 복잡도 x 실행 횟수 = O(1) ∙ O(log n) = O(log n)

 

복잡도

1,2 행: O(1)

3~9 행: O(log n)

10 행: O(1)

 

=> 따라서 이진 탐색의 전체 복잡도는

: O(1) + O(log n) + O(1) = O(max(1, log n, 1)) = O(log n)

**선형 탐색과 이진 탐색의 비교

선형: 요소1000개 일 경우, 평균 루프 실행 횟수: n/2=500 회

이진: log n=10 회

-> 이진 탐색이 압도적으로 빠름

3. 해싱

: 데이터의 규모에 관계없이 삽입,탐색, 삭제 조작을 실질적으로 O(1)에(즉, 일정 시간 내에) 할 수 있는 고속 탐색 알고리즘

: 키 값을 데이터가 저장된 위치(배열의 첨자 값)와 직접 연관 짓는 것이 해싱의 원리

: 선형/이진 탐색과는 근본적으로 다름

 

 

: 어떤 특정 범위 내에 있는 정수 (0~99) 를 키로 하는 일련의 데이터가 있다고 가정, 

크기가 100인 배열 x를 준비하여 키 값 a를 이 배열의 첨자로!

즉, 키가0인 데이터는 x[0] 에, 키가 37인 데이터는 x[37]에 저장

: 이 방식을 사용하면 삽입, 탐색, 삭제 모두 명백히 O(1)로 실행이 가능

 

: 그러나 실제로는 키를 바로 배열의 첨자로 사용하는 경우는 거의 없음

그래서 키 값 x를 배열의 첨자로 변환하는 함수 h(x)를 사용

 

: 이 함수를 해시 함수(hash function)이라고 하며, 해시 함수가 반환하는 값을 해시 값(hash value) 이라고 함

: hash 란 ‘잘게 썰다’ 라는 의미로, 키 값을 ‘잘라 내어’ 억지로 배열의 첨자로 사용하는 것

 

: 그러나 해싱은 해시 값 중복의 문제가 발생할 수 있음

: 이를 해결하는 방법은 2가지, 

1. 동일 해시 값을 가지는 데이터를 연결리스트로 연결(체인화, 연쇄화)

2. 해시 값에 대응하는 버킷이 이미 차 있다면, 어떤 절차에 따라 다른 버킷에 데이터를 저장 (오픈 어드레스 법)

 

~ 8장. p183 에서 자세히 ~

** 3가지 탐색 알고리즘을 복잡도로 평가

뛰어난 순서: 해싱-> 이진-> 선형

 

그러나 복잡도는 절대적인 기준이 아님

여러 득실을 따져야 함

 

ex1. 선형 탐색에서는 데이터 등록 순서가 보존

ex2. 해싱에서는 등록할 데이터 개수 보다 큰 배열을 준비할 필요가 있으며, 해시 함수의 선택에 따라서는 해시 값의 충돌이 빈번히 발생할 수 있어 성능이 대폭 저하될 우려가 있음

** 알고리즘 선택 시 복잡도 외에 고려해야할 요인

1. n이 작을때에는 오더(빅오)의 크고 작음 보다 정수의 대소가 결정적인 요인이 됨

2. 프로그래밍 하는데 드는 노력 (복잡도의 오더가 작은 알고리즘은 프로그래밍, 디버그, 유지 보수 모두 어려움, 따라서 일회용 알고리즘일 경우 시간이 많이 걸리더라도 단순한 알고리즘을 사용하는 쪽이 득)

3. 시간과 공간의 트레이드 오프(공간을 희생하여 복잡도의 오더를 낮출 때 신중히)

책. Java 프로그래머를 위한 알고리즘과 자료구조