시간 복잡도 , 공간 복잡도

알고리즘을 평가하는 두 가지 요소

 

시간 복잡도 : 얼마나 빠른가에 대하여 논하는 것(cpu에 얼마나 부담을 주는가?)

(cpu가 하는 일의 시간과 비례한다.)

 

공간 복잡도 : 얼마나 메모리를 적게 쓰는가?

(알고리즘 평가시에 보조적인 역할을 담당한다.)

 

이때 시간 복잡도를 조금더 중요시 여긴다.

 

 

시간 복잡도의 평가 방법

 

- 중심이 되는 특정 연산의 횟수를 세어 평가를 한다.

 

- 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

시간복잡도 T(n)을 계산한다고 하면

'최악의 경우(worst case)'를 기준으로 계산한다.

'평균적인 경우'는 알고리즘 평가에 도움이 되지만 객관적 평가가 쉽지 않고 계산하기가 어렵다.

그리고 '평균적인 경우' 라는 것을 증명하기 어렵고, 상황에 따라 계속 달라진다.

반면, 최악의 경우는 늘 동일하게 나타난다.

 

 

알고리즘의 수행 속도 비교 기준

 

- 데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.

(요즘 컴퓨터들은 다 성능이 좋아서 거의 무관)

 

- 데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다.