이진 탐색(Binary Search)알고리즘과 빅-오

이진 탐색(Binary Search) 알고리즘 소개

이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어내 탐색 대상을 찾아내는 알고리즘 이다.

 

정렬된 배열에서 탐색의 시작 위치를 first, 탐색의 마지막 위치에 해당하는 인덱스 값을 last로 표기한다. 이진 탐색 알고리즘이 진행되면 first와 last는 점차 가까워진다.

이진 탐색은 first가 last보다 큰경우 종료된다. 이렇게 종료되는 경우는 탐색에 실패한 경우이다.

 

BinarySearch.c

BinarySearch 실행

if(target < ar[mid])

     last = mid -1;

else

     first = mid + 1;

이진 탐색 알고리즘에서 위처럼 구성해야 하는 이유는 한번 탐색한 대상을 포함하지 않기 위함과 탐색의 대상이 배열에 존재하지 않는 경우를 위함이다.

 

if(target < ar[mid])

    last = mid;

else

    first = mid;

위처럼 알고리즘이 구성되어 있을 때, 탐색의 대상이 배열에 존재하지 않는다면 프로그램은 끝나지 않을것이다. 탐색의 대상이 존재하지 않을때 이진 탐색을 끝내는 경우는 first가 last보다 커졌을 때 이기 때문이다.

 

이진 탐색 알고리즘의 시간 복잡도 계산(worst case 기준)

이진 탐색 알고리즘에서 데이터 수가 n개일 때, 최악의 경우 비교연산 횟수는 얼마인가?

n일때 1회

데이터 개수가 n/2일때 1회

데이터 개수가 n/4일때 1회

데이터 개수가 n/8일때 1회

....

개수가 1일때 1회이다.

 

위 과정을 정리하면 n이 1이 될때까지 2로 나눈 횟수 k회, 이진 탐색에서 비교연산 k회를 진행,

데이터가 1개 남았을 때 비교연산 1회

즉 최악의 경우에 대한 시간복잡도 함수 T(n)은 T(n) = K+1 이 된다.

 

n이 1이 되기까지 2로 나눈 횟수가 k이다.

n과 k에 관한식

-> n x (1/2)^k = 1

위 식을 정리하면

n x (1/2)^k =1 -> n x 2^(-k) = 1 -> n = 2^k

(^는 제곱이다.)

n = 2^k에서 양변에 log2를 취해준다.

log2 n = klog2 2 -> log2 n = k

위 식은 이진 탐색 알고리즘의 worst case 시간 복잡도 함수이다. 즉 T(n) = log2 n이 된다.

정확하게는 T(n) = log2 n +1이지만 +1은 중요하지 않다.

n이 증가함에 따라 연산횟수가 로그적으로 증가한다는 것이 중요하다.

 

위처럼 식(T(n))을 구성함으로써 데이터 수의 중가에 따른 연산횟수의 변화 정도를 판단할 수 있게 된다.

 

빅-오 표기법(Big-Oh Notation)

빅-오 : 시간복잡도 함수 T(n)에서 가장 영향력이 큰부분

 

T(n) = n^2 + 2n + 1

위 식에서 n이 커짐에 따라 2n + 1이 미치는 영향은 미미해지므로 T(n) = n^2으로 간략화 할 수 있다.

이를 빅-오 표기법으로 표현하면 O(n^2)이며, 읽을 때는 "빅-오 오브 n^2(Big-Oh of n^2)"이라고 읽는다.

 

단순하게 빅-오 구하기.

 

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

ex)

T(n) = n^2 + 2n + 9               ->      O(n^2)

T(n) = n^4 + n^3 + n^2 + 1    ->      O(n^4)

T(n) = 5n^3 + 3n^2 + 2n + 1   ->      O(n^3)

 

위를 일반화 하면 다음과 같다.

T(n) = a(m)n^m + a(m-1)n^(m-1) + ... a(1)n^1 + a(0)     -> O(n^m)

 

시간 복잡도 함수가 n^2인 경우에도, 9999n^2인 경우에도 O(n^2)이다. 빅-오는 '데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)'을 나타내는 표기법 이기 때문이다.

 

O(log n)의 경우 데이터 수 증가에 따라 로그 그래프와 유사한 형태를 띤다.

 

대표적인 빅-오

1.O(1)

상수형 빅-오 이다. 데이터 수와 상관없이 연산횟수가 고정인 알고리즘이다. 데이터 수와 상관없이 3회 진행되는 알고리즘일지라도 O(1)이 된다. O(1)는 연산횟수가 고정인 알고리즘이라는 의미가 담겨있다.

 

2.O(log n)

로그형 빅-오 이다. '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다. 매우 바람직한 유형이다. 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 알고리즘 성능 관점에서는 매우 미미하기 때문에 대부분의 경우 무시된다.

 

3.O(n)

선형 빅-오 이다. 데이터 수와 연산횟수가 비례하는 알고리즘 이다.

 

4.O(nlog n)

선형로그형 빅-오 이다. 이는 데이터의 수가 두배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘을 의미한다.

 

5.O(n^2)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 데이터양이 많은 경우 부적절하다. 이중으로 중첩된 박복문 내에서 연산이 진행되는 경우 발생한다.

 

6.O(n^3)

데이터 수의 세제곱에 해당하는 연산 횟수를 요구하는 알고리즘이다. 이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.

 

7.O(2^n)

지수형 빅-오 이다. '지수적 증가'라는 무서운 연산횟수의 증가를 보인다. 이러한 성능을 보이는 알고리즘이라면 개선의 과정을 거쳐서 현실적인 알고리즘으로 수정해야 한다.

 

빅-오 성능 대소관계

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n)

 

순차 탐색 알고리즘과 이진 탐색 알고리즘 비교

순차 탐색 알고리즘 : T(n) = n

이진 탐색 알고리즘 : T(n) = log2 n + 1

각각의 빅-오

순차 탐색 알고리즘 : O(n)

이진 탐색 알고리즘 : O(log2 n)

 

O(n)의 경우 실험을 하지 않아도 비교연산 횟수와 데이터 수가 같음을 알 수 있다.

 

이진 탐색 알고리즘 실험 코드

 

BSWorstOpCount.c

BSWorstOpCount.c 실행화면

위 실행결과를 통해 순차탐색 알고리즘과 이진 탐색 알고리즘 연산 횟수 비교

 

                     n                           순차 탐색 연산횟수                             이진 탐색 연산횟수

                    500                                 500                                                   9

                   5000                               5000                                                  13 

                  50000                              50000                                                 16

 

 

위 결과를 통해 O(n)과 O(log n) 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지 알 수 있다.