[매일메일] 시간 복잡도와 공간 복잡도의 차이점은 무엇인가요?

어떤 문제 푸는데 여러 방법이 존재한다.

그럼 우리는 어떤 기준으로 어떤 알고리즘을 사용할 지에 대해서 정해야 한다. 

빠르다가 기준이라면 시간 복잡도를 계산할 것이고, 공간을 너무 많이 차지하면 안된다면 공간 복잡도를 생각할 것이다.

 

이때 시간을 실제로 측정한다면, time등의 라이브러리 등으로 측정 가능할테지만 운영체제나 실제 알고리즘의 문제 뿐 아닌 기타 환경 등의 문제로도 다른 값이 나올 것이다. 그렇다면 어떻게 측정하는 것이 옳을 것인가?

 

우리는 이에 시간 복잡도라는 것을 사용한다.

시간 복잡도란, 직접 속도를 측정하는 것이 아닌 컴퓨터가 처리해야 하는 연산의 수는 것이 나은 방법일 수 있다는 점에서 시작된 아이디어이다.

특정 입력을 기준으로 연산의 수를 계산한 것이 시간 복잡도이다.

 

반면 공간 복잡도의 경우, 특정 입력을 기준으로 알고리즘이 얼마나 많은 공간을 차지 하는 지를 나타냄

 

시간 복잡도와 공간 복잡도 모두 알고리즘의 평가 척도로 사용 가능하다.

차이는 연산의 수를 기준으로 하는지, 메모리 사용량을 평가 기준으로 하는 지 정도이다.