가능한 작게 쪼개서 하나씩 해결하는 방식의 대표적인 형태가 이진 탐색(Binary Search)이다. 특히, 주어진 입력값이 정렬되어 있다면, 이진 탐색은 검색 공간을 반으로 줄여가면서 원하는 값의 범위를 좁혀간다. 이런 알고리즘을 구현하기 위해 재귀(recursive)를 사용할 수도 있고, 반복(Iterate)를 사용할 수도 있다.
이진 탐색 알고리즘의 값의 정확성을 제외하고, 수행 성능을 분석해보자. 수행 성능은 최악의 경우와 평균 수행 시간을 측정하는 것이 일반적이다. 먼저, 최악의 경우를 생각해본다면, 이진 탐색의 경우 최악의 경우라고 하더라도 n의 입력이 들어왔을 때 log(n) 이상의 시간을 소모하지 않는다(Ο(log(n))). 그렇다면 이진 탐색의 평균 수행 시간은 어떻게 측정 할 수 있는가?
이진 탐색의 평균 수행 시간을 분석해보면, 먼저 탐색이 발생하는 전체 횟수는 n + 1이다. n회를 탐색하면서, 원하는 값이 존재하지 않는 경우도 있기 때문에 n + 1회의 탐색을 수행하게 된다. 여기서, S(t)라는 함수를 생각해보자. S(t)는 t가 증가하면서 원하는 값을 찾을 수 있는 위치의 수라고 정의한다. t = 1이라면, 전체 집합에서 처음의 시도로 값을 찾을 수 있는 위치는 한군데 밖에 존재하지 않는다. t = 2라면, 전체 집합은 2개의 집합으로 나뉘어지며, 각각의 집합에서 원하는 값을 찾을 기회가 늘어나게 된다. t = 3인 경우에는 전체 집합의 8개로 나뉘어지며, S(3) = 8이 된다.
따라서, 이진 탐색이 성공하는 경우를 생각해본다면, A(success)(n) = SIGMA(FROM t = 1 TO d)(t * S(t) /n)이 된다. 1/n은, 전체 배열 n에서 이 사건이 발생할 확률을 의미한다. 여기서 S(t) = S^(t- 1)의 형태이므로, A(n)을 다시 쓰면 다음과 같은 형태가 된다.
A(n) = SIGMA(FROM t = 1 TO d)(t * 2^(t-1) / n)
이진 탐색은, 무엇보다 입력값이 연속된 자료형(Sequenced) 형태여야 하며, 배열과 같은 형태로 주어져야 가장 효율적으로 탐색할 수 있다. 굳이 연속된 자료형 형태가 아니라도 상관없지만, 리스트와 같은 구조를 사용한다면 그 성능은 크게 하락한다.
마지막으로, 이 알고리즘은 정렬된 상태의 입력값에서 원하는 값을 찾는 최적의 알고리즘인가? 최적의 알고리즘 여부를 검증하기 위해서는, 먼제 문제의 하한(lower bound)을 알아내야 한다. 이진 탐색 알고리즘의 최적성을 검증하기 위해서, 검증 트리(Decision Tree)를 알아봐야 한다. 먼저 찾으려는 키 값이 결정되었다면, 전체 n 배열에서 이 값을 leaf로 가지는 트리 하나를 결정 할 수 있다. 이것을 검증 트리라고 한다. 여기서 최악의 경우는, 깊이가 깊어질수록 최악의 형태가 된다. 즉, 트리가 균형 잡힌 형태가 아니고, 리스트의 구조에 가까워질수록 이진 탐색의 효율은 떨어지게 된다. 그렇다면, 정렬된 상태에서의 최적의 해결 방법이 log(n)보다 떨어질 수 있는가? 이진 분할 외에, 집합을 셋 이상으로 분할하면 원하는 값을 찾을 기회가 더 늘어나므로 더 좋은 알고리즘이 존재할 수 있지 않을까?
여기서의 log(n)은, 밑을 2로 하는 로그함수이다. 집합을 셋, 넷 이상으로 분할한다고 하더라도 그것은 c * log(n)의 형태로 표현되며, 매우 작은 차이일 뿐이다. Ω(n) 역시 Ο(n) 축약과 동일하므로, 커다란 이득은 없다. 예를 들어, 4개의 집합으로 분할하는 방법을 선택한다고 하더라도 1/2 * log(n)으로 표현되므로, 앞의 1/2은 큰 요소는 아니다. 대략적으로, log(n) 정도라면 정렬된 입력값에서 문제를 해결하는 하한이라고 할 수 있다. 따라서, 이진 탐색은 이에 근접하는 최적의 알고리즘이라 할 수 있다.
Library/Algorithm