[Data Structure] 순차 탐색 / 이진 탐색 알고리즘의 연산횟수 비교

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

 

이진 탐색 알고리즘 : O(logn) 의 알고리즘으로 개선시키는 것이 

 

직접 연산횟수의 비교를 통해서 도대체 왜?

 

약간의 개선이 아닌 혁신적인 성능의 개선으로 간주되는지 알아보자.

 

비교를 위한 실험의 원칙은 다음과 같다.

 

1. 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다.

2. 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지를 센다.

3. 데이터의 수는 500, 5000, 50000일 때를 기준으로 각각 실험을 진행한다.

 

#include <stdio.h>

int BSearch(int ar[], int len, int target)
{
    int first = 0;
    int last = len - 1;
    int mid;
    int opCount = 0; // 비교연산의 횟수를 기록

    while (first <= last)
    {
        mid = (first + last) / 2;

        if (target == ar[mid])
        {
            return mid;
        }
        else
        {
            if (target < ar[mid])
                last = mid - 1;
            else
                first = mid + 1;
        }
        opCount += 1; // 비교연산의 횟수 1 증가
    }
    printf("비교연산횟수: %d \n", opCount); // 탐색실패 시 연산횟수 출력
    return -1;
}

int main(void)
{
    int arr1[500] = { 0, };    // 모든 요소 0으로 초기화
    int arr2[5000] = { 0, };   // 모든 요소 0으로 초기화
    int arr3[50000] = { 0, };  // 모든 요소 0으로 초기화
    int idx;

    //배열 arr1을 대상으로, 저장되지 않은 정수 1을 찾으라고 명령
    idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 1);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    // 배열 arr2를 대상으로, 저장되지 않은 정수 2를 찾으라고 명령
    idx = BSearch(arr2, sizeof(arr2) / sizeof(int), 2);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    // 배열 arr3를 대상으로, 저장되지 않은 정수 3을 찾으라고 명령
    idx = BSearch(arr3, sizeof(arr3) / sizeof(int), 3);
    if (idx == -1)
        printf("탐색 실패 \n\n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    return 0;
}

 

실행결과

n	순차 탐색 연산횟수	이진 탐색 연산횟수
500	500	9
5,000	5,000	13
50,000	50,000	16

위의 표에 정리된 결과는 O(n)의 알고리즘과 O(logn)의 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지를 보여준다.

 

---

참고사항

// 이렇게 하지 않고
if(target < ar[mid])
	last = mid;
else 
	first = mid;

// 다음과 같이 코드를 짠 이유는?
if(target < ar[mid])
	last = mid - 1;
else 
	fisrt = mid + 1;

이렇게 값을 하나 빼거나 더해서 그 결과를 변수 last와 first에 저장하지 않으면, mid에 저장된 인덱스 값의 배열요소도 새로운 탐색의 범위에 포함이 된다. 그런데 이는 불필요한 일이다. mid의 배열요소에 탐색 대상이 저장되어 있는지 검사가 이미 끝난 상태이기 때문이다.

 

"그까짓 거 탐색 대상 하나 더 추가한다고 해서 크게 문제 될 것은 없지 않나요?"

 

맞다. 그냥 탐색 대상이 하나 늘어나는 정도라면 문제삼지 않을 수 있다. 하지만 이 경우에는 문제가 발생한다.

탐색의 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, 위와 같이 코드를 수정하고 나면 결코 first에 저장된 값은 last보다 커질 수 없다. 때문에 무한루프를 형성하게 되는 것이다.

 

"그런데 왜 first에 저장된 값이 last보다 커질 수 없는 거죠?"

 

간단히 생각해보면 기본적으로 세 변수에 저장된 인덱스 값은 항상 다음의 식을 만족하도록 알고리즘이 디자인되어있다.

 

first <= mid <= last

 

그런데 기껏 하는 연산이 mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부인데, 어떻게 first에 저장된 값이 last보다 커질 수 있겠는가?