빅오 Big-O, 시간 복잡도, 공간 복잡도

빅오 (Big-O)

 컴퓨터과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데도 매우 유용하게 활용된다.

빅오 표기법이란 입력 크기가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법으로, 특히 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행시간 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다.

빅오로 시간 복잡도를 표현할 때는 최고차 항만을 표기하며, 계수는 무시한다. 예를 들어, 입력값 n에 대해 4n^2 + 3n + 4 번 만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차 항인 4n^2 만을 고려한다. 이 중에서도 계수는 무시하며 n^2만 고려한다. 즉 여기서 시간 복잡도는 O(n^2)이 된다. 이처럼 시간 복잡도를 표기할 때는 구체적인 연산 횟수가 아니라 입력값에 따른 알고리즘 실행 시간의 추이만을 살피게 된다.

 

---

각 시간 복잡도 별 로직 예시

• O(1): 입력값이 아무리 커도 실행 시간이 일정하다.
  • n의 크기가 얼마든 간에 일정한 상수를 반환하므로 O(1)이다.

// O(1) 예시 
public int fn(int n) { return 42; }

 

 

• O(log n): 입력값에 영향을 받는다.
  • 연산 횟수가 log2 n의 계산 결과와 동일하다. 컴퓨터 과학에서는 주로 밑인 2를 생략하여 log n으로 표현한다. 사실상 O(log n) 정도면 최고의 알고리즘이라 할 수 있다. 대표적으로 이진 검색(Binary Search)이 이에 해당한다.

// O(log n) 예시
public int fn(int n) { 
    while(n > 1) n /= 2;
    return n; 
}

 

 

• O(n): 정확히 입력값(n)의 크기만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다.

// O(n) 예시
public int fn(int n) { 
    int r = 0;
    
    for (int i = 0; i < n; i++) {
        r++; 
    }
    
    return r;
}

 

 

• O(n log n): 입력값만큼 순회하며 log n의 연산이 곱해진다.
  • 병합정렬(Merge Sort)을 비롯한 효율적인 정렬 알고리즘이 이에 해당한다. 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없다. 물론 입력값이 최선인 경우, 비교를 건너뛰는 최적화를 추가하면 O(n)이 될 수 있으며 파이썬의 기본 정렬 알고리즘인 팀소트(Tim sort)가 이런 로직을 갖고 있다. 하지만 기본적으로 모든 정렬 알고리즘은 최악의 경우O(n log n)보다 빠를 수 없다. 실용적인 관점에서 O(n)이나 O(n log n)은 사실상 비슷한 성능으로 나온다.

// O(n log n) 예시
public int fn(int n) { 
    int r = n; 
    
    for (int i = 0; i < n; i++) {
        while (n > 1) n /= 2;
        n = r; 
    }
    
    return r; 
}

 

 

• O(n^2): 입력값의 제곱만큼 연산한다.
  • 버블정렬(Bubable Sort)같은 비효율적인 정렬 알고리즘이 이에 해당한다. 입력값이 클 경우 n^2 부터는 타임아웃이 발생하는 경우가 잦기 때문에 최적화를 필요로 하는 단계다. 코딩 테스트에서 알고리즘을 최적화한다고 하면 O(n^2)을 O(n log n)으로 줄이는 일이 거의 대부분이다.

public int fn(int n) { 
    int r = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            r += j; 
        }
    } 

    return r; 
}

 

 

• O(2^n): 입력값의 크기만큼 2배씩 연산한다.

public int fn(int n) {
    if (n <= 1) return;
    else return fn(n - 1) + fn(n - 2);
}

---

 

빅오를 계산하는 실용적인 방법

 웬만큼 알고리즘에 익숙하더라도 헷갈릴 때가 많다. 팩토리얼(n!) 계산 같은 게 그런 예다.

public int factorial(int n) {
    if (n >= 1) return n * factorial(n - 1);
    else return 1;
}

얼핏 봐서는 팩토리얼 계산이고 재귀도 있어 시간복잡도가 O(n!)쯤 될 것으로 예상한다. 하지만 재귀는 n, n-1, n-2, … 순으로 한 번씩만 구하면 되기 때문에 시간 복잡도는 O(n)에 불과하다. 정확하게 계산하기 위해 좋은 방법이 있다. 아래 예시코드에서 연산횟수를 살펴보자.

int count = 0;
public int factorial(int n) {
    if (n >= 1) {
        count++;
        return n * factorial(n-1);
    } else {
        count++;
        return 1;
    }
}

이처럼 연산 횟수를 직접 헤아리는 방법이 가장 쉬운 방법이다.