[면접대비] 공간 복잡도(Space complexity)

공간 복잡도

알고리즘이 얼마나 많은 메모리를 소모하는가.

메모리 소모와 빅 오 표기법

• newArray 등 새로운 배열을 원소 N개에 따라 생성하는 경우: O(N)
• 새로운 배열을 생성하지 기존 배열의 원소를 바꾸는 경우: O(1)
• 추가로 소모한 공간은 보조 공간(auxiliary space)라 부른다.
• 입력도 포함하여 공간 복잡도를 계산하는 경우도 있다. 이 경우도 틀린 경우는 아니다.

시간 복잡도와 공간 복잡도의 선택

• 애플리케이션이 매우 빠르고, 처리할 메모리가 충분하다면 시간복잡도가 낮은 경우가 적절하다.
• 속도는 크게 중요하지 않지만 메모리를 절약해야 하는 경우 공간복잡도가 낮은 경우가 적절하다.
• 근본적으로는 최소 허용 속도와 메모리 한도를 아는 것이 좋다.

재귀함수와 공간 복잡도: O(N)

재귀함수를 호출하는 경우 호출 스택에 항목을 추가한다.

가장 마지막 재귀함수가 실행될 때까지 모든 호출이 쌓이는 것이다.

따라서 재귀 함수는 재귀 호출 횟수만큼 단위 공간을 차지한다.

루프, 퀵 정렬과 공간 복잡도

루프로 동일한 동작을 한다면 메모리를 추가로 차지하지 않는다.

퀵 정렬은 O(logN) 번의 재귀 호출을 수행하므로 최고점에서 호출 스택 크기가 log(N)이다.