[19장] 공간 제약 다루기

여지껏 알고리즘 효율성 분석에서 알고리즘이 얼마나 '빠른가', 즉 시간 복잡도에만 초점을 맞춰왔다. 그러나 알고리즘이 얼마나 많은 메모리를 소모하는지도 효율성의 척도가 되는데, 이를 공간 복잡도(space complexity)라 부른다. 메모리는 무한하지 않으며, 대량의 데이터를 다루거나 메모리가 제한된 작은 장치를 프로그래밍할 때는 공간 복잡도가 매우 중요해진다.

 

이상적으로는 빠르고 메모리 효율적인 알고리즘이 최고지만, 둘 다 만족시킬 수 없는 상황이 즐비하기때문에 메모리와 속도 사이에서 우선순위를 매기는 능력 또한 중요하다.

 

1. 공간 복잡도의 빅 오

시간 복잡도와 마찬가지로 공간 복잡도 또한 빅 오 표기법을 사용한다. 애초에 빅 오란 "핵심 질문"에 대한 답을 표현하는 수단이다. 즉, 시간 복잡도에선 "데이터 원소가 N개일 때 필요한 알고리즘 단계 수"에 대한 답으로써 빅 오를 쓴 것일 뿐이다.

 

공간 복잡도에서 빅 오는 "데이터 원소 N개를 처리하는데 '추가로' 소모하는 공간이 얼마인지"에 대한 답이다. 예를 들어, 아래 코드에서 1번 함수는 array와 동일한 크기의 배열을 추가로 하나 만들어 반환한다. 반면 2번 함수는 추가로 소모하는 공간이 없다. ( 추가로 소모하는 공간을 보조 공간(auxiliary space)라고 부른다 )

정리하면, 아래 표처럼 되는데 2번 함수가 좀 더 메모리 효율적이다. 시간 복잡도가 같고 공간 복잡도에서 우위에 있으니 2번 함수가 더 좋다고 할 수 있다. 단, 원본 배열을 변형시키므로 주의해야 한다.

	시간 복잡도	공간 복잡도
1번 함수	O(N)	O(N)
2번 함수	O(N)	O(1)

 

2. 재귀에 숨겨진 비용

결론부터 말하면 재귀는 재귀 호출 횟수만큼 단위 공간을 차지한다. 예를 들어, 아래 recurse함수를 20,000번 실행하기 위해선 스택에 recurse를 20,001개를 추가해야한다. 그깟 20000개쯤 컴퓨터가 못할 게 뭐 있겠는가? ㅇㅇ 못함.

위 함수를 실제로 돌려보면 20,000부터 8,847까지만 출력하고 스택이 꽉 차서 실행이 종료된다(물론 컴퓨터마다 다를 수있다) 재귀는 마법 같은 하향식 사고방식을 적용할 순 있으나, 대용량 데이터나 큰 수를 처리할 때면 적절치 않을 수 있다. 

 

재귀 자체가 나쁘다는게 아니다. 그저 상황에 따라 각 알고리즘의 장단점을 골고루 저울질해야 한다는 뜻이다.