[Algorithm] 공간 복잡도

공간복잡도(Space Complexity)

프로그램이 얼마나 많은 공간(메모리)를 차지하느냐를 분석하는 방법

 

공간복잡도 빅-오 계산법

1) 일반적으로 공간이 하나씩 생성되는 것을 1이라고 표현함 아래의 공간복잡도는 O(1)

int a = 5;

 

2) 반복문에서의 지역변수 사용시 n값에 상관없이 공간복잡도는 O(1)

반복문이 N번만큼 반복하여도 for문 안에서의 지역변수이므로 다른 것에 영향 X

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

 

3) 재귀함수

n의 값에 따라 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간복잡도는 O(n)

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

 

프로그램에 필요한 공간은 고정, 가변 공간으로 나눌 수 있다.

시간적인 측면을 무시하고 공간복잡도만을 생각한다면 고정 공간보다는 가변 공간을 사용하는 자료구조를 사용하는 것이 효율적이다.

 

https://prinha.tistory.com/entry/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-Big-O%ED%91%9C%EA%B8%B0%EB%B2%95

[Algorithm] 시간 복잡도 & Big-O표기법

---

참고 및 출처 : https://coding-factory.tistory.com/609?category=794828