시간복잡도 Big-O 정리

시간 복잡도? Big-O?

시간 복잡도는 알고리즘의 실행 속도를 "변수 N을 기준으로 대충 얼마 걸린다."라는 걸 표현하는 가장 쉽고 빠른 방법이다.

Big-O는 특히 "최악의 상황에서 대충 얼마 정도 걸려요~"라는 걸 수식으로 요약해놓은 것이다.

 

경험상 프로그램에서 평균적이나 최선의 케이스 같은 건 크게 의미가 없고, 최악의 경우에 얼마가 걸리는지 파악하는 게 제일 중요하고 심지어 계산하기도 제일 편하다.

그래서 대부분 시간 복잡도를 물어보면 Big-O를 기준으로 이야기하곤 한다.

(이하 내용에서도 시간 복잡도 = Big-O로 이야기하고 있으니 참고 바람.)

 

시간 복잡도 기초

O(N) : N의 시간이 걸림. - 오더(Order) N이라고 읽음
O(N²) : N제곱의 시간이 걸림. - 오더 엔 제곱
O(NLogN) : NLog₂N의 시간이 걸림. - 오더 엔 로그 엔

일단 기본적인 표기법과 읽는 방법은 위 표와 같다.

 

int Function(int n){
    int iSum = 0;
    for(int i=1; i<=n; ++i){
        iSum += i;
    }

    return iSum;
}

위 함수의 시간 복잡도는 O(N)이다.

반복이 N번 돌기 때문이다.

 

추가적으로 Big-O의 핵심은 변수(N, M, X..)가 중요하고, 자잘한 숫자나 낮은 계수는 다 생략한다는 것이다.

 

- N+100의 시간이 걸린다? O(N)이다.

- 100N의 시간이 걸린다? O(N)이다.

- 633N² + 32N + 12332의 시간이 걸린다? O(N²)이다.

- 73N² + 16N + 236M의 시간이 걸린다? O(N² + M)이다.

 

Big-O에서 100N이나 N+100은 N과 별로 차이가 없다고 생각한다.

N이 1억이라고 했을 때, N²(1경)에 비해서 2N(2억)이나 N+100(1억 100)은 거의 눈에 띄지 않는 차이이기 때문이다.

 

void Function(int n){
    for(int k=1; k<=10; ++k){
        for(int i=1; i<=n; ++i){
            // loop
        }
    }

    for(int i=1; i<=n; ++i){
        // loop
    }

    for(int i=1; i<=500; ++i){
        // loop
    }
}

즉 위 함수의 시간 복잡도도 O(N)이다.

"10N + N + 500"는 "O(N)"과 같다.

 

좀 더 복잡한 복잡도 계산

void Function(int n){
    for(int i=1; i<=10; ++i){
        // Do something.
    }
}

N이 존재하지 않는 상수 시간이다.

O(1)으로 표기한다.

 

void Function(int n){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            // loop
        }
    }
}

위 함수는 더할 나위 없는 O(N²)이다.

 

void Function(int n){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            // loop
        }

        for(int j=1; j<=n; ++j){
            for(int k=1; k<=100; ++k){
                
            }
        }

        for(int j=1; j<=100; ++j){
            // loop
        }
    }
}

위 함수 역시

N ( N + 100N + 100 )

-> N² + 100N² + 100N

-> 102N² + 100N (더 낮은 상수곱 차수는 고려 가치가 없다.)

-> O(N²)이다.

 

void Function(int n, int m){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            // loop
        }

        for(int j=1; j<=m; ++j){
            for(int k=1; k<=100; ++k){

            }
        }

        for(int j=1; j<=m; ++j){
            // loop
        }
    }
}

N( N + 100M + M )

-> N² + 100NM + NM

-> N² + 101NM (101은 의미 없는 숫자이다)

-> N² + NM (NM은 N² 보다 커질 가능성이 있으므로, 고려 가치가 있다.)

-> O(N² + NM)

 

다른 이야기지만, 위 시간 복잡도를 보면 N을 최소화하고 M에 부담을 몰빵 하면 O(M)에 가까워지니까 입력값의 N을 최대한 줄여서 받으면 되겠다는 판단을 할 수 있을 것 같다.

 

void Function(int n){
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=i; ++j){
            // loop
        }
    }
}

1+2+3+4+...+N

-> N(N+1) / 2 (등차수열 합의 공식을 사용해서 N의 방정식으로 정리)

-> 0.5N² + 0.5N (낮은 차수와 계수 0.5는 다 지워버리자)

-> N²

-> O(N²)

 

void Function(int n){
    for(int i=1; i<n; ++i){
        Function(i);
    }

    // Do something.
}

N-1 * N-2 * N-3 * ... 1

-> (N-1)! // 사실 그냥 여기서 -1 빼고 N!으로 퉁치면 됨.

-> N! * 1/N

-> N!

-> O(N!)

 

int BinarySearch( const vector<int>& vec, int target ){
    int iLength = vec.size();
    
    int iLower = 0;
    int iUpper = iLength - 1;
    int iIndex = 0;

    while( iLower <= iUpper ){
        iIndex = iLower + ( iUpper - iLower ) / 2;

        if(vec[iIndex] == target){
            return iIndex;
        }
        else if(vec[iIndex] < target){
            iLower = iIndex + 1;
        }
        else {
             iUpper = iIndex - 1;
        }
    }

    return -1;
}

이진 탐색의 N이 1000이라고 칠 경우,

고려 값이 1000 -> 500 -> 250 - > 125 -> 62 -> 32 -> 16 -> 8 -> 4 -> 2 

이런 식으로 줄어들게 된다.

 

즉 Log₂1000

-> O(Log₂N)이다.

 

시간 복잡도에서 말하는 LogN은 밑이 2(Log₂)를 의미하므로 줄여서 O(LogN)이라고 해도 무방하다.

 

위에서 예시한 케이스들 말고도 여러 케이스가 존재하지만 신입 수준에서 배우는 알고리즘에는 이 정도면 충분히 표현 가능하다.

 

직접 계산해보거나 찾아보기

1. 벡터에서 특정 N번째 Element를 가져오는 함수의 시간 복잡도는?

2. 리스트에서 특정 N번째 Element를 가져오는 함수의 시간 복잡도는?

3. 해시 맵에서 특정 Key의 Element를 가져오는 함수의 시간 복잡도는?

4. 큐에서 새로운 Element를 푸시할 때 필요한 시간 복잡도는?

5. 우선순위 큐에서 새로운 Element를 푸시할 때 필요한 시간 복잡도는?

6. 버블 정렬 알고리즘의 시간 복잡도는?

7. 선택 정렬 알고리즘의 시간 복잡도는?

8. 퀵 정렬 알고리즘의 시간 복잡도는?
9. 머지 정렬 알고리즘의 시간 복잡도는?

10. BFS 알고리즘의 시간 복잡도는?

11. A* 알고리즘의 시간 복잡도는?

 

위 내용들은 실제로 신입 평가 문제로 출시되는 시간 복잡도이다. (10, 11은 좀 오버..)

실제 실무에서는 컨테이너 관련 시간 복잡도만 잘 파악하고 있어도 충분하다.

 

 

 

정답

1. 벡터는 위치로 랜덤 액세스가 가능하므로 O(1).

2. 리스트는 위치를 액세스 하려면 순회를 해야 하므로 O(N).

3. 일반적으로 O(1). 해시 충돌이 심하면 O(N)까지 가능하지만, 보통 해시 알고리즘의 시간 복잡도를 이야기할 때는 해시의 충돌 부분은 고려하지 않는다.

4. 맨 뒤에 넣기만 하면 되므로 O(1).

5. 이진트리 마지막에 넣고 계속 한 레벨씩 올라와야 하므로 O(LogN)

6. O(N²)

7. O(N²)

8. O(N²).

9. O(NLogN)

10. 인접 리스트의 경우 O(|V|+|E|), 행렬일 경우 O(|V|²). 여기서 |는 절댓값이 아니고 Vector, Edge의 집합을 의미한다.

11. O(|E|Log|V|). 이까지 이해했으면 A* 알고리즘의 시간 복잡도는 별 의미가 없다는 것을 알 수 있을 것임.

 

여담

사실 백트래킹과 같이 오랜 시간이 걸릴 수밖에 없는 알고리즘 문제를 풀 때는 가지치기를 해서 시간을 줄이는 것이 중요하다. 그러면 시간 복잡도는 바뀌지 않지만 훨~~~ 씬 빨라진다.

Ex. O(N!) 알고리즘 제귀 함수가 N-4쯤에 끊기게 가지를 쳐서 O(N³) 급으로 돌게끔..

 

영어로 시간 복잡도를 검색해볼 때는 [어쩌고 알고리즘 big o notation]이라고 치면 나온다.

또는 [어쩌고 알고리즘 time complexity]라고 쳐도 됨.

 

 

---

 

 

사전 지식이 거의 없는 친구한테, 시간 복잡도를 최대한 빠르게 알려주기 위해서 작성해본 포스트입니다.

틀린 내용이 있으면 댓글로 공유 부탁드립니다. (꾸벅)