[CS] 알고리즘의 공간 복잡도(Space Complexity)란?

 

1. 정의
공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리의 양을 나타냅니다. 

전체 공간 복잡도 = 입력 공간 + 보조 공간 으로 나뉘지만 

알고리즘 자체의 공간 복잡도에 집중해야 보조 공간 (auxiliary space complexity) 메모리 효율성 평가에 유용하며 입력 크기와 무관한 추가 메모리 사용을 명확히 파악 가능하므로

여기서는 입력 되는 크기는 제외하고 알고리즘 자체가 얼마나 많은 추가 메모리가 필요한지를 측정합니다.

 

2. 표기법
보통 빅오(Big O) 표기법을 사용합니다. 예: O(n), O(1), O(n^2) 등

3. 종류
고정 공간: 입력 크기와 무관한 상수 공간
가변 공간: 입력 크기에 따라 변하는 공간

 

4. 예시

 

4-1. O(1) 공간 복잡도 예시

function findMax(arr) {
    let max = arr[0];  // O(1) 보조 공간
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

이 함수는 입력 배열의 크기와 관계없이 항상 일정한 추가 메모리(변수 max)만 사용하므로 O(1) 공간 복잡도를 가집니다.

 

4-2. O(n) 공간 복잡도 예시

function reverseArray(arr) {
    let reversed = [];  // O(n) 보조 공간
    for (let i = arr.length - 1; i >= 0; i--) {
        reversed.push(arr[i]);
    }
    return reversed;
}

 

이 함수는 입력 배열의 크기에 비례하는 새로운 배열을 생성하므로 O(n) 공간 복잡도를 가집니다.

4-3. O(n^2) 공간 복잡도 예시

function createMatrix(n) {
    let matrix = [];  // O(n^2) 보조 공간
    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
            matrix[i][j] = i * j;
        }
    }
    return matrix;
}

이 함수는 n x n 크기의 2차원 배열을 생성하므로 O(n^2) 공간 복잡도를 가집니다.

4. 재귀 함수의 공간 복잡도 예시

function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 출력: 120

이 재귀 함수는 호출 스택에 O(n)의 공간을 사용하므로 O(n) 공간 복잡도를 가집니다.

 

 

5. 공간 복잡도를 고려할 때 중요한 세 가지 요소

 

 

5-1. 재귀 호출의 스택 사용

 

재귀 함수는 호출 스택을 사용하여 각 호출의 상태를 저장합니다. 이는 추가적인 메모리 사용을 의미합니다

function recursiveSum(n) {
    if (n <= 1) return n;
    return n + recursiveSum(n - 1);
}

console.log(recursiveSum(5)); // 출력: 15

 

이 함수에서 recursiveSum(5)를 호출하면 스택에는 5개의 함수 호출이 쌓입니다. 

따라서 공간 복잡도는 O(n)입니다.

 

5-2.  동적 할당된 메모리

 

프로그램 실행 중에 동적으로 메모리를 할당하는 경우, 이는 공간 복잡도에 영향을 줍니다.

function createArray(n) {
    let arr = new Array(n); // 동적으로 n 크기의 배열 생성
    for (let i = 0; i < n; i++) {
        arr[i] = i * 2;
    }
    return arr;
}

console.log(createArray(5)); // 출력: [0, 2, 4, 6, 8]

이 함수는 입력 크기 n에 비례하는 메모리를 동적으로 할당하므로 공간 복잡도는 O(n)입니다.

 

5-3.  임시 데이터 구조 사용

 

알고리즘 실행 중 임시로 사용되는 데이터 구조도 공간 복잡도에 포함됩니다.

function findDuplicates(arr) {
    let seen = new Set(); // 임시 데이터 구조
    let duplicates = [];

    for (let num of arr) {
        if (seen.has(num)) {
            duplicates.push(num);
        } else {
            seen.add(num);
        }
    }

    return duplicates;
}

console.log(findDuplicates([1, 2, 3, 2, 1, 4, 5, 4])); // 출력: [2, 1, 4]

 

이 함수는 Set과 duplicates 배열을 임시 데이터 구조로 사용합니다. 최악의 경우 (모든 요소가 고유할 때) Set의 크기가 입력 배열의 크기와 같아질 수 있으므로, 공간 복잡도는 O(n)입니다.

 

시간복잡도에 관해서는 아래 링크에서 확인 가능합니다

https://daunje0.tistory.com/3

[CS] 빅 오 표현법(Big O Notation) 간단히 살펴보기