[자료구조] 11 알고리즘의 성능 평가 : 공간 복잡도 (Space Complexity)

📌 Performance Evaluation 

설계한 프로그램이 구현되면 성능 평가가 필요

 

✔️프로그램이 requirement 만족하는가

✔️오류 없이 올바르게 동작하는가 

✔️효율적으로 구현 되었는가 

 

 

📌 성능 분석 기준 

👉 공간 복잡도 (space complexity)

프로그램이 수행을 완료하는데 필요로 하는 메모리의 양 (memory space)

👉 시간 복잡도 (time complexity)

프로그램이 수행을 완료하는데 걸리는 시간 (computation time)

 

 

✔️공간복잡도 (space complexity)

알고리즘 실행에 필요한 메모리 공간의 양 

 

요구하는 시점에 따라 2가지 공간으로 나뉜다

 

 

👉 고정 메모리 공간 (fixed memory space) 

프로그램이 실행되기 전 결정되는 요소 

ex) 프로그램 명령어, 고정 크기 변수, 상수 등을 저장하는데 필요한 기억공간

float cal(int a, int b, int c, int d){
	return ( a * b + c * d ) - ( c * b + a * d );
}

단일 변수들 a,b,c,d 가 고정되어 있어 고정 메모리 공간을 필요로 한다

 

 

👉 가변 메모리 공간 (variable memory space)

프로그램 실행 중에 요구되는 요소

ex) 배열 전달 (array passing), 재귀 호출 (recursion)

실행 중에 요구하는 메모리 공간은 양이 가변적이고 예측이 어려움 ==> 공간 복잡도 평가에서 중요한 항목

int factorial(int n){
	if (n>0){
    	return n * factorial(n-1);
    }
    return 1;
}

factorial 재귀 함수를 호출, 매개 변수, 지역 변수, 회귀 주소를 저장해야 한다 

❓회귀주소란

return address : 함수가 호출된 명령어의 다음 위치 

 

➿ 계산 => 1회 호출 시 매개 변수 n을 위한 4byte 와 회귀 주소를 위한 4byte 각각 저장 필요 

총 n번 호출되므로 (4+4) * n = 8n byte의 가변 메모리 공간이 필요하다 

 

 

💫 기억하자 💫 

즉 고정 메모리 공간은 고정 되어 있는 변수나 상수들을 위한 메모리 공간이고 

가변 메모리 공간은 매개 변수나 지역변수, 그리고 함수가 호출될 경우 그 명령어 위치인 회귀 주소를 말한다!