[탐색 알고리즘] 순차 탐색 알고리즘 vs 이진 탐색 알고리즘

[탐색 알고리즘] 순차 탐색 알고리즘 vs 이진 탐색 알고리즘

알고리즘 비교

알고리즘의 시간 복잡도만 비교하게 되면, 순차 탐색 알고리즘은 $O(n)$이고 이진 탐색 알고리즘은 $O(logn)$이므로 이진 탐색 알고리즘이 훨씬 좋아 보인다.

하지만 이진 탐색 알고리즘은 데이터가 정렬되어 있어야 한다는 전제 조건이 있다. 보통 정렬 알고리즘의 경우 $O(nlogn)$의 시간 복잡도를 가진다. 어떤 알고리즘이 좋다고 분명하게 말할 수는 없다. 상황에 맞춰서 적합한 알고리즘을 선택해야 한다.

아래 코드는 배열의 길이가 500, 5000, 50000일 때, 각 알고리즘의 최대 연산횟수를 나타낸 것이다.(Worst Case)

$O(n)$과 $O(logn)$의 차이가 어느정도인지 알 수 있을 것이다.

Code

#include <stdio.h>
 
int LSearch(int ar[], int len, int target){
    int i = 0;
    int opCnt = 0;
 
    for (; i < len; i++){
        opCnt++;
        if (ar[i] == target){
            printf("비교 연산 횟수 : %d\n", opCnt);
            return i;
        }
    }
    printf("비교 연산 횟수 : %d\n", opCnt);
    return -1;
}
 
int BSearch(int ar[], int len, int target){
    int start = 0;
    int last = len - 1;
    int mid = 0;
    int opCnt = 0;
 
    while (start <= last){
        mid = (start + last) / 2;
        opCnt++;
        if (ar[mid] == target){
            printf("비교 연산 횟수 : %d\n", opCnt);
            return mid;
        }
        else{
            if (ar[mid] > target)
                last = mid - 1;
            else
                start = mid + 1;
        }        
    }
    printf("비교 연산 횟수 : %d\n", opCnt);
    return -1;
}
 
int main(int arc, char** argv){
    // 크기가 500인 배열을 생성하고 값을 모두 0으로 초기화
    int arr1[500] = { 0, };
    // 크기가 5000인 배열을 생성하고 값을 모두 0으로 초기화
    int arr2[5000] = { 0, };
    // 크기가 50000인 배열을 생성하고 값을 모두 0으로 초기화
    int arr3[50000] = { 0, };
    int idx = 0;
 
    // 탐색 실패시 연산 횟수를 알아내는 것이 목적이므로
    // 배열에 없는 값을 탐색한다.
    idx = LSearch(arr1, sizeof(arr1) / sizeof(int), 1);
    if (idx == -1)
        printf("L(500) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
 
    idx = LSearch(arr2, sizeof(arr2) / sizeof(int), 1);
    if (idx == -1)
        printf("L(5000) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
 
    idx = LSearch(arr3, sizeof(arr3) / sizeof(int), 1);
    if (idx == -1)
        printf("L(50000) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
 
    idx = BSearch(arr1, sizeof(arr1) / sizeof(int), 1);
    if (idx == -1)
        printf("L(500) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
 
    idx = BSearch(arr2, sizeof(arr2) / sizeof(int), 1);
    if (idx == -1)
        printf("L(5000) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
 
    idx = BSearch(arr3, sizeof(arr3) / sizeof(int), 1);
    if (idx == -1)
        printf("L(50000) Search Fail\n");
    else
        printf("Target Index %d\n", idx);
}

Output

// 순차 탐색
비교 연산 횟수 : 500
L(500) Search Fail
비교 연산 횟수 : 5000
L(5000) Search Fail
비교 연산 횟수 : 50000
L(50000) Search Fail
 
// 이진 탐색
비교 연산 횟수 : 9
L(500) Search Fail
비교 연산 횟수 : 13
L(5000) Search Fail
비교 연산 횟수 : 16
L(50000) Search Fail