안녕하세요. 도미닉입니다.
오늘은 복잡도에 대해서 알아보겠습니다.
복잡도란 무엇인가
복잡도는 확장성과 관련이 깊다.
확장이 가능하냐는 질문은 소프트웨어 개발을 할 때 반복되는 질문 중 하나이다.
만약 10분 안에 처리되야하는 소프트웨어가 100분이 걸리게 된다면 이것은 확장성에 위배된다고 할 수 있다.
하지만 데이터의 양에 따라 10분이라는 시간은 상대적일 것이다.
이럴 때 우리는 복잡도를 활용한다.
복잡도에는 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)가 있다.
시간 복잡도란 무엇인가
시간 복잡도는 입력되는 데이터의 양이 증가함에 따라 알고리즘이 실행되는데 필요한 시간을 나타낸 것이다.
시간 복잡도의 종류에는 Constant time, Linear time, Quadratic time, Logarithmic time, Quasilinear time 등이 있다.
Constant time 이란 무엇인가
Constant 은 번역하면 일정한 이라는 형용사이다.
입력되는 사이즈와 상관없이 일정한 시간을 가지는 시간 복잡도이다.
빅오표기법으로 O(1) 이다.
예제 소스는 아래와 같다.
데이터의 증가에 따라 시간의 증가를 나타내는 표는 아래와 같다.
Linear time 이란 무엇인가
Linear 은 번역하면 선형이라는 뜻이다.
가장 일반적인 것으로 데이터의 양이 증가함에 따라 시간도 균등하게 증가하는 시간 복잡도이다.
빅오표기법으로 O(N) 이다.
예제 소스는 아래와 같다.
데이터의 증가에 따라 시간의 증가를 나타내는 표는 아래와 같다.
Quadratic time 이란 무엇인가
Quadratic 은 번역하면 이차라는 뜻이다.
이차라는 말에서 예상할 수 있듯이 데이터의 양이 증가함에 따라 제곱 꼴로 증가해가는 시간 복잡도이다.
빅오표기법으로 O(N제곱) 이다.
예제 소스는 아래와 같다.
Logarithmic time 이란 무엇인가
Logarithmic 은 번역하면 대수라는 뜻이다.
Logarithmic 에서 앞에 세글자만 보면 log 이다.
그렇다. Logarithmic 은 로그와 관련이 있다.
빅오표기법으로 O(logN) 이다.
예제 소스는 아래와 같다.
Quasilinear time 이란 무엇인가
준선형 시간이다.
빅오표기법으로 O(NlogN) 이다.
공간 복잡도(Space comlexity) 란 무엇인가
시간과 마찬가지로 공간 또한 확장의 주요 요소이다.
공간 복잡도는 소프트웨어가 메모리를 얼마나 차지하는지에 대한 지표이다.
위의 예제소스의 공간 복잡도는 O(N) 이다.
같은 기능을 하지만 더 긴 아래 예제소스의 공간 복잡도는 O(1) 이다.
정리
- 시간 복잡도는 입력 크기가 증가함에 따라 알고리즘을 실행하는 데 필요한 시간을 측정한 것이다.
- 공간 복잡도는 알고리즘을 실행하는 데 필요한 메모리를 측정한 것이다.
- Big O 표기법은 일반적인 형태의 시간 및 공간 복잡성을 나타내는 데 사용한다.
- 시간과 공간의 복잡성은 높은 수준의 확장성의 척도이다. 알고리즘 자체의 실제 속도는 측적하지 않아도 된다.
- 작은 데이터 세트의 경우 시간복잡도와 일반적으로 관련이 없다. 준선형 알고리즘음이 선형 알고리즘 보다 느릴 수 있다.