공간복잡도

시간복잡도에 비해 소홀해지기 쉬운데, 공간복잡도 또한 최적화하면 좋으므로 알아두도록 하겠습니다.

메모리 계산은 보통 C++ 기준으로 생각하는데, 아래 테이블은 자바의 데이터 타입별 메모리 사용 크기이므로 참고하면 좋을 것 같습니다.

출처 : https://eatnows.tistory.com/54

C++의 int는 4byte이며, int로 20,000,000(2천만) 정도가 대략 80MB라는 것을 기준으로 계산하면 편합니다. 마치 시간복잡도 중에서 N이 1억번에 1초로 기준을 잡는 것과 동일합니다.

public static final int N = 20,000,000;

int[] a = new int[N]; // 80 MB
int[] a = new int[N/10]; // 80 / 10 = 8 MB
char[] a = new char[N]; // 80 / 2 = 40 MB
double[] a = new double[N]; // 80 * 2 = 160 MB

 

이러한 방식을 바탕으로 공간복잡도를 계산할 수 있습니다.

 

한번 빅오 표기법으로 계산해봅시다.

def solution(n):
	list = int[n][n][n]
    for i in range(0, n):
    	tmp = int[n]
        for j in range(0, n):
        	tmp[j] = list[0][i][j]

위 함수에서는 공간복잡도를 빅오표기법으로 계산하면 O(N^3)가 됩니다.