공간복잡도

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다. 즉 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미한다.

프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구한다. 여기서 집중해야 할 부분은 가변적인 공간이다. 왜냐하면 고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않기 때문이다. 그러나 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 준다.

이런 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법으로 표현한다. 아래의 가장 간단한 공간복잡도 예시를 보겠다.

공간 복잡도 예시

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

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

공간 복잡도는 얼마나 중요한가?

보통 때의 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다. 왜냐하면 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 거의 없으며 시간 내에 발생하는 메모리 문제들은 보통 알고리즘을 구현할 때에 발생하는 문제이기 때문이다.

보통 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문에 알고리즘 구현 시 공간 복잡도에 실패했다면, 보통은 변수를 설정할 때 쓸데없는 공간을 많이 차지하도록 설정했을 경우가 많을 것이니 그것부터 확인해야 한다.

그러나 때에 따라 공간 복잡도를 중요하게 보는 경우가 있는데, 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우가 바로 그 경우이다. 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력 값의 범위가 넓어지면 사용하지 못하는 경우도 많고, 하드웨어 환경이 매우 한정되어 있는 경우(ex. 임베디드, 펌웨어 등)라면 가용 메모리가 제한되어 있기 때문이다.