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

시간 복잡도, 공간 복잡도

시간 복잡도

소스 코드 로직의 실행 시간(Execution Time)을 예측해 얼마나 효율적인 코드인가를 나타내는 개념이다. 실행 시간은 연산(Operation)에 비례해 길어진다. CPU사용량과 관련 있다.

공간 복잡도

코드가 얼마나 메모리 공간을 효율적으로 사용하는지에 대한 개념이다. 정적 배열이나 해시 테이블 처럼 공간을 미리 확보하는 자료구조에 자주 등장하는 개념이다. RAM 사용량과 관련 있다.

소스 코드 로직에 먼저 동작이 되어야 하겠지만, 동작뿐 아니라 시공간 복잡도를 계산하여 얼마나 효율적인 코드인지 여부가 판가름 된다.

빅오(Big O) 표기법이란

빅오(Big-O)는 시공간 복잡도를 수학적으로 표시하는 대표적인 방법이다. 단, 코드의 실제 러닝 타임을 표시하는 것이 아니며, 인풋 데이터 증가율에 따른 알고리즘의 성능을 (논리적으로) 예측하기 위해 사용한다. 빅오 표기법에는 다음 2가지 규칙이 있다.

가장 높은 차수만 남긴다.

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

계수 및 상수는 과감하게 버린다.

O(4n + 5) -> O(n)

빅오 표기법으로 시간 복잡도 구분하기

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다. 데이터가 증가해도 성능에 영향을 거의 미치지 않는다.

O(log₂ n) (Logarithmic)

입력 데이터의 크기가 커질 수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 된다. 선형 탐색 알고리즘이 대표적이다.

O(n log₂ n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배 만큼 더 늘어나는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 Merge sort, Quick sort의 평균 시간 복잡도이다.

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다. 이중 루프(n² matrix)가 대표적이다. 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는것이 바람직하다.

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.

시간의 복잡도 계산법

명령이 끝날때마다 실행 횟수를 적어본다.

기본 계산법

public static void basic() {
    int[] a = {7, 3, 6, 3, 3, 5, 6, 9};          // 1
    for (int i = 0; i < a.length - 1; i++) {     // n             [i > 0 to n-1 : n times called]
        for (int j = i + 1; j < a.length; j++) { // (n-1) * n     [j > 1 to n   : n times called]
            if (a[i] == a[j]) {                  // (n-1) * (n-1) [if 문은 결국 n-1 번만 실행 ]
                a[j] = 0;
            }
        }
    }

    for (int i : a) {
        System.out.println(i);
    }
}

명령어 실행횟수를 모두 더하면 2n²-2n+2 -> 상수는 생략하고 최고차항만 생각하면, O(n²)로 표기된다.

재귀함수 시간 복잡도 계산법

public static int factorial(int n) {
    System.out.println("n:" + n);
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

재귀 호출은 아래와 같이 n번이 호출하게 된 것이다. 그래서 O(n)으로 표기된다.

factorial(n) -> factorial(n -1) .... ->factorial(2) -> factorial(1)