공간 복잡도

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

공간 복잡도는 컴퓨터 과학에서 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 양을 나타낸다. DSPACE(f(n))과 NSPACE(f(n))은 각각 결정적 및 비결정적 튜링 기계가 O(f(n)) 공간을 사용하여 결정할 수 있는 언어 집합을 의미하며, PSPACE와 NPSPACE는 다항식 공간을 사용하는 문제를 나타낸다. 공간 복잡도 계급 사이에는 DTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ DTIME(2O(f(n)))의 포함 관계가 성립하며, 사비치 정리는 NSPACE(f(n)) ⊆ DSPACE((f(n))2)임을 보여준다. LOGSPACE (또는 L)는 O(log n) 공간을 사용하여 풀 수 있는 문제의 집합이며, 보조 공간 복잡도는 입력 외에 추가로 사용되는 공간을 의미한다.

공간 복잡도

알고리즘

범주	알고리즘 분석
자료 구조	알고리즘

공간 복잡도

정의	알고리즘이 사용하는 컴퓨터 메모리의 양
측정 기준	입력 크기 n에 대한 함수로 표현
예시	O(1): 입력 크기에 관계없이 일정한 메모리 사용 (예: 상수 크기의 변수 사용) O(n): 입력 크기에 비례하는 메모리 사용 (예: 크기 n의 배열 생성) O(n^2): 입력 크기의 제곱에 비례하는 메모리 사용 (예: n x n 크기의 2차원 배열 생성)
관련 개념	시간 복잡도

📚 더 읽어볼만한 페이지

계산 자원 - 계산 복잡도
계산 복잡도는 알고리즘의 효율성을 평가하는 척도로, 시간, 공간 등의 자원을 고려하며, 입력 크기의 함수로 표현되고, 빅 오 표기법을 사용하여 알고리즘의 예상 성능을 파악하는 데 중요한 역할을 한다.
계산 자원 - 시간 복잡도
시간 복잡도는 알고리즘의 효율성을 분석하는 지표로서, 문제 해결에 필요한 시간과 입력 크기 간의 관계를 빅 오 표기법으로 표현한다.
계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간

1. 개요
2. 공간 복잡도 계급
3. 계급 사이의 관계
4. LOGSPACE
5. 보조 공간 복잡도

2. 공간 복잡도 계급

시간 복잡도 계급 DTIME(f(n)) 및 NTIME(f(n))과 유사하게, 복잡도 계급 DSPACE(f(n))와 NSPACE(f(n))은 $O(f(n))$ 공간을 사용하는 결정적 및 비결정적 튜링 기계에 의해 결정 가능한 언어 집합이다. 복잡도 계급 PSPACE 및 NPSPACE는 P와 NP와 유사하게 임의의 다항식이 될 수 있다. 즉,
$\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)$
및
$\mathsf{NPSPACE} = \bigcup_{c \in \Z^+} \mathsf{NSPACE}(n^c)$
이다.

공간 계층 이론에 따르면 공간 구성이 가능한 모든 함수 $f(n)$ 에 대해 메모리 공간 $f(n)$ 을 가진 기계로 풀 수 있지만, 점근적으로 $f(n)$ 보다 작은 메모리 공간을 가진 기계는 풀 수 없는 문제가 존재한다.

복잡도 계급 간에는 다음과 같은 포함 관계가 성립한다.
$\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)$

또한 사비치 정리에 따라 $f \in \Omega(\log(n))$ 인 경우 아래의 역의 포함 관계가 성립한다.
$\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right)$

직접적인 따름정리로 $\mathsf{PSPACE} = \mathsf{NPSPACE}$ 이 성립한다. 이 결과는 비결정적 기계가 문제를 해결하는 데 필요한 공간을 조금만 줄일 수 있다는 것을 뜻하기에 놀랍다. 대조적으로, 지수 시간 가설은 시간 복잡도에 대해 결정론적 복잡도와 비결정론적 복잡도 사이에 기하급수적인 차이가 있을 수 있다고 추측한다.

3. 계급 사이의 관계

공간 계층 정리에 따르면, 모든 공간 구성 가능 함수 f(n)에 대해 f(n) 메모리 공간으로 풀 수 있지만, 점근적으로 f(n)보다 작은 메모리 공간으로는 풀 수 없는 문제가 존재한다.

복잡도 계급 간에는 다음과 같은 포함 관계가 성립한다.
:DTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ DTIME(2^O(f(n)))

또한, 사비치 정리에 따라 f ∈ Ω(log(n))인 경우 다음이 성립한다.
:NSPACE(f(n)) ⊆ DSPACE((f(n))²)

이로부터 PSPACE = NPSPACE가 성립한다. 이는 비결정적 기계가 문제를 해결하는 데 필요한 공간을 조금만 줄일 수 있다는 것을 의미한다. 반면, 지수 시간 가설은 결정적 시간 복잡도와 비결정적 시간 복잡도 사이에 지수적인 차이가 있을 수 있다고 추측한다.

이머만-스제레페세니 정리에 따르면, f∈Ω(log(n))일 때, NSPACE(f(n))은 보완에 대해 닫혀있다. 예를 들어, NP ≠ co-NP라고 추측된다.

4. LOGSPACE

L 또는 LOGSPACE는 입력 크기에 대해 O^영어(log n) 메모리 공간만 사용하여 결정적 튜링 기계로 해결할 수 있는 문제들의 집합이다. 전체 n^영어 비트 입력을 인덱싱할 수 있는 단일 카운터조차 log n^영어 공간이 필요하므로, LOGSPACE 알고리즘은 상수 개의 카운터 또는 유사한 비트 복잡도를 가진 다른 변수만 유지할 수 있다.

LOGSPACE 및 기타 하위 선형 공간 복잡도는 컴퓨터의 RAM에 맞지 않는 대량의 데이터를 처리할 때 유용하다. 이는 스트리밍 알고리즘과 관련이 있지만, 사용 가능한 메모리 양만 제한하는 반면, 스트리밍 알고리즘은 입력이 알고리즘에 어떻게 제공되는지에 대한 추가 제약이 있다.
이 클래스는 또한 의사 난수 및 비무작위화 분야에서 사용되며, 연구자들은 L = RL인지 여부에 대한 미해결 문제를 고려한다.

이에 해당하는 비결정적 공간 복잡도 클래스는 NL이다.

5. 보조 공간 복잡도

보조 공간은 입력에 의해 사용되는 공간 외에 추가적으로 사용되는 공간을 의미한다.

보조 공간 복잡도는 읽기 전용 입력 테이프와 쓰기 가능한 작업 테이프를 가진 튜링 기계를 통해 정의된다.

예를 들어, n개의 노드를 가진 균형 이진 트리에 대한 깊이 우선 탐색의 보조 공간 복잡도는 Θ(log n)이다.