공간복잡도

알고리즘의 공간복잡도를 계산하는 방법에 대해서 알아보자. 

입력크기 N에 비례하여 알고리즘 실행을 완료하는데 필요한 총 메모리 공간의 양을 나타냅니다.

시간복잡도와 마찬가지로, 가장 큰 영향을 미치는 항을 기준으로 점근적 표기법을 사용하여 표현 합니다. 

 

공간복잡도는 크게 고정공간과 가변 공간으로 구성된다. 알고리즘 분석 시 주로 가변 공간에 초점을 맞춰서 계산하면 됩니다. 

 

• 고정 공간(Fixed Part) : 입력 크기에 관계 없이 항상 일정하게 필요한 공간 (코드 저장공간, 변수/상수 저장공간)
      보통 O(1)로 취급되어 무시된다. 
• 가변 공간(Variable Part) : 입력 크기나 함수 호출 횟수 등 알고리즘의 실행 상황에 따라 달라지는 공간 (배열, 리스트, 맵 등)

 

🧠  1.  알고리즘 메모리 제한 해석

[C언어] (1바이트 = 8비트)

자료형	용도	일반적인 크기(바이트)	비트 수	표현 범위
int	정수	4 바이트	32(8*4)비트	(약) -2* 10^9 ~ 2 * 10^9
double	실수	8 바이트	64(8*8)비트	+- 1.7 * 10^308

 

 

[JavaScript/TypeScript]

int,double을 구분하지 않고 double(=number)만 있다고 생각하면 된다

자료형	용도	일반적인 크기(바이트)	비트 수
number	정수,실수	8 바이트	64(8*8)비트

 

[메모리 크키]

단위	변환(비고)
비트(bit)	0과 1로 구성되어 있다.
바이트(Byte)	1B = 8비트
킬로바이트(KB)	1KB = 1,024바이트
메가바이트(MB)	1MB = 1,024KB
기가바이트(GB)	1GB = 1,024MB
테라바이트(TB)	1TB = 1,024GB