Analysis of Algorithms | Space Complexity

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

보통 알고리즘 문제를 해결할 때 시간복잡도는 항상 고려하지만 공간복잡도는 미처 생각하지 못하는 경우가 발생한다. 그러나 몇몇 알고리즘 문제를 해결할 땐 문제를 해결하기 위해 끌어다 사용하는 공간자원에 대한 제한사항을 명시하는 경우도 있기 때문에 어느 정도는 염두에 둘 필요가 있다.

하지만 이번에 정리하고자 하는 게시글에서는 이 용어가 자주 오용된다는 사실을 언급한다. 엄밀하게 따지면 우리가 흔히 '공간복잡도(Space complexity)'는 좀 더 포괄적인 개념이고 문제 해결을 위해 잠시 끌어다 쓰는 공간은 '보조 공간(Auxiliary Space)'이 맞는 표현이라는 것이다.

보조 공간(Auxiliary Space)

보조 공간(Auxiliary Space)는 input size를 고려하여 알고리즘이 문제를 해결하기 위해 임시로 사용하는 공간을 의미한다. 즉, 임시로 사용하는 공간이기 때문에 input의 size를 포함하지 않고 문제 해결을 위해 중간에 사용하는 버퍼 공간을 말한다.

공간 복잡도(Space Complexity)

그렇다면 공간 복잡도(Space Complexity)는 무엇인가. 엄밀한 정의는 input size를 고려하여 알고리즘이 문제를 해결하기 위해 사용하는 모든 공간을 의미한다. 즉, 공간 복잡도(Space Complexity)는 보조 공간(Auxiliary Space)와는 다르게 'input size'를 포함한다. 그럼로 좀 더 포괄적인 개념이다.

사용할 용어 채택 시 문제점?

문제 해결을 위해 제한된 공간만 사용할 것을 요구받았다고 생각해보자. 예를 들어 크기가 n인 배열의 곱연산이라 하자. 그리고 크기가 N인 공간 내에서 해결할 것을 요구받았다. 한발짝 물러서서 보면 문제 해결을 위해 input size보다 작은 공간을 사용하라고 요구할 리는 없기 때문에 당연히 포괄적으로 공간복잡도의 개념을 사용해도 무방하기는 하다. 단순히 문제를 해결하기 위해 크기가 N인 배열끼리의 곱연산을 한꺼번에 메모리에 올려 진행하려 하면 제한에 걸리므로 불가능하기 때문이다. 그러므로 제약사항에 걸리지 않게끔 분할하여 연산하는 코드를 작성해야 한다.

굳이 두 개념을 나눠서 정리한 이유는 용어의 정의를 정확하게 파악하고 포괄적으로 사용하는 것과 오류가 크게 발생하지 않기 때문에 적당히 사용하는 것과는 차이가 있기 때문이다. 앞으로 용어를 사용함에 있어 문제가 있진 않겠지만 가볍게 짚고 넘어가도 좋다고 생각한다.

참고자료

1. What does ‘Space Complexity’ mean?