공간복잡도
공간복잡도는 '입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양'을 가리킨다.
이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함하며 배열이든 맵이든 셋이든 요소들을 담을 공간이면 다 적용된다.
다음 코드에서 선언한 int형 배열 1000만개 짜리 1개, 1004개 짜리 1개 둘 다 포함해 공간 복잡도를 계산한다.
int a[10000000];
void f(){
int b[1004]
}
int main() {
}예를 들어 입력이 N이 들어왔고 거기에 따라 N개 짜리 int형 요소를 담아야 할 공간이 필요하다면 4N 바이트의 공간이 필요하다.
이를 빅오 표기법으로 나타내면 O(N)이 된다. (int형 4바이트)
int a[N];일반적으로 문제를 풀 때 배열의 범위 등을 잡는 방법
- 최대범위
보통 문제의 최대범위를 기반으로 배열을 미리 만든다.
ex. N의 최대 범위가 1000000인 경우int a[1000000];
- 메모리제한
메모리 제한이 512MB 인 경우,int a[128000000];을 선언할 수 있다.
