빅오 표기법 (Big-O Notation), 시간 복잡도, 공간 복잡도

big-O는 알고리즘의 효율성을 나타내는 지표입니다. big-O를 이용하여 내가 개선한 알고리즘이 빨라졌는지, 메모리를 많이 잡아 먹지는 않는지 등의 알고리즘의 성능을 판단합니다. 시간에 대한 개념인 시간 복잡도와 공간에 대한 공간 복잡도가 있습니다.

시간 복잡도

시간 복잡도란 big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타냅니다. 수행되는 연산의 수를 가지고 계산하며 알고리즘에서 중요하지 않는 값들은 최대한 무시합니다.

여기서 알고리즘을 계산하는데 사용하는 연산이란 대개 산술, 비교, 대입 등을 말합니다. 하지만 어떤 연산이 해당 되는지를 암기할 필요는 없습니다. 반복문을 기준으로 입력 값(N)에 영향을 받는 핵심적인 코드가 어느 부분인지를 파악하고 N과 어떤 관계가 있는지를 파악하는 관점을 기르는 것이 중요합니다. 연산이 많이 존재하더라도 하나로 취급하여 big-O값을 구할 수도 있습니다.

입력 값(N)에 따라서 실제 소요되는 시간이 big-O에 의한 결과와 다를 수도 있습니다. 예를 들어 특정 입력 값에 대해 O(N)이 O(1)보다 빠를 수도 있습니다. 하지만 이는 big-O에서 무시합니다. 그 이유는 big-O는 단순히 증가하는 비율을 나타내는 개념으로, 데이터의 입력이 충분히 큰 것을 가정합니다. 알고리즘의 효율성은 데이터의 입력 값이 얼마나 큰지에 따라 영향을 받기 때문에 이런 사소한 부분을 무시할 수 있는 것입니다. 아래에 나오는 경우들도 이와 같은 이유입니다.

상수항 무시

O(2N) -> O(N)
O(N² + 2) -> O(N²)

영향력 없는 항 무시

O(N² + N) -> O(N²)
O(N²)이 가장 지배적이기 때문에 그 외에 영향력이 없는 항들은 무시합니다.

big-O에는 다양한 실행 시간이 존재하지만 자주 사용 되는 것들은 아래와 같습니다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

항상 N 변수 하나만 사용되는 것은 아닙니다. O(AB), O(wh) 등 다양하게 표현 될 수 있고 문제 상황에 따라 하나만 사용될 수도 있고 여러 개의 변수가 사용될 수도 있으니 주의해야합니다.

시간 복잡도 예제

입력 값 N에 대해 N²을 구하는 프로그램을 작성 한다고 해봅시다. 예를 들어 10을 입력하면 100이라는 값이 출력돼야 합니다. 이 예제를 가지고 몇 가지 다른 방식의 알고리즘을 구현하고 각각의 시간 복잡도를 구하여 비교 해봅니다.

int sum1(int N){
    return N*N;
}

첫 번째 방법은 곱셈 연산 1개로 big-O 표기법으로 O(1) 이 됩니다.

int sum2(int N){
    sum = 0;

    for (int i=1; i<=N; i++) {
        sum = sum + N;
    }    

    return sum;
}

이 경우는 덧셈 연산 1개와 대입 연산 1개가 N만큼 실행되므로 2N의 시간이 걸리지만 big-O 표기법으로는 상수항을 무시하여 O(N) 이 됩니다.

int sum3(int N){
    sum = 0;

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            sum = sum + 1;
        }
    }

    return sum;
}

마지막 경우는 덧셈 연산, 대입 연산 이 각각 NxN번 실행되므로 총 2N²의 시간이 걸리지만 마찬가지로 상수항을 무시하여 big-O 표기법으로 O(N²) 이 됩니다.

참고로 sum = 0; 또한 대입 연산인데 무시한 이유는 상수 값 1이기 때문입니다.

공간 복잡도

공간에 대한 개념으로 알고리즘이 공간을 얼마나 필요로 하는지를 나타냅니다. 시간 복잡도 보다는 덜 중요시 취급되지만 신경 써봐야 할 필요가 있습니다.
예를 들어, 크기가 N인 배열을 만든다고 가정하면 공간 복잡도가 O(N)이 되고 NxN인 배열을 만들면 O(N²)이 됩니다.

함수의 재귀적인 호출의 경우 스택 공간도 고려해야 합니다.

공간 복잡도 예제

1부터 N까지의 합을 구하는 예제를 재귀적으로 구현한 알고리즘을 살펴봅시다.

int sum(int N){
    sum = 0;
    if(N<1)
        return 0;
    return N + sum(N-1);
}

N=5일 경우 스택에 쌓이는 최대 메모리는 sum(1) + sum(2) + … + sum(5) 이 됩니다. 따라서 공간 복잡도로 나타내면 O(N) 으로 표현됩니다.

하지만 단지 N번 호출했다고 해서 공간 복잡도가 항상 O(N)이 되는 것은 아닙니다.
아래의 경우를 살펴봅시다.

int mainSum(int N){
    int result = 0;

    for(int i=0; i<N; i++)
        result += sum(i, i+1);

    return result;
}

int sum(int a, int b){
    return a + b;
}

mainSum()함수에서 sum()를 N번 호출하지만 스택에 쌓이는 최대 공간은 mainSum() + sum(), 2입니다. 따라서 이 경우는 O(1) 공간만 사용합니다.

참고자료

• 코딩 인터뷰 완전 분석 - 게일 라크만 맥도웰 지음, 이창현 옮김