[알고리즘] 공간복잡도

 

빅-O 표기법

 

 

1.  공간 복잡도

- 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지를 나타낸다.

- 시간 복잡도 : 얼마나 빠르게 실행되는지를 나타낸다.

- 알고리즘은 공간 복잡도, 시간 복잡도를 통하여 평가될 수 있다.

- 이 중 우리가 더욱더 집중해야 하는 부분은 시간 복잡도 이다.

  - 왜냐하면 최근에는 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선되기 때문이다.

  - 하지만 좋은 알고리즘은 실행 시간도 짧으며, 저장 공간도 적게 쓰는 알고리즘이다. 

 

 

 

 

2.  공간 복잡도의 계산 방법 

- 총 필요 저장 공간 : 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.

  (실제 알고리즘 실행시 사용되는 저장 공간을 계산하면 된다. )

  - 고정 공간 (알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 

  - 가변 공간 : 실행 중 동적으로 필요한 공간 

• S(P) = c + Sp(n)
  • c: 고정 공간
  • 𝑆𝑝(𝑛): 가변 공간

공간 복잡도 또한 시간 복잡도와 마찬가지로 빅 오 표기법을 사용하여 계산하는데,

입력 개수에 따라 고정 공간이 얼마나 늘어나느냐를 기반으로 계산된다. 

 

 

 

3. 공간 복잡도 예제  

- n! 팩토리얼 구하기  (1)

  - n! = 1 x 2 x... x n

-  n의 값에 상관없이 변수 n, 변수 fac, 변수 i 만 필요하다.

- 공간 복잡도 O(1)

 

public int factorial(int n) {
    int fac = 1;
    for (int i = 2; i < n+1; i++) {
        fac = fac * i;
    }
    return fac;
}

 

 

- n! 팩토리얼 구하기  (2)

  - n! = 1 x 2 x... x n

-  재귀 함수를 사용해서 풀이할 경우 n에 따라 변수 n이 n개가 만들어지게 된다.

  - factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨.

- 공간 복잡도 O(n)

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