공간복잡도(Space Complexity)란?

공간복잡도(Space Complexity)란?

---

공간복잡도(Space Complexity)

 - 알고리즘을 수행할 때 필요한 메모리의 총량

 - Space Complexity = Auxiliary Space + Input Size Space

 - Auxiliary Space는 알고리즘을 실행하면서 필요한 임시변수 등을 의미

 - Input Size는 알고리즘에 전달되는 파라미터 값이나 문제해결을 하는데 사용되는 변수를 의미

 

프로그램의 메모리 사용

 - 프로그램의 명령어들

   => 컴파일러에 의해 컴파일된 명령어 mov, sub, ...

 

 - 환경적인 부분

   => A함수에서 B함수를 호출하면 A함수의 다음 위치 및 A함수에서 사용된 변수값들을 스택에 PUSH하고 B함수가 종료되면 A함수의 변수값들을 다시 POP해서 원래 내용대로 돌아오는 행위들

 

 - 데이터 공간

   => 변수 또는 상수의 메모리 양

 

알고리즘에서 공간복잡도를 구할때 보통 데이터 공간을 이용하여 계산함

 

예시)

int sum(int a, int b){
	return a + b;
}

위 예시에서 공간복잡도는 파라미터 a(4byte), 파라미터 b(4byte), return값(4byte)해서 총 12byte이며 빅-오를 이용하여 공간복잡도를 구하면 O(1)이 된다. 

 

int sum(int arr[], int b){
	int sum = 0;
	for(int i=0; i<b; i++){
    	sum += arr[i];
    }
    
    return sum;
}

위 예시에서 공간복잡도는 파라미터 arr배열(4 * n), 파라미터 b(4byte), 지역변수 sum(4byte), 지역변수 i(4byte), return값(4byte)해서 총 4n + 16이며 빅-오를 이용하여 공간복잡도를 구하면 O(n)이 된다.

 

 

[참고사이트]

1. www.studytonight.com/data-structures/space-complexity-of-algorithms

2. hoseockchoi.wordpress.com/2019/04/05/time-complexity-%EC%99%80-space-complexity-%EC%97%90-%EB%8C%80%ED%95%9C-%EC%9D%B4%ED%95%B4-%EA%B7%B8%EB%A6%AC%EA%B3%A0-code-review-%EA%B4%80%EC%A0%90%EC%97%90%EC%84%9C-%EB%8B%A4%EC%8B%9C-%EB%B3%B4/