알고리즘 계산 복잡도는 두가지로 나뉘어짐
- 시간 복잡도
- 공간 복잡도
둘다 만족시키기는 어려움
- 시간과 공간은 반비례적 경향
- 대용량 시스템 보편화로 시간 복잡도가 우선
공간 복잡도
프로그램 실행/완료 시 필요한 저장 공간
총 필요 저장 공간
- 고정 공간 (알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수
- 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
- 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛) / c: 고정 공간, 𝑆𝑝(𝑛) : 가변 공간
- 공간 복잡도는 가변 공간에 좌우됨
공간 복잡도 계산
공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨
예제 1
n! 구하기
- n! = 1 * 2 * 3 * ... * n
- 공간 복잡도는 O(n) / 실행시 사용되는 저장공간을 계산하면 됨
// 변수 n, 변수 fac, 변수 index만 필요함
// O(1)
public class Factorial {
public int factorialFunc(int n) {
int fac = 1;
for (int index = 2; index < n + 1; index++) {
fac = fac * index;
}
return fac;
}
}
// n ➡️ 1까지 스택에 쌓이게 됨
// O(n)
public class Factorial {
public int factorialFunc(int n) {
if (n > 1) {
return n * factorialFunc(n - 1);
} else {
return 1;
}
}
}
feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스
'코테 > 알고리즘' 카테고리의 다른 글
삽입 정렬 (0) | 2023.08.29 |
---|---|
선택 정렬 (0) | 2023.08.29 |
버블 정렬 (0) | 2023.08.29 |
알고리즘 시간 복잡도 (Time Complexity) (0) | 2023.08.11 |
최대공약수 - 유클리드 알고리즘 (유클리드 호제법) (0) | 2023.01.01 |