[코드트리] 공간복잡도

공간 복잡도는 코드가 차지하는 메모리를 나타낸다

set arr = [n][n];이면 O(N^2)
이렇게 할당을 해주는 부분이 메모리를 차지하니까 이걸로 공간 복잡도를 판단

문제링크

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

set list = [n][n]에서 공간 복잡도가 O(N^2)인 것을 알게 됨
또 set tmp = [n - 1][n - 1]에서의 공간 복잡도를 구하여
두개의 합이 전체 함수의 공간 복잡도를 나타냄

for문이 돌면서 n번 tmp가 생성되었다가 사라지기 때문에
O(n * n^2)이라고 생각했는데
-> for문이 돌때마다 tmp가 생성되었다가 사라지기 때문에
전체적으로 O(N^2)의 공간 복잡도만 차지

전체 함수의 공간복잡도는 O(N^2) + O(N^2)가 되어서
O(N^2) 이다.

보통 메모리를 계산하는 경우에는 C++을 기준으로 생각합니다. C++ 에서는 int가 4 byte, char이 1 byte, double이 8 byte, short가 2 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