공간 복잡도

알고리즘 계산 복잡도는 두가지로 나뉘어짐

• 시간 복잡도
• 공간 복잡도

둘다 만족시키기는 어려움

• 시간과 공간은 반비례적 경향
• 대용량 시스템 보편화로 시간 복잡도가 우선

 

공간 복잡도

프로그램 실행/완료 시 필요한 저장 공간

 

총 필요 저장 공간

• 고정 공간 (알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수
• 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
• 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛) / 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편 - 패스트캠퍼스