[Section 1] 알고리즘의 분석 _ 빅-오 표기법

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

빅-오(Big-O) 표기법은 알고리즘의 분석에 자주 등장하는 용어이다. 시간 복잡도를 의미하는 빅-오 표기에 대해 공부하고 예시를 통해서 그 개념을 숙지하도록 하자.

1. 빅-오(Big-O) 표기법

빅오 표기법을 나타내는 기호는 O(함수) 형태로 나타낸다. 다음의 정의와 예시를 보자. 

 

O 기호는 다음과 같은 수학적 정의를 내포하고 있다.

 

" O(f(n)) = { g(n) : 양의 정수  c와 n₀가 존재하여,

0 ≤ g(n) ≤ cf(n)을 만족하는 경우에 대해서 모든 n은 항상 n₀보다 크거나 같다 } "

 

위의 정의는 선뜻 이해하기 어렵지만, 예시를 들어보면 보다 쉽게 이해할 수 있다. g(n) 함수가 n² + 2n + 1이라고 가정하자. g(n)과 f(n)은 O의 정의와 함께 다음과 같이 나타낼 수 있다.

 

"O(f(n)) = g(n) = n² + 2n +1"

 

"f(n) = n²"

 

즉, 빅-오의 괄호 안에 들어가는 함수 f(n) 은  어떤 함수 g(n)의 최소 성장률(smallest rate of growth)을 암시한다. 그리고 이 함수 f(n)이 바로 g(n)에 대해서 점근적으로 가까운 상한(Asymptotic tight upper bound)이 되는 것이다. 보다 명확한 이해를 위해 다음과 같이 각각의 함수 그래프를 그려보자. 왼쪽의 그림을 보면 f(n)이 최소 성장률이 되는 것을 한눈에 알 수 있다. 

 

"왼쪽 그림의 f(n) = n²"

 

"오른쪽 그림의 f(n) = 2n²"

 

빅-오 예시 _ n은 1부터 5까지의 데이터 개수를 나타낸다.

 2. 상한(Upper bound)의 정의

위 그림에서 c가 2일 때 빅-오의 수학적 정의를 만족시키는 n₀는 3이다. 이때 n₀의 의미는 데이터 개수가 최소 3 이상일 때 빅오의 수학적 정의가 들어맞는다는 것이다. 그리고 이 빅오의 수학적 조건을 만족하는 cf(n)을 함수 g(n)의 상한(Upper bound)이라고 말한다.

 

따라서 어떤 함수의 빅오를 나타내는 것은 그 함수의 상한을 보여주는 것이다. 그러므로 함수 g(n)의 빅-오 표기법은 O(n)이 되고 상한은 c=2, n₀ =3이다. 

 

* 어떤 알고리즘의 빅-오 표기법을 보았을 때, n₀에 대해서는 크게 고민하지 않느것이 좋다. 왜냐하면 데이터의 개수가 매우 작은 경우이므로 시간 복잡도가 중요성이 떨어지기 때문이다. 중요한 것은 상한 이라고 할 수 있다. 

 

* 참고로 n₀를 한계점(Threshold) 이라고 부르기도 한다.