- 입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양
- 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다.
- 배열, 맵, 셋, … → 요소들을 담을 공간이면 다 적용된다.
- 재귀함수도 메모리를 먹지만, 계산하기에 무리가 있으므로 보통 사용되는 자료구조에 대해서만 계산한다.
- N개 int형의 입력 =
4N바이트의 공간 필요 (int 4바이트) → O(n)
- 공간복잡도는 빅오표기법으로 잘 사용하지 않는다.
배열의 범위 잡는 법
- 문제를 풀때는 공간복잡도 개념을 잘 사용하지 않는다.
- 최대 범위
- 문제에서 N의 최대범위가 1000000 →
int a[1000000];
- 주로 입력 받을때 사용하는 방법
- 메모리 제한
- 문제의 메모리 제한이 512MB → 512,000,000 바이트 / 4 바이트 →
int a[128000000];
- 동작은 하지만 실전에서 ‘1000만 까지는 어느정도는 된다’ 라고 잡는게 좋다.
- 문제에서 입력 보단 문제의 로직에 필요한 공간에서 1000만을 상한선의 기준으로 잡을만 하다. (문제에 따라 다르다)
- 예를 들어, 동적 배열에서 특정 요소를 log n 에 탐색하는 로직이 필요할 때, 1000만 짜리 배열이 필요하다면 새로이 배열을 만드는 펜윅 알고리즘보다 이분탐색 알고리즘을 먼저 고려해볼 만 하다.
