03b. 성능 분석의 기준

양질의 자료구조와 알고리즘을 구분하는 기준

시간은 귀중합니다. 그렇기에 양질을 판단하는 대표적 척도는 실행시간(Running time) 입니다. 자료구조의 연산, 알고리즘이 수행하는 절차에서 효율성에 관심을 가져야합니다. 또한 메모리 사용 크기(공간)도 고려해야합니다. 단순히 용량 뿐만 아니라 실행시간에 영향을 주기 때문이죠.(쓸 데 없이 짐이 크면 나르기 힘들잖아요.)

추가로 처리해야되는 데이터의 개수와 크기에 따라 어떻게 실행시간이 바뀌는 지에 대한 관계도를 고려해야합니다. 경우에 따라 격차가 작을수도, 엄청 클 수도 있기 때문인데, 이에 대해서 빅오(Big-Oh) 표기법에서 알아봅시다.

시간 복잡도와 공간 복잡도

최적의 알고리즘은 시간 복잡도와 공간 복잡도로 분석한 결과가 좋음을 뜻합니다. 시간 복잡도(time complexity)는 '속도'에 관한 분석 결과, 공간 복잡도(space complexity)는 '메모리 사용량'에 대한 분석 결과입니다. 즉. 메모리도 적게 쓰고 속도도 최고로 빨라야 최적 알고리즘이죠.

그러나 시간이 지날수록 메모리에 대해서는 외부적 요인(하드웨어 부품 개발 등)으로 개선되거나 비교 대상이 메모리에 대해서는 동일한 조건일 경우가 많고, 시간 복잡도와 공간 복잡도를 동시에 사용하여 어느 것이 더 좋다를 판단하기 애매합니다. 그래서 보통 '속도'에 집중하여 판단합니다.

 

위키독스 연재 : https://wikidocs.net/book/2868