[Algorithm] 시간복잡도 vs 공간복잡도

시간복잡도는 어떤 명령 x를 수행하는데 걸리는 시간을 말한다.

공간복잡도는 어떤 명령 x를 수행하는데 필요한 메모리의 크기를 말한다.

 

가장 이상적인 프로그램은 시간복잡도와 공간복잡도가 모두 낮은 것이지만,

시간복잡도와 공간복잡도는 반비례

라는 글을 보면 제목 그대로 일반적으로 시간복잡도와 공간복잡도는 반비례 관계임을 알 수 있다

 

그러므로 두개의 가치중 한가지를 일부 포기해야만 하는(trade-off) 상황이 항상 생기는데

결론적으로 얘기하자면 우리는 시간복잡도를 우선으로 생각해야만 한다.

 

예를 들어 어떤 프로그램을 짜고보니 이 녀석이 명령x를 수행하는데 10일이라는 시간이 걸리지만

메모리의 여유가 있는 상태이며, 메모리를 더 많이 쓴다면 시간을 10일에서 1일까지 줄일 수 있다고 가정해보자

 

시간은 돈을 주고도 살 수 없지만 메모리는 부족하면 돈 주고 사서 추가로 달면 된다

메모리는 돈으로 살 수 있는 가치이다.

 

또한 현대의 하드웨어는 성능이 너무 괴악하여 일반 개발자들은 평소 메모리의 부족을 느낄 일이

사실상 없다고 봐도 무방하다.

 

일반적으로 개발자들이 사용하는 개발용 노트북의 경우 작게는 8GB부터 많게는 32GB까지의 RAM을 사용하는데 이게 얼마나 큰 메모리인지 계산해보자면

 

int[] ints = new int[10000][10000];

 

Java에서 정수형은 4byte의 크기를 갖는다.

위 배열의 크기를 계산해보면

 

10,000 x 10,000 x 4 = 400,000,000 Byte

 

1024 Byte = 1 KB

1024 KB = 1 MB

 

이므로,

 

400,000,000 Byte = 약 400 MB

 

우리가 사실상 사용할 일 없는 비현실적인 배열의 크기에 비해

정말 별 볼일 없는 메모리 크기가 나옴을 알 수 있다.

 

그러니 항상 메모리보다는 수행 시간을 중요하게 여기자.