시간복잡도와 공간복잡도

 

 

 

시간 복잡도는 코드의 실행 시간을 의미하고, 공간복잡도는 코드가 메모리를 얼마나 잡아먹는지를 의미한다.

 

배열에서 특정 원소에 접근할 때는 인덱스를 기반으로 한 번에 찾아갈 수 있지만, LinkedList에서 특정 원소에 접근하려하면 처음이나 끝에서부터 시작해서 특정 원소의 위치까지 접근해야 한다. 

 

이 때 배열은 원소의 접근에 있어서 시간복잡도가 낮고, 링크드리스트는 접근에 있어서 시간복잡도가 높다고 할 수 있다.

 

C언어에서 int타입은 4바이트, char타입은 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이 크든 작든 메모리에서 사용하는 공간은 변수 두 개 밖에 없다.

공간복잡도는 O(1)이다.

 

public class Factorial {
    public int factorialFunc(int n) {
        if (n > 1) {
            return n * factorialFunc(n - 1);
        } else {
            return 1;
        }
    }
}

 

반면에 팩토리얼을 재귀로 구현하면, n에 따라서 메모리에서 사용하는 공간이 늘어난다.

공간복잡도는 O(n)이다.