[자료구조] 공간 복잡도

공간 복잡도를 알기에 앞서서

알고리즘 계산 복잡도는 시간 복잡도와 공간 복잡도로 이루어져 있음

시간 복잡도는 "얼마나 빠르게 실행되는가" 이고,

공간 복잡도는 "얼마나 많은 저장 공간이 필요한가" 이다.

 

좋은 알고리즘을 짜기 위해서는 빠르게 실행되면서도 적은 공간을 사용하는 것이 맞다.

 

하지만 둘 다 충족시키기에는 어렵기 때문에 공간 복잡도보다는 시간 복잡도가 우선시 된다.

그렇지만 메모리 최적화가 필요한 부분에서는 시간 복잡도보다 중요하게 다룬다.

 

공간 복잡도는 무엇일까?

1. 의미

공간 복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양

2. 정의

알고리즘이 실행될 때 필요한 전체 메모리 공간을 입력 크기 n에 따라 표현한 것

3. 표현 방식

보통 빅오 표기법을 사용하여 표현한다

예) O(1), O(n), O(n^2) 등

 

4. 포함 요소

4 - 1. 고정 공간: 변수, 상수 등 입력 크기와 무관한 공간

 

예시)

int sevenInt = 7;
float sevenFloat = 7.777777f;
bool isLucky = false;

변수 sevenInt, sevenFloat, isLucky는 모두 일정한 크기만 사용합니다.

이것들은 입력 크기 n과 관계가 전혀 없기 때문에 고정 공간이다.

공간 복잡도: O(1)

 

4 - 2. 입력 공간: 입력 데이터를 저장하기 위한 공간

 

예시)

vector<int> ValueList(const vector<int>& vec) {
    vector<int> ret;
    for(int v : vec) ret.push_back(v);
    return ret;
}

ValueList라는 vector<int>를 리턴하는 메서드에서 매개변수로 전달된 vector<int>는 입력 공간에 해당한다.

공간 복잡도: O(n)

 

4 - 3. 보조 공간: 알고리즘이 추가로 사용하는 임시 공간

 

예시)

vector<int> filterEven(const vector<int>& vec) {
    vector<int> ret;
    for(int v : vec) {
        if(v % 2 == 0) ret.push_back(v);
    }
    return ret;
}

짝수들을 구해서 vector<int>로 리턴하는 메서드에서 ret은 알고리즘을 실행 중 생긴 추가적인 공간이기에 보조 공간에 해당한다. 

공간 복잡도: O(n)

 

5. 메모리제한

Int타입 배열 기준

메모리	입력 크기
64MB	약 1500만
128MB	약 3000만
256MB	약 6000만
512MB	약 1억2천만

 

계산법(근사값)

(메모리) x 10^6 / (자료형 크기)

 

6. 재귀함수

재귀함수에서의 공간복잡도는 함수가 호출될 때마다 스택 프레임이 쌓이기 때문에 얼마나 많은 메모리를 사용하는지를 측정하는 것인데, 재귀 깊이가 공간 복잡도를 결정짓는 것이 핵심입니다.

 

스택 프레임은 매개변수, 지역 변수, 복귀 주소 3가지를 담고 있으며, 재귀 호출이 깊어질수록 메모리 사용량도 증가합니다.

 

2가지의 예시를 한번 봅시다.

 

예시 1) 팩토리얼

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

만약에 factorial(5)를 호출 했다면, factorial(4), factorial(3)... 이렇게 총 5번의 스택이 쌓이고,

각 호출은 n이라는 지역 변수와 복귀 정보를 담고 있기 때문에 재귀의 깊이는 n이므로

공간복잡도는 O(n)이 됩니다.

 

예시 2) 피보나치

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

 

트리 형태로 중복 호출이 발생하며, fib(5)를 호출했을 때 거의 2^n에 가까운 호출이 발생한다

하지만 같은 값을 여러 번 계산해도, 공간 복잡도는 최대 재귀 깊이 기준으로 계산하기 때문에

가장 깊은 경로가 fib(n) -> fib(n-1) -> ... fib(1) 이므로 공간복잡도는 O(n)이 됩니다.

 

마지막으로 정리를 하면 재귀 함수의 공간 복잡도는 = 최대 재귀 깊이 x (프레임당 메모리)가 되고,

일반적으로 O(재귀 깊이)로 표기하며, 반복문은 스택을 쓰지 않기 때문에 O(1)이 됩니다.

 

7. 최적화

공간 복잡도 측면에서 최적화 하는 방법은 알고리즘이 사용하는 메모리를 줄이는 것이다.

 

첫번째는 배열 대신에 변수를 이용해서 최적화 하는 방법이다.

// 공간 복잡도 O(n)
int fib(int n) {
    vector<int> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// 공간 복잡도 O(1)
int fib_optimized(int n) {
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return b;
}

위는 배열을 통해서 피보나치를 구현한 것이고,

아래는 배열 없이 변수를 통해서 피보나치를 구현한 것이다.

단지 위는 dp라는 배열을 사용한 공간이기에 O(n)이며, 

아래는 a,b라는 변수만을 사용한 공간이기에 O(1)이다.

따라서 배열을 사용했는지 변수만을 사용했는지에 따라서 공간복잡도가 차이가 나는 것이다.

 

두번째는 입력 데이터를 직접 재사용하는 것이다.

void reverse(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r)
        swap(nums[l++], nums[r--]);
}

reverse라는 입력받아 저장되어 있는 값들의 순서를 바꾸는 함수인데,

자세히 보면 이 함수에서는 새로 배열을 만들어 리턴을 해주지 않고 입력받은 nums 자체를 바꾸고 있다.

따라서 입력 크기에 상관없이 추가로 사용하는 메모리인 단지 변수 2개와 복사본을 만들지 않은 nums는 인자로 참조 전달하고 있고, 새로운 배열을 만들지 않았기 때문에 O(1)이 된다.

불필요한 새로운 배열을 만들지 않고도 기존 배열만을 수정해서 할 수 있다면 하는 것이 최적화에 좋다.