빅오 표기법: 공간 복잡도

Java 코드 최적화

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

공간 복잡도란 무엇인가요?

시간 복잡도는 입력 크기가 실행 시간에 미치는 영향을 나타냅니다
공간 복잡도는 입력 크기가 메모리 사용량에 미치는 영향을 나타냅니다

다음과 같은 애플리케이션을 만들려면 공간 복잡도를 이해하는 것이 중요합니다:

필요한 만큼만 메모리를 사용
OutOfMemoryError와 같은 오류로 인한 충돌 방지

빅오 표기법

표기법은 시간 복잡도와 동일합니다.

일반적인 복잡도 클래스:

O(1): 상수 시간 - 크기와 무관
O(n): 선형 시간 - 입력 크기에 따라 증가
O(n²): 2차 시간 - 입력 크기에 따라 제곱으로 증가

최댓값을 찾는 메서드

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

정수 배열의 요소가 10개든 1,000만 개든, 변수 max 하나에 대한 메모리만 사용합니다
공간 복잡도는 O(1), 즉 상수 공간입니다

값을 두 배로 만드는 메서드

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

입력에 n개의 요소가 있으면 n개의 추가 요소를 위한 공간이 필요합니다
필요한 추가 메모리가 입력 크기에 따라 선형적으로 증가하므로 공간 복잡도는 O(n)입니다

곱셈표를 만드는 메서드

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

n이 10이면 100개의 셀이 필요하고, n이 100이면 10,000개의 셀이 필요합니다
이를 O(n²)으로 분류합니다

공간 복잡도가 중요한 이유

메모리는 유한한 자원입니다!

입력 크기가 10,000개일 때 앞서 살펴본 예시를 실제로 적용해 보면:

findMax, O(1) -> 몇 바이트 정도만 추가
doubleValues, O(n) -> 약 40KB의 추가 메모리
multiplicationTable, O(n²) -> 약 400MB의 추가 메모리

findMax는 8바이트, doubleValues는 40KB, multiplicationTable은 400MB의 메모리 사용량 증가를 보여주는 막대그래프

공간 복잡도 vs. 시간 복잡도

기억해 두세요:

공간을 희생해서 시간을 절약하는 경우도 있고
시간을 희생해서 공간을 절약하는 경우도 있습니다
올바른 선택은 각자의 상황과 제약 조건에 따라 달라집니다

시간과 공간 간의 트레이드오프를 나타내는 그래픽

연습해 봅시다!

Java 코드 최적화