직접 구현하지 않고도 알고리즘의 효율성을 따져볼 수 있는 "알고리즘 복잡도 분석" 방법에는 2가지의 측면을 고려할 수 있습니다. 바로 "알고리즘의 수행시간"과 "알고리즘이 필요로 하는 기억공간의 양"입니다. 알고리즘의 수행시간을 고려하는 분석을 "시간 복잡도"라고 하며, 기억공간의 양을 고려하는 분석은 "공간 복잡도"라고 합니다.
이번 포스팅에서는 알고리즘이 필요로 하는 기억공간의 양을 다루는 "공간 복잡도"에 대해서 포스팅해보도록 하겠습니다.
공간 복잡도(Space Complexity)
공간 복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 의미합니다. 즉, 알고리즘이 필요로 하는 "메모리의 양"을 의미합니다.
코딩테스트 문제들에 주로 보이는 "제한 시간 1초, 메모리 제한 128MB" 등의 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위하여 명시하는 것입니다. 코딩테스트 문제의 많은 경우에서는 공간 복잡도 보다는 시간 복잡도로 인해 틀리게 되기에 공간 복잡도에 대해서는 너무 크게 신경 쓰지 않으셔도 됩니다.
공간 복잡도의 표기법
공간 복잡도는 "총 공간 요구 = 고정 공간 요구 + 가변 공간 요구"로 나타낼 수 있습니다.
수식으로는 \( S(P) = c + Sp(n) \)으로 표현합니다.
위에서 말하는 "고정 공간"은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구를 말합니다. 즉, 코드 저장 공간이나 단순 변수 그리고 고정 크기의 구조 변수, 상수를 뜻한다. "가변 공간"은 동적으로 필요한 공간의 요구를 말합니다. 예를 들어, 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간 등이 있습니다.
공간 복잡도 또한 시간 복잡도와 마찬가지로 "빅오 표기법"을 사용해서 표현할 수 있습니다. 빅오 표기법 자체가 알고리즘의 성능을 수학적으로 표현하는 방식이기에 시간 복잡도에도, 공간 복잡도에도 사용이 가능합니다.
두 개의 함수 \(f(x)\)와 \(g(n)\)이 주어졌을 때 모든 \(n > n_0\)에 대하여 \( |f(n)| \leqq c|g(n)| \)을 만족하는 2개의 상수 \(c\)와 \(n_0\)가 존재하면 \(f(n) = O(g(n))\)이다.
크기가 n짜리의 1차원이 배열을 만든다면, 그때는 우리에게는 \( O(n) \)의 공간이 필요하고, 크기가 n짜리의 2차원 배열을 만든다면 그때는 \( O(n^2) \)의 공간이 필요하고, 배열이 따로 필요하지 않다면 \( O(1) \)의 공간이 필요합니다.
사실 공간 복잡도는 시간 복잡도에 비하면 중요도가 조금 떨어집니다. 그렇지만 알고리즘을 설계할 때, 메모리에 대해 생각하는 것 또한 중요합니다. 앞으로 다른 자료구조-알고리즘 포스팅을 보시게 된다면 별 다른 언급이 없다면 그때 쓰이는 "복잡도"라는 말은 대부분 "시간 복잡도"를 의미하는 것입니다.
