시간 & 공간 복잡도

시간 복잡도와 공간 복잡도

우리는 구현의 목적으로만 코드를 짜지 않는다. 어떤 데이터가 들어오고 어떻게 저장하는지 그리고 해당 데이터를 사용할 때 프로그램이 얼마나 효율적인지를 고민하면서 코드를 짠다. 즉, 자료구조와 알고리즘을 고려하여 작성한다면 훨씬 더 품질이 좋은 코드를 짤 수 있다는 것이다.

모든 평가에는 평가 기준이 있다. 마찬가지로 코드, 프로그램에서도 평가 기준이 있는데 시간 복잡도와 공간 복잡도가 이 기준에 속해있다. 코드가 얼마나 복잡한지, 얼마나 빠른지. 즉, 얼마나 “효율적” 으로 프로그램이 잘 만들어져 있는가를 의미한다.

시간 복잡도

시간 복잡도는 입력의 크기에 따른 프로그램의 실행 관계를 의미한다. 말이 조금 어려운데, 데이터의 크기에 따라 혹은 데이터의 처리의 양에 따라 시간이 얼마나 걸리는가? 라고 생각하면 편하다.

Big-O 표기법

시간 복잡도는 Big-O 표기법을 척도로 사용한다. Big-O는 함수의 점근적 상한을 표현한다.

점근적 상한

입력하는 $n$ 이 점점 증가하여 무한대로 커진다고 가정하자. $n$에 따라 실행 시간이 증가하지만. 한계에 점차 다가가는 것을 의미한다. 즉, 그 한계 이상으로는 커지지 않는다는 것을 내포한다.

Big-O의 표기법으로는 $O(\text{상환}(n))$ 으로 표현된다. 예를 들면 $O(n^2)$는 입력값이 $n$이 증가하더라도 실행 시간의 증가율은 $n^2$보다는 작다는 것으로 알 수 있다.

• $\theta$ 표기법: 평균적인 실행 시간. $\theta (n^2)$ : 실행 시간의 증가율은 $n^2$과 같다.
• $\omega$ 표기법: 입력에 대한 실행 시간의 점근적 하한 $\omega (n^2)$: 실행 시간의 증가율은 $n^2$보다 크다.

Big-O 표기법

Big-O 표기법은 최고 사항만 고려한다. 즉, 입력값 n에 대한 실행 시간의 점근적 상한을 수식으로 표현할 때 최고 차항의 차수만 고려한다.

공간 복잡도

공간 복잡도는 시간 복잡도와는 다르게 공간, 즉, 사용될 메모리 자원의 양을 의미한다. 메모리의 사용량이 많다면 공간 복잡도가 상승하고, 그게 아니라면 줄어들 것이다.

참고자료

※ 이 글은 『이것이 컴퓨터 과학이다』 책을 기반으로, 다양한 자료를 참고해 작성했습니다.