Algorithm - 공간복잡도(Space Complexity)

1. 개요

알고리즘의 성능을 평가하는 계산 복잡도는 두 가지로 표현된다. 

1) 시간 복잡도(Time Complexity) - 얼마나 빠르게 실행되는가 

2) 공간 복잡도(Space Complexity) - 얼마나 많은 저장공간을 필요로 하는가

 

통상적으로 두 가지 계산 복잡도를 모두 만족시키기는 어렵다. 그 이유는 다음과 같다.

- 시간과 공간은 반비례적 경향이 있다.

- 최근 대용량 시스템이 보편화되면서, 공간보다 시간 복잡도가 우선적이다.

 

그러므로 알고리즘은 시간복잡도가 우선이다. 

---

2. 공간 복잡도(Space Complexity)

- 프로그램을 실행 및 완료하는데 필요한 저장 공간의 양/크기를 의미한다.

 

 

2-A) 총 필요 저장공간 계산법

 

- 고정 공간(알고리즘과 무관): 코드, 단순 변수 및 상수의 저장공간

- 가변 공간(알고리즘과 연관): 실행 중 동적으로 필요한 저장공간 

 

→ 고정 공간보다 알고리즘에 의해 좌우되는 가변 공간이 공간 복잡도에 미치는 영향이 크다.

 

 

2-B) 공간 복잡도 계산 예제

 

예제 1) n!(팩토리얼) 연산 메소드

def factorial(n):
	fac = 1
    for index in range(2, n+1)
    	fac = fac * index
    return fac

- 위의 코드는 n의 값에 상관없이 fac, index, n 이렇게 3가지 변수를 필요로 한다.

- 그러므로 공간 복잡도는 O(1)이다.

 

 

 

예제 2) 재귀함수를 이용한 n!(팩토리얼) 연산 메소드

def factorial(n):
	if n > 1:
    	return n * factorial(n-1)
    else:
    	return 1

- 위의 코드는 재귀함수이기 때문에, n에 따라서 재귀함수가 n번 호출된다.

  ex) n이 5라면 재귀함수가 5번 호출 = 변수 n이 5번 생성된다.  

- 그러므로 공간 복잡도는 O(n)이다.