[알고리즘] 공간 복잡도 'Space Complexity'

빅오 표기법 : 공간 복잡도 (Space Complexity)

공간 복잡도

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

 

1. 시간 복잡도 : 얼마나 빠르게 실행되는지

2. 공간 복잡도 : 얼마나 많은 저장 공간이 필요하는지

 

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

 

- 통상 둘 다 만족시키기는 어렵다.

: 시간과 공간은 반비례적인 경향이 있음

: 최근 대용량 시스템이 보편화되면서 공간복잡도 보다는 시간복잡도가 우선이 되었다.

: 그래서 알고리즘은 "시간 복잡도" 가 중심이다.

 

공간 복잡도의 대략적인 계산이 필요함

- 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많다.

- 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있다.

- 또한, 기존 알고리즘 문제에 영향을 받아서 면접시에도 공간 복잡도를 묻는 경우도 있다.

 

Complexity:

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

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

 

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

 

1. 공간 복잡도 (Space Complexity)

- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함

- 총 필요 저장 공간

• 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 (문제의 인스턴스(입출력 크기)에 무관, 일정한 양의 메모리 공간)
• 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간 (문제의 인스탄스에 따라 가변저긴 메모리 공간)
• S(P) = c + Sp(n) => c: 고정 공간 / Sp(n) : 가변공간

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

 

2. 공간 복잡도 계산

- 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.

: 이를 빅오 표기법으로 표현할 수 있으면 된다.

 

공간 복잡도 예제 ①

- n! 팩토리얼 구하기

: n! = 1 x 2 x ... x n

- 구현 : 반복문

- n의 값에 상관없이 변수n, 변수 fac, 변수 index만 필요하다.

- 공간복잡도는 O(1)이다.

 

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

 

[Python]

 

def factorial(n):
    fac = 1
    for index in range(2, n+1):
        fac = fac * index
    return fac
 
factorial(3) # 결과 6

 

 

공간 복잡도 예제 ②

- n! 팩토리얼 구하기

: n! = 1 x 2 x ... x n

- 구현 : 재귀함수

- 재귀함수를 사용하였으므로, n에 따라 변수 n이 n개를 만들어지게 된다.

: factorial 함수를 재귀함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 된다.

- 공간 복잡도는 O(n)

 

[Python]

 

def factorial(n):
    if n > 1:
        return n * factorical(n-1)
    else:
        return 1
 
factorial(3) # 결과 6