[집합과 검색] #3. 검색과 복잡도

이진 검색

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

(단, 데이터가 키 값으로 이미 정렬돼있다는 조건을 가진다.)

 

이진 검색을 한 단계 진행할 때마다 검색 범위가 (거의) 반으로 좁혀짐에 따라 불필요한 비교를 줄일 수 있다.

 

이진 검색의 초기화

LOW	검색 범위의 맨 앞 인덱스
MID	검색 범위의 중앙 인덱스
HIGH	검색 범위의 맨 끝 인덱스

 이진 검색 응용

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int bin_search(int arr[],int n,int key){
    int LOW,MID,HIGH;

    LOW = 0;
    HIGH = n -1;
    do{
        MID = (LOW + HIGH)/2;
        if(arr[MID] == key) return MID;
        else if(arr[MID] < key) LOW = MID + 1;
        else HIGH = (MID -1);
        /**
        중앙값보다 검색하고자 하는 값이 큰 경우
        -> (중앙값+1)를 LOW로
        
        중앙값보다 검색하고자 하는 값이 작은 경우
        -> (중앙값-1)를 HIGH
         */
    }while(LOW <= HIGH);
    return -1;
    /**
    LOW  : 검색 범위 맨 앞의 인덱스 == pl
    MID  : 검색 범위 가운데 인덱스  == pr
    HIGH : 검색 범위 맨 뒤의 인덱스 == pc
    */

}

int main(){
    int num,key,cnt=0;
    printf("이진검색\n");
    printf("요소 개수: ");scanf("%d",&num);

    int *arr = (int*)malloc(sizeof(int)*num);
    printf("오름차순으로 입력하세요.\n");

    while(num > cnt){
        if(cnt == 0){
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            cnt ++;
        }
        else{
            printf("x[%d]: ",cnt);
            scanf("%d",&arr[cnt]);    
            if(arr[cnt-1] < arr[cnt]) cnt ++;
            else printf("오름차순으로 다시 입력하세요.\n");
        }
    }
    printf("검색값: ");scanf("%d",&key);

    int idx  = bin_search(arr,num,key);
    if(idx == -1) puts("검색에 실패했습니다.");
    else printf("%d는 x[%d]에 있습니다.",key,idx);

    free(arr);

}

 

복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라지는데, 이러한 알고리즘의 성능을 객관적으로 평가하는 기준

시간 복잡도	실행에 필요한 시간을 평가한 것
공간 복잡도	기억 영역과 파일 공간이 얼마나 필요한 가를 평가한 것

복잡도 메트릭을 통해 시스템의 복잡도를 측정한 결과 복잡도가 높은 경우, 일반적으로 많은 장애가 유발될 가능성이 크므로 보다 정밀한 시험을 통해 내재된 오류를 사전에 제거하여야 한다. 

 복잡도의 형태

O(1)과 같은 상수(constant) 형태
O(log n)과 같은 로그 형태
O(n)과 같은 선형
O(n log n)과 같은 선형로그 형태
O(n^c), O(n^3)과 같은 다차 형태
O(c^n), O(3^n)과 같은 지수 형태
O(n!)과 같은 팩토리얼 형태

연산의 횟수가 다항식으로 표현될 경우, 계산의 편의성을 위해 불필요한 정보는 모두 버린 후 시간 복잡도를 계산한다. 

 

n/2번 실행했을 때의 복잡도는 O(n/2)가 아닌 O(n)으로서, n의 값이 무한히 커진다고 해도 복잡도는 O(n)으로 표시한다. 이는 컴퓨터의 계산 속도가 인간이 느낄 수 있는 범위를 넘어가기 때문이다. 다시 말해 괄호 안의 수는 정확한 값이 아닌 비례의 관계로 이해는 것이 좋다.

 

단계	실행 횟수	복잡도
1	1	O(1)
2	n/2	O(n)
3	n/2	O(n)
4	1	O(1)
5	n/2	O(n)
6	1	O(1)

n이 점점 커짐에 따라 O(n)에 필요한 계산 시간은 n에 비례하여 커지지만 O(1)에 필요한 계산시간은 변하지 않는다.

 

일반적으로 O(f(n))과 O(g(n))의 복잡도의 계산은 다음과 같다.

O(f(n)) + O(g(n)) = O(max(O(f(n)),O(g(n)))

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 더 우선 시 한다.

다시말해, 복잡도는 차원이 가장 높은 복잡도를 선택한다.