시간 복잡도와 공간 복잡도

알고리즘의 성능을 평가하기 위해서 시간 복잡도와 공간 복잡도라는 개념이 사용된다.

시간 복잡도는 속도에 관한 것이고, 공간 복잡도는 메모리 사용량에 관한 것이다.

 

하지만 알고리즘의 속도를 재기란 매우 힘든 일이다. 컴퓨터의 연산 속도에 따라 다르고, 같은 컴퓨터에서 잰다 하더라도 시간은 다르게 나오게 된다. 그래서 알고리즘의 속도를 재기 위해서는 연산 횟수를 세고, 처리할 데이터의 수 n에 대한 연산 횟수를 계산하는 함수 T(n)을 만든다.

함수 T(n)을 만드는 이유는 데이터의 수가 늘어남에 따라 연산 횟수의 변화를 알아내기 위함이다. T(n)을 구성하면 아래와 같이 그래프를 통해 데이터수에 따른 연산 횟수 변화를 한눈에 볼 수 있다.

 

 

그렇다면 위와 같이 알고리즘 A와 B가 있다고 가정해보자. 데이터가 적을 땐 B가 더 빠르고, 데이터가 많을 땐 A가 더 빠르다. 그렇다면 우리는 어떤 알고리즘을 사용해야 할까?

정답은 A이다. 그 까닭은 데이터의 수가 적을 땐 속도 차이가 크지 않기 때문이다. 중요하게 봐야 할 것은 데이터의 수가 증가함에 따른 수행 속도의 증가이다.

 

그렇기 때문에 알고리즘을 평가할 때 중요한 것은 최선의 경우( 가장 빠를 때 )가 아니라 최악의 경우( 가장 느릴 때 )이다.