[Algorithm] 공간 복잡도(Space Complexity)

1. 공간 복잡도란?

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  • S(P) = c + Sp(n)
    • c: 고정 공간
    • 𝑆𝑝(𝑛)Sp(n): 가변 공간
• 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우된다.

 

2. 공간 복잡도 계산

공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 표기법으로 표현한다.

 

2.1 O(n) 공간 복잡도 예시

n! 팩토리얼 구하기

• 재귀 함수를 통해서 구현하므로 변수 n에 따라서 변수 n이 n개가 만들어지게 됨
• factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
• 따라서 공간 복잡도는 O(n)

public int factorial(int n) {

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

 

배열에서 n인덱스 이전까지 합 구하기

• 사용되는 변수는 a[], n,result,i 이다. 
• ( a[]의 n개의 원소를 저장할 공간 ) + ( 변수 n,i,result를 위한 공간 ) 이 필요하다. a[]가 n보다 큰 공간을 할당해야하므로 O(n) 만큼의 공간 복잡도가 필요하다.

public int sum(int a[], int n){
    int result =0;          
    for(int i=0; i<n ; i++){
        result += a[i];
    }
    
    return result;
}

 

2.2 O(n) 공간 복잡도 예시

n! 팩토리얼 구하기 (반복문 버전)

• 반복문을 통해서 구현하므로 result에 저장하기 때문에 공간복잡도는 O(1)이다.
• 사용하는 변수 n, i, result

public int get_factorial(int n)
{
    int i = 0;
    int result = 1;
    
    for(i = 1; i <= n; i++)
    {
        result = result * i;
    }
    return result;
}

 

REFERENCE

https://velog.io/@aonee/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[알고리즘] 공간 복잡도