알고리즘/공간 복잡도

공간 복잡도 (Space Complexity)

• 알고리즘이 수행되는 데에 필요한 메모리의 총량

프로그램이 요구하는 공간 ⇒ 고정적인 공간 + 가변적인 공간
고정적인 공간: 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않음
가변적인 공간: 처리할 테이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줌!

• 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오(Big-O) 표기법으로 표현

• 보통 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다.
  • WHY? 시간이 적으면서 메모리까지 지속적으로 증가하는 경우는 거의 없기 때문에..
  • BUT! 동적 계획법(Dynamic Programming)과 같이 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우, 공간 복잡도가 중요!!
• ex) 

function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}

변수 n에 따라 변수 n이 n개가 만들어지게 되며, 해당 함수를 재귀함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 됩니다.
따라서 해당 함수의 공간 복잡도는 O(n)입니다.