[Algorithm] 공간 복잡도

프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양을 말한다. 공간의 복잡도를 결정하는 것으로 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀함수 인지 등이 있다.

총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있다.

고정 공간은 입력과 출력의 횟수나 크기에 관계없는 공간의 요구를 말한다. ex) 코드 저장 공간, 단순 변수, 변수, 상수 저장

가변 공간은 프로그램 실행 중에 요구되는 요소이다. ex) 배열 전달, 재귀 호출, 회귀 주소

함수 호출시에 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요한데, 특히 재귀함수의 경우 매 함수 호출마다 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요하다.

대표적인 예시로 팩토리얼이 있는데, 재귀적으로 짤 수 있고 반복문로 짤 수도 있으나 후자가 더 효율적이다.

a = 1

일반적으로 공간이 하나 생성되는 것을 1이라고 표현하고, 이를 O(1)로 표기한다.

result = 0
for i in range(1,100):
	result += i

반복문이 N번만큼 반복해도 for문 안에서의 지역변수이므로 공간 복잡도는 여전히 O(1)이 된다.

ex. factorial

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

: n이 1 이하일때까지 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이게 된다. 즉 공간 복잡도는 O(n)이 된다.

def factorial(n):
	i=0
    fac=1
    for i in range(n):
    	fac=fac*i'
    return fac

: n의 값에 상관없이 스택에는 n과 i 그리고 fac 변수만 저장되므로 공간 복잡도는 O(1)이다.

* 시간 복잡도와 공간 복잡도는 반비례의 경향이 있기 때문에 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.

알고리즘을 풀 때는 시간 복잡도를 고려하자 !

gyu-ree s devlog