알고리즘 복잡도 - 공간 복잡도

시간 복잡도는 얼마나 빠르게 실행 되는지를 나타내는 척도라면,

공간 복잡도는 얼마나 많은 저장 공간이 필요한지를 나타내는 척도다.

 

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이겠지만 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선된다. 따라서 알고리즘은 시간 복잡도가 중심이다.

 

또한 현업에서 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있다.

 

공간 복잡도란?

프로그램을 실행 및 완료하는데 필요한 저장 공간의 양을 의미(=입력의 크기와 문제를 해결하는데 걸리는 공간의 상관관계)

 

공간 복잡도라는 개념보다는, 512MB가 int 변수를 대략 1.2억개 정도 담을 수 있다는 개념을 가지고 문제에 임하는 것이 좋음

 

고정 공간(알고리즘과 상관없이 코드 저장, 단순 변수 및 상수) + 가변 공간(알고리즘 실행과 관련있는 공간, 실행 중 동적으로 필요한 공간)

Big O의 관점에서, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.