공간 복잡도

공간 복잡도는 입력의 특성에 따라 계산 문제의 인스턴스를 해결하는 데 필요한 메모리 공간의 양이다. 이는 알고리즘이 완전히 실행될 때까지 필요한 메모리이며, 입력 공간(입력 데이터 저장)과 보조 공간(실행 중 추가로 사용하는 메모리)을 모두 포함한다. 시간 복잡도와 마찬가지로 공간 복잡도는 점근적 분석을 통해 알고리즘의 성능을 직관적으로 파악하는 데 목적이 있다. 정확한 메모리 사용량보다는 입력 크기에 따른 증가 추세를 분석한다.

알고리즘이 사용하는 총 공간은 크게 고정 공간과 가변 공간으로 구분된다.

• 고정 공간: 입력 데이터의 크기와 관계없이 고정적으로 필요한 공간이다. 프로그램 코드 저장 공간, 단순 변수, 상수 등이 이에 해당한다.
• 가변 공간(보조 공간): 알고리즘 실행 과정에서 동적으로 필요한 공간이다. 실행 중에 사용하는 보조 메모리, 함수가 순환 호출(재귀)될 때 필요한 스택 공간, 추가로 생성하는 배열 등이 포함된다.

예를 들어, 재귀 함수는 호출 스택에 각 호출의 상태를 저장하므로 깊이에 비례하는 공간을 사용한다.

공간 복잡도는 시간 복잡도와 마찬가지로 점근 표기법을 사용하여 표현한다. 가장 널리 쓰이는 방식은 빅오 표기법($O$)이며, 이외에도 세타($\Theta$), 오메가($\Omega$) 표기법이 사용된다. 입력 크기를 $n$이라 할 때, 주요 복잡도는 다음과 같다.

• $O(1)$: 입력 크기와 무관하게 일정한 공간을 사용한다. (예: 변수 몇 개만 사용하는 알고리즘)
• $O(\log n)$: 입력 크기의 로그에 비례하여 공간을 사용한다. (예: 이진 탐색의 재귀 호출 스택)
• $O(n)$: 입력 크기에 비례하여 공간을 사용한다. (예: 입력 배열을 그대로 저장)
• $O(n \log n)$: 입력 크기와 로그의 곱에 비례한다. (예: 병합 정렬의 추가 배열)
• $O(n^2)$: 입력 크기의 제곱에 비례하여 공간을 사용한다. (예: 2차원 배열)
• $O(2^n)$: 지수적으로 증가하는 공간을 사용한다. (예: 부분 집합 생성)

결정적 튜링 기계와 비결정적 튜링 기계가 사용하는 공간에 따라 복잡도 계급이 정의된다.

• DSPACE(f(n)): 결정적 튜링 기계가 $O(f(n))$ 공간을 사용하여 해결할 수 있는 문제 집합이다.
• NSPACE(f(n)): 비결정적 튜링 기계가 $O(f(n))$ 공간을 사용하여 해결할 수 있는 문제 집합이다.
• PSPACE: 임의의 다항식 크기 공간을 사용하여 해결할 수 있는 문제들의 집합으로, $PSPACE = \bigcup_{c \in \mathbb{Z}^+} DSPACE(n^c)$와 같이 정의된다.
• NPSPACE: 비결정적 튜링 기계에 대한 다항식 공간 문제 집합이다. 사비치 정리(Savitch's theorem)에 따르면 $NPSPACE = PSPACE$이다.

이러한 계급은 계산 복잡도 이론에서 중요한 위치를 차지하며, 문제의 난이도를 공간 측면에서 분류한다.

좋은 알고리즘은 시간 복잡도와 공간 복잡도가 모두 낮은 알고리즘이다. 그러나 일반적으로 시간과 공간은 반비례 관계(Trade-off)를 갖는 경우가 많다. 즉, 메모리를 더 많이 사용하여 실행 시간을 단축하거나, 반대로 실행 시간을 늘려 메모리 사용량을 줄이는 방식이다.

예를 들어, 동적 계획법(Dynamic Programming)은 메모이제이션을 통해 중복 계산을 피하지만 추가 메모리를 사용한다. 반면, 재귀적 분할 정복은 추가 메모리를 적게 사용하지만 동일한 부분 문제를 반복 계산할 수 있다.

최근에는 하드웨어의 발전으로 메모리 용량이 증가함에 따라 공간 복잡도보다는 시간 복잡도를 더 우선시하는 경향이 있지만, 임베디드 시스템이나 대규모 데이터 처리에서는 여전히 공간 효율성이 중요하다.

다음은 대표적인 알고리즘의 공간 복잡도 예시이다.

이러한 예시는 공간 복잡도가 알고리즘 설계에 미치는 영향을 보여준다.