자료 구조와 복잡도(Complexity) (1) - 복잡도의 개념과 빅오(Big-O) 표기법

본 포스팅에서는 복잡도의 개념 및 종류와 이를 효율적으로 표기하는 빅오(Big-O) 표기법에 대해 설명하고 이를 이용해 Java 의 Collection 자료구조별 복잡도를 분석합니다.

복잡도(Complexity)란 단순히 알고리즘을 실행하는 데 얼마만큼의 자원(시간 또는 메모리)이 필요한지에 대한 지표입니다.

또한 이 기준 자원에 따라 **시간 복잡도(Time Complextiy)**와 **공간 복잡도(Space Complexity)**로 나뉩니다.

시간 복잡도(Time Complexity)는 알고리즘을 실행하는 데 걸리는 시간을 의미하며 보통 단순화하여 연산 횟수를 기준으로 산정합니다.

public void calculateTimeComplexity(int n) {
    int number = 1;						// 1
    for (int i = 0; i < n; i++) {
        number++;						// n
    }
}

위와 같은 함수가 있다고 가정하면 연산 횟수는 아래와 같이 산정됩니다.

그리고 이 연산 횟수 즉, 시간 복잡도는 아래와 같은 방정식으로 표현할 수 있습니다. $$ f(n)=n+1 $$ 하지만 충분히 복잡한 알고리즘에서 모든 연산 횟수를 표기하기에는 방정식도 복잡해질 수 있고, 이는 단순히 지표로 이용하는 데에 불필요합니다.

그래서 복잡도를 표현하는 데 사용하는 표기법이 바로 빅오(Big-O) 표기법입니다.

빅오(Big-O) 표기법은 최악의 경우(위 예시에서는 n번 수행하는 연산)만을 고려하는데, 기본적인 규칙은 다음과 같습니다.

이 규칙에 따라 가장 영향력이 큰 항만을 이용해 시간 복잡도 표현식을 다음과 같이 표현할 수 있습니다. $$ n+1 = O(n) $$

$$ 2n^2 + 3n + 1 = O(n^2) $$

하지만 자료구조와 로직별로 복잡도 표현식이 정형화되어 있어, 개발자가 보통 복잡도의 정확한 값을 직접 계산하지 않고 아래와 같이 정형화된 근사값을 이용합니다.

복잡도	예시
O(1)	Stack(push, pop)
O(log n)	이진트리
O(n)	for 문
O(n log n)	퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort)
O(n^2)	이중 for 문, 삽입 정렬(insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort)
O(2^n)	피보나치 수열

위 표에서 아래로 갈수록 복잡도가 높고 성능이 떨어짐을 의미하며, 아래 그래프는 복잡도별 소요시간 증가를 시각화한 것입니다.

또한 경우에 따라 아래와같이 시간 복잡도를 구할 수 있습니다.

공간 복잡도(Space Complexity)는 알고리즘을 실행하는 데 메모리가 얼마나 필요한지를 의미하며 보통 단순화하여 메모리 할당 횟수를 기준으로 산정합니다.

컴퓨터 하드웨어 성능의 비약적인 상승으로 상대적으로 시간 복잡도에 비해 중요도는 떨어지지만 대량의 데이터를 다루는 빅데이터, AI 분야에서는 여전히 중요한 지표로 여겨집니다.

공간 복잡도도 시간 복잡도와 같이 빅오(Big-O) 표기법으로 나타낼 수 있으며, 아래 n 팩토리얼 계산 예시들을 통해 표현해보겠습니다.

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

위와 같이 재귀 호출로 n 팩토리얼을 계산하는 함수가 있다고 가정하면, n 부터 1 까지 재귀호출로 인한 반환 결과가 메모리상에 n회 할당되므로 O(n) 으로 나타낼 수 있습니다.

public int factorial(int n) {
    int result = 1;
    for (int j = n; j > 0; j--) {
        result *= j;
    } 
    return result;
}

만약 동일한 n 팩토리얼 계산 함수를 위처럼 수정한다면 result 변수 선언시 메모리 할당 1회, for 문의 j 변수 선언시 메모리 할당 1회로, 총 2회의 메모리 할당이 수행되며 이는 O(1) 로 나타낼 수 있습니다.