알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있다.

• 시간 복잡도: 얼마나 빠르게 실행되는지
• 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘

• 통상 둘 다를 만족시키기는 어려움이 있다.
  • 시간과 공간은 반비례적 경향이 있다.
  • 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선이 되었다.
  • 그래서! 알고리즘은 시간 복잡도가 중심

공간 복잡도 대략적인 계산이 필요하다.

• 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많다.
• 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있다.
• 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도 있다.

Complexity:

• expected worst-case time complexity: O(N)
• expected worst-case space complexity: O(N)

현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있다.

1. 공간 복잡도 (Space Complexity)

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
• 총 필요 저장 공간
  • 고정 공간 (Fixed Space) (알고리즘과 무관한 공간): 알고리즘이 실행되는 동안 고정적으로 필요한 공간이다. 코드 저장 공간, 단순 변수 및 상수가 이에 해당한다.
  • 가변 공간 (Variable Space) (알고리즘 실행과 관련있는 공간): 알고리즘이 실행되는 동안 동적으로 필요한 공간으로, 동적 배열이나 재귀 스택 등이 해당된다.
  • $S(P) = c + S_p(n)$
    • c: 고정 공간
    • $S_p(n)$: 가변 공간

빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우된다.

공간 복잡도를 표현할 때는 대체로 가장 큰 영향을 미치는 부분만을 고려한다. 예를 들어, 입력 크기 n에 대해 O(n)의 공간이 필요한 알고리즘이라면, 이 알고리즘의 공간 복잡도는 O(n)으로 표현된다.

주의할 점은, 시간 복잡도와 공간 복잡도는 트레이드오프 관계에 있다. 즉, 알고리즘이 더 빠르게 동작하게 하려면 더 많은 메모리를 사용해야 하고, 반대로 메모리 사용량을 줄이려면 실행 시간이 늘어날 수 있다는 것이다. 이러한 트레이드오프를 고려하여 알고리즘을 설계하는 것은 중요한 과제다.

2. 공간 복잡도 계산

• 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.
  • 이를 빅 오 표기법으로 표현할 수 있으면 된다.

공간 복잡도 예제1

• n! 팩토리얼 구하기
  • n! = 1 x 2 x ... x n
• n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
• 공간 복잡도는 O(1)

공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 됨

def factorial(n):
    fac = 1
    for index in range(2, n + 1):
        fac = fac * index
    return fac

factorial(3) # 6

이 함수는 주어진 정수 n의 팩토리얼을 계산한다. 팩토리얼은 주어진 수에서 1까지의 모든 정수를 곱한 값이다.
n! = n * (n-1) * (n-2) * ... * 1

공간 복잡도 관점에서 보면, 이 함수는 n, fac, index라는 세 개의 변수만을 사용한다. 이 세 변수는 입력 n의 크기와 무관하게 일정한 공간만을 차지하므로, 이 함수의 공간 복잡도는 O(1)이다. O(1) 복잡도는 알고리즘이 실행되는 동안 일정한 저장 공간을 사용한다는 것을 의미한다.

즉, 이 알고리즘은 입력값의 크기에 관계없이 일정한 양의 메모리만을 사용하므로 공간 효율성이 매우 높다고 볼 수 있다.

공간 복잡도 예제2

• 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
  • factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
• 공간 복잡도는 O(n)

def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1

이 함수는 주어진 정수 n의 팩토리얼을 재귀적으로 계산한다. 이는 주어진 수에서 1까지의 모든 정수를 곱한 값이다.
n! = n * (n-1) * (n-2) * ... * 1

재귀 함수는 함수가 자신을 다시 호출하는 방식으로 작동하는데, 이 경우에는 factorial(n - 1)의 형태로 자신을 다시 호출하고 있다. 이렇게 재귀 함수를 사용하면, 각 재귀 호출마다 메모리 스택에 새로운 함수 호출이 쌓이게 된다. 따라서 이 함수는 n에 비례하는 메모리를 사용하게 된다.

공간 복잡도 관점에서 보면, 이 함수는 입력 크기 n에 비례하여 변수 n이 n개가 생성되므로, 이 함수의 공간 복잡도는 O(n)이다. O(n) 복잡도는 알고리즘이 실행되는 동안 입력 크기에 비례하는 저장 공간을 사용한다는 것을 의미한다.

즉, 이 함수는 입력 크기가 커질수록 메모리 사용량도 선형적으로 증가하므로 공간 효율성이 낮다. 이는 재귀 함수의 한계로, 과도한 메모리 사용을 초래할 수 있다. 이러한 이유로 재귀 함수의 사용은 신중하게 고려되어야 한다.