복잡도 (Complexity) (1) - 빅오 (Big-O) 표기법

복잡도란 알고리즘의 성능을 나타내는 척도이다.

복잡도에는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 시간복잡도는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타내고 공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 메모리를 얼마나 차지하는지를 나타낸다.

일반적으로 적은 시간을 소요하고, 적은 메모리를 차지하는 것이 좋은 알고리즘이라는 것은 자명한 사실이다.

복잡도를 표기하는 방법에는 여러가지 방법이 있다.

• 빅오(Big-O)표기법
• 빅오메가(Ω)표기법
• 빅세타(Θ)표기법

---

 

빅오(Big-O)표기법

먼저 빅오(Big-O)표기법이란 쉽게 말해 함수의 상한(upper-bound)만을 고려하는 표기법이다. 즉, 가장 빠르게 증가하는 항만을 고려하는 것이다. 만약 적절한 양수 c가 존재하고, ∣f(n)∣ ≤ c * ∣g(n)∣ (n≥n0인 모든 n에 대해서) 를 만족하는 n0가 존재한다면 f(n)은 빅오표기법을 사용해 아래와 같이 표기한다.

f(n) = O(g(n))

빅오표기법 (그래프)

---

 

빅오메가(Ω)표기법

다음으로 빅오메가(Ω)표기법이란 빅오표기법과 반대되는 개념이라고 생각할 수 있다. 즉, 어떤 함수의 하한(lower-bound)만을 고려하는 표기법이다. 만약 적절한 양수 c'이 존재하고, ∣f(n)∣ ≥ c' * ∣g(n)∣ (n≥n0인 모든 n에 대해서)  를 만족하는 n0가 존재한다면 f(n)은 빅오메가표기법을 사용해 다음과 같이 표기한다.

f(n) = Ω(g(n))

빅오메가표기법 (그래프)

---

 

빅세타(Θ)표기법

마지막으로 빅세타(Θ)표기법이란 빅오표기법과 빅세타표기법을 합친 개념이라고 할 수 있다. 즉, 어떤 함수의 상한과 하한을 동시에 고려하는 표기법이다. 만약 적절한 양수 c와 c'이 존재하고, c' * ∣g(n)∣ ≤ ∣f(n)∣ ≤ c * ∣g(n)∣ (n≥n0인 모든 n에 대해서)  를 만족하는 n0가 존재한다면 f(n)은 빅세타표기법을 사용해 다음과 같이 표기한다. ( => g(n)은 f(n)의 상한이자 하한이다. )

f(n) = Θ(g(n))

빅세타표기법 (그래프)