[Data Structure] 공간 복잡도 (Space Complexity)

1. 공간 복잡도 (Space Complexity)

• 공간 복잡도(Space Complexity)란 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양이다.

2. 프로그램의 공간 구성 요소

• 고정부분: 프로그램의 입출력 특성(e.g. 횟수, 크기)과 관계 없음. ⇒ 명령어 공간 및 상수 공간과 연관
• 가변 부분: 문제의 인스턴스에 의해 크기가 결정되는 요소 변수가 필요로 하는 공간과 참조된 변수가 필요하는 공간, 순환 스택 공간

3. 공간 복잡도 예제

3.1 단순 산술 계산 반환 함수

// code#1
float Abc(float a, float b, float c)
{
	return a + b + b*c + (a + b - c)/(a + b) + 4.0;
}

• code#1에서 문제 인스턴스는 a, b, c의 특정한 값으로 특징지을 수 있음.
• float형 a, b, c를 각각 저장하고, 함수 Abc에서 값을 반환하는 데에 1개의 워드(word)가 필요하다고 가정함.
• 함수 Abc에서 필요한 공간은 인스턴스 특성과 관계 없음.
• 따라서, 인스턴스 특성(S)는 0임.

3.2 합산을 위한 반복 함수

// code#2
float Sum(float *a, const int n)
{
	float s = 0;
	for (int i = 0; i < n; i++)
		s += a[i];
	return s;
}

• code#2에서 문제 인스턴스는 합산할 원소의 수인 n으로 특징지을 수 있음.
• n 이 값으로 넘겨지기 때문에 1개의 워드(word)가 필요함.
• *a는 a[] 에 있는 첫 번째 원소인 주소(a[0])이므로 한 워드(word)가 필요함.
• 따라서, 함수에 필요한 공간은 n 과 무관하며, 인스턴스 특성(S)는 0임.

3.3 합산을 위한 순환 함수

// code#3
float Rsum(float *a, const int n)
{
	if (n <= 0) return 0;
	else return (Rsum(a, n-1) + a[n-1]);
}

• code#3에서 문제 인스턴스는 합산할 원소의 수인 n으로 특징지을 수 있음.
• 순환 스택 공간에는 형식 인자, 지역 변수, 반환 주소가 포함됨.
• *a는 a[0] 의 주소이므로 스택의 메모리에는 1개의 워드(word)가 필요함.
• Rsum 을 호출할 때마다 최소 4개의 워드(word)가 필요함. ⇒ n , a의 값 , return 값 , return 주소 의 공간 포함
• 순환의 깊이가 n + 1 이므로, 순환 스택 공간에서 공간은 4(n + 1) 이 필요함.
• 즉, n = 1000 이면 순환 스택 공간은 4004 가 됨.