공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다.
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P) = c + $S_p(n)$ 으로 표기합니다.
여기서 고정 공간
은 입력과 출력의 횟수나 크기와 관계없이 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말합니다.
*가변 공간
은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간을 말합니다.*
아래의 코드를 통해 공간 복잡도의 예시를 살펴봅시다.
function factorial(n) {
if(n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}
위 코드의 공간 복잡도가 어떻게 될까요? n이 1 이하일 때까지 함수가 재귀적으로 호출되므로 스택에는 n 부터 1 까지 모두 쌓이게 될겁니다. 즉 공간 복잡도는 O(n)
이 됩니다.
아래와 같이 구현하게 되는 경우는 어떻게 될까요?
function factorial(n) {
let fac = 1;
for(let i = 1; i <= n; i++) {
fac = fac * i;
}
return fac;
}
n의 값에 상관없이 스택에는 n 과 i 그리고 fac 변수만 저장됩니다. 여기서의 공간 복잡도는 O(1)
입니다.
시간 복잡도는 “얼마나 빠르게 실행되느냐 “그리고 공갑 복잡도는 “얼마나 많은 자원이 필요한가?”