알고리즘의 복잡도

입력 n에 대한 알고리즘의 성능을 평가하는 지표로써
시간복잡도와 공간 복잡도를 사용

 

• 시간복잡도 : 알고리즘의 수행시간을 평가
• 공간복잡도 : 알고리즘에 사용되는 메모리용량에 따라 평가

대표적인 복잡도 카테고리

O(log N)

O(N) : 1차(linear)

O(n log n)

O(n^2) : 2차(quadratic)

O(n^3) : 3차(cubic)

O(2^n) : 지수(exponential)

O(n!)

 

함수가 다항식일 때 최고차항만을 계산하여 표기함

---

시간복잡도 함수 증가율

* bigO 표기법

정의 : 주어진 복잡도함수 f(n)에 대해서  g(n) = O(f(n))을 만족한다(= g(n)의 증가율, 기울기가 낮다라고 말할 수 있다.)

 

정리하자면 시간복잡도에 대한 표기를 bigO 표기법으로 하며, bigO표기법으로 사용되는 대표적인 카테고리를 알아보았다. 특정 알고리즘의 수행시간의 상한이 O(f(n))넘어가지 않는 경우를 말한다.