[알고리즘] 공간복잡도

---

* 시간 복잡도 : 알고리즘이 실행되는 상대적인 시간

https://geukggom.tistory.com/159

[알고리즘] 점근 표기법(Asymptotic Notation)과 빅 오의 사용 방법

 

1. 공간 복잡도란?

: 알고리즘이 실행될 때 필요한 저장 공간.

효율적인 알고리즘은 시작부터 결과가 나올 때까지 실행에 걸리는 시간이 짧고(작은 시간복잡도), 연산하는 컴퓨터 내의 메모리 자원을 덜 사용하는 것(작은 공간 복잡도)입니다.

시간복잡도와 공간복잡도는 반비례하는 경향이 있습니다.

 

* 총 저장 공간 = 고정 공간 + 가변 공간

- 고정 공간 : 알고리즘과는 상관 없는 공간. 코드를 저장하는 공간, 단순 변수 및 상수의 저장 공간이 포함됩니다.

- 가변 공간 : 알고리즘 실행과 관련이 있는 공간. 실행 중 동적으로 필요한 공간입니다.

 

 

2. 공간 복잡도의 예시

n!(1부터 n까지 곱한 것)을 구현한 두가지 알고리즘이 있습니다.

 

1번.

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

 

 

2번.

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

 

 

1번 코드의 경우 factorial이라는 함수는 n번 만큼 반복하게 되고, n만큼의 공간을 사용하게 됩니다. 그래서 1번 코드의 공간 복잡도는 O(n)으로 표시합니다. 반면, 2번 코드는 n의 값과는 상관없이 factorial이라는 함수를 1번 사용합니다. 그래서 2번 코드의 공간 복잡도는 O(1)입니다.