[코드트리] 공간복잡도

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

프로그램의 소요시간 뿐만 아니라, 컴퓨터의 메모리가 한정되어 있으므로 공간복잡도도 중요합니다.

공간복잡도도 시간복잡도와 동일하게 점근적 표기법을 사용합니다.

function example(n)
  set arr = [n][n]
  for i = 0 ... i < n
    for j = 0 ... j < n
      arr[i][j] = 1

 

공간복잡도 = '이 코드가 메모리를 얼마나 차지하고 있을까?'

위 코드에서 set arr = [n][n] 이외의 다른 코드는 메모리를 차지하고 있지 않기 때문에,

공간복잡도는 O(N^2) 입니다.

 

그렇다면 공간복잡도는 왜 필요할까요?
문제에서 메모리 제한이 80MB라는 식으로 주어지는 경우가 있습니다.

보통 메모리를 계산하는 경우에는 C++을 기준으로 생각합니다.

 

(C++ 기준)  int = 4 byte, char = 1 byte, double = 8 byte

 

따라서, int로 2천만이 대략 80MB라는 것을 이용하여 다음과 같이 쉽게 계산이 가능합니다.

int a[2천만] : 80MB
int a[2백만] : 80 / 10 = 8MB
char a[2천만] : 80 / 4 = 20MB
double a[2천만] : 80 * 2 = 160MB

 

따라서 사용하는 배열의 크기에 따라 대략 어느 정도의 메모리를 사용하는지를 계산할 수 있습니다.

---

공간복잡도를 추론할 때 중요한 점은, 값이 생성되었다가 없어질 수 있다는 점에 있습니다.

만약에 함수 내 정의한 값이 함수가 종료되어 사라졌다면

메모리를 차지 하고 있는 값들이 가장 많을 때, 그 시점에서의 메모리 사용량을 계산에 고려해야 합니다.

 

function solution(n)
  set list = [n][n]       // (1)
  for i = 0 ... i < n
    list[i][i] = n
  for i = 0 ... i < n
    set tmp = [n-1][n-1]     // (2)
    for j = 0 ... j < n-1
      tmp[j][0] = list[0][j]

 

위 코드에서는 배열 선언을 하는 두 부분만 공간복잡도에 영향을 미칩니다.

(1)과 (2)에서 선언되는 배열이 동시에 존재할 때, 메모리를 가장 많이 차지하게 되며 그 최댓값이 이 코드의 공간복잡도이므로,

(N^2) + (N^2) = 2(N^2)  =>  O(N^2)

 

시간복잡도와 동일하게 상수값 및 낮은 차수들은 무시됩니다.

 

 

 

출처 코드트리