👏 복잡도란

프로그램의 실행속도는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(Complexity)라고 한다.

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

지금까지 학습한 선형 검색과 이진 검색의 복잡도를 살펴보자!

선형 검색의 복잡도

static int search1(int[] arr, int n, int key){
    int i = 0;		//(1)
    while (i<n){	//(2)
        if(arr[i] == key)//(3) 
            return i;	//(4)
        i++;	//(5)
    }
    return -1;	//(6)
}

각 단계별로 몇 회 실행되는지 정리해보자.

1. 변수 i에 0을 대입하는 것은 처음 한번 실행한 후 이후에는 없다. 이럴 경우 복잡도는 O(1)로 표기한다.
2. 배열에 맨 끝에 도달했는지 판단하고 있다. 평균 실행 횟수는 n/2이고 n에 비례하는 횟수만큼 실행하는 경우 복잡도를 O(n)으로 표기한다.
3. 검사하고 있는 값과 키값이 같은지 판단하고 있다. (2)와 동일한 복잡도를 가진다.
4. 키 값을 찾았을 때 1번 실행되므로 O(1) 복잡도를 가진다.
5. 검사를 진행하면서 n번만큼 실행되므로 O(n) 복잡도를 가진다.
6. 검사가 모두 종료된 후 마지막에 1번 실행되므로 O(1) 복잡도를 가진다.

n/2번 실행했을 때 복잡도를 O(n/2)가 아닌 O(n)으로 표기하는 이유는 n값이 무한히 커진다고 가정했을 때, 그 값의 차이가 무의미해지기 때문이다. 마찬가지로 100번만 실행하는 경우도 O(100)이 아닌 O(1)로 표기한다. 컴퓨터가 100번 계산하는 시간과 1번만 계산하는 시간 차이는 사람이 느낄 수 없을 정도로 작기 때문이다.

이진 검색의 복잡도

static int binSearch(int[] a, int n, int key){
    int pl = 0;     //(1)
    int pr = n-1;   //(2)

    do{
        int pc = (pl+pr)/2;	//(3)
        if(a[pc]==key)		//(4)
            return pc;		//(5)
        else if(a[pc]<key)	//(6)
            pl=pc+1;		//(7)
        else			
            pr = pc-1;		//(8)
    }while(pl<=pr);		//(9)

    return -1;  //(10)
}

1. 변수 pl에 0을 1회 대입하므로 O(1) 복잡도를 가진다.
2. 변수 pr에 n-1을 1회 대입하므로 O(1) 복잡도를 가진다.
3. pc의 값을 대입하는 횟수가 n번 반복하지 않고 조건에 따라 절반씩 줄어들고 있으므로 O(log n) 복잡도를 가진다.
4. pc의 요소값이 key 값과 동일한지 비교하는 횟수가 n번이 아닌 조건에 따라 줄어들고 있으므로 O(log n) 복잡도를 가진다.
5. key 값을 찾았을 때 1회 실행되므로 O(1) 복잡도를 가진다.
6. key 값 보다 요소수가 작을 때 실행되는 횟수가 n번이 아닌 조건에 따라 줄어들고 있으므로 O(log n) 복잡도를 가진다.
7. key 값 보다 요소수가 작을 때 실행되는 횟수가 n번이 아닌 조건에 따라 줄어들고 있으므로 O(log n) 복잡도를 가진다.
8. key 값 보다 요소수가 클 때 실행되는 횟수가 n번이 아닌 조건에 따라 줄어들고 있으므로 O(log n) 복잡도를 가진다.
9. pl이 pr보다 작거나 같은지 비교하는 횟수가 n번이 아닌 조건에 따라 줄어들고 있으므로 O(log n) 복잡도를 가진다.
10. 검색에 실패했을 경우 1회 실행되므로 O(1) 복잡도를 가진다.

복잡도의 크기 순서

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

시간 복잡도에 대한 추가 참고글