공간 복잡도와 공간 복잡도 함수

공간 복잡도(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) 입니다.

Time Complexity & Space Complexity

시간 복잡도는 “얼마나 빠르게 실행되느냐 “그리고 공갑 복잡도는 “얼마나 많은 자원이 필요한가?”