[이론] 공간복잡도 (feat. 코드트리 조별과제 : 1주차)

 

공간복잡도란?

메모리 사용량 (코드가 메모리에서 얼마나 차지하고 있는가?)

공간복잡도가 왜 중요한가?

• 컴퓨터의 메모리는 한정되어 있으므로 사용되는 메모리가 적을수록 효율이 좋음.
• 메모리 사용을 미리 계산해보면 메모리 제한을 넘는 코드인지 확인 가능함.

 

공간복잡도 계산

메모리 계산 기준

- 메모리 계산 기준은 보통 C++ 기준

자료형	크기
int	4byte
char	1byte
double	8byte
short	2byte

 

계산 방법

• 값이 생성 후 없어지는 경우도 있음
  • 특정 시점에 메모리를 차지하고 있는 값들이 가장 많은 경우를 고려함
  •  

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

-- 공간복잡도 계산 예시 

1. char a[2천만]
-> char 타입의 크기는 1byte, 2천만의 배열을 만들면 2천만 byte = 20MB

2. docuble a[2천만]
-> double 타입의 크기는 8byte, 2천만의 배열을 만들면 1억 6천만 byte = 160MB

3. int a[1억]
-> int 타입의 크기는 4byte, 1억의 배열을 만들면 400MB

 

- 출처

공간복잡도의 쓰임(코드트리 문제)

진행 커리큘럼 : 자료구조,알고리즘(Lv.NH)