공간복잡도 정리

공간복잡도란?

공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나인데 작성한 프로그램이 얼마나 많은 공간(메모리)를 차지하느냐를 분석하는 방법이다. 다만 요즘은 컴퓨터 성능의 발달로 인해서 메모리 공간이 충분하다보니 중요도는 많이 떨어졌다고 한다. 시간복잡도의 경우에는 알고리즘을 잘 못 구성하면 결과값이 나오지 않거나 매우 느린 속도로 나오기 때문에 최근에는 시간복잡도를 더 우선시 한다고 한다.

 

공간복잡도의 계산법 - 빅오(Big-O)

x = 1

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

sum = 0

for i in range(n):
    sum += i

반복문의 경우 n번만큼 반복하더라도 for문 안에서의 지역변수이기 때문에 공간복잡도는 O(1)이 된다. n의 값과는 상관없이 i와 sum의 변수만 사용되고 다른 것은 전혀 영향을 주지 못하기 때문이다.

def factorial(n):
    if n == 1:
    	return 1
    return n * factorial(n - 1)

다만 위처럼 재귀함수일 경우 이야기가 달라진다. 위의 예제를 보면 함수의 인자값 n에 따라 공간복잡도가 달라진다. 함수 내부에서 n이 1 d이하일 때 까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이기 때문에 위의 재귀함수의 공간복잡도는 O(n)이 된다.

 

공간복잡도를 줄이는 방법

공간복잡도를 결정하는 것은 대게 배열의 크기가 몇인지, 얼마만큼의 동적 할당을 하는지, 몇 번 호출하는 재귀 함수인지 등이 공간복잡도에 영향을 미친다.

 

프로그램에 필요한 공간은 크게 두가지로 나눌 수 있는데,

1. 고정 공간

2. 가변 공간

이렇게 두가지이고 시간적인 측면을 무시하고 공간복잡도만 생각한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조가 더 효율적이다.

 

함수 호울 시 할당되는 지역변수나 동적 할당되는 객체들도 모두 공간이 필요한데, 특히나 재귀 함수와 같은 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요하기 때문에 만약 재귀적으로 짤 수도 있고, 반복문으로 짤 수도 있는 경우라면 공간복잡도 측면에서는 반복문으로 짜는 것이 더 효율적이라고 한다.

 

참고 사이트

- https://coding-factory.tistory.com/609

- https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84