공간복잡도(Space Complexity) 란?

공간복잡도란?

프로그램 성능을 분석하는 방법 중 하나로, 프로그램이 얼마나 많은 메모리(공간)를 차지하는 가를 분석하는 방법이다.

최근에는 공간 복잡도의 중요성이 예전보다는 낮아졌다고한다.

그 이유는 반도체 기술향상이다. 메모리의 공간이 충분하기 때문에 그렇다.

공간복잡도는 총 공간요구 = 고정공간 요구 + 가변공간 요구 로 나타낼 수 있다. 수식은 S(P) = c + Sp(n)으로 표기한다.

* 고정 공간(알고리즘과 무관한 공간) 
: 코드 저장 공간, 단순 변수 및 상수 (문제의 인스턴스에 무관, 일정한 양의 메모리공간)
* 가변 공간(알고리즘 실행과 관련있는 공간)
: 실행 중 동적으로 필요한 공간 (문제의 인스턴스에 따라 가변적인 메모리 공간)

 

공간복잡도를 줄이는 방법은?

고정공간 보다는 가변공간을 사용할 수 있는 자료구조를 사용하면 된다.

또한 함수 호출 시 할당되는 지역변수들이나 할당되는 개체들도 모두 공간이 필요한다 특히 재귀함수 같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요하기 때문에 재귀를 반복문으로 코드 설계를 할 수 있다면 공간복잡도 줄이는 방법에서는 반복으로 코드를 작성하는 게 더 효율적이다.

 

• 변수 하나를 선언하면 O(1)
• 일반 적인 반복문에 변수 하나를 선언해서 루프를 돌릴 시에도 O(1)
• 재귀함수는 함수 내부에서 n이 1까지의 팩토리얼을 구현함으로 스택에는 n부터 1까지의 공간이 쌓인다. 따라서 복잡도는 O(n) 이다.