Chapter 01. 빅-오에 대한 수학적 접근

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

 

지금부터는 빅-오의 수학적 판별법에 대해 배웁니다. 그런데 이 책의 저자는 설명하기에 앞서 이 내용이 어려운 편에 속하니 이해가 쉽지 않다면 이 내용은 건너뛰어도 문제가 없다고 말합니다.

 

먼저 빅-오의 수학적 정의입니다.

 

"두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ K에 대하여 f(n) ≤ Cg(n)을 만족하는 두 개의 상수 C와 K가 존재한다면, f(n)의 빅-오는 O(g(n))이다." 

 

예를 들어 다음의 두 함수가 있다고 가정하겠습니다.

n ≥ 10인 경우에 대해서, 어떤 상수 C를 g(n)에 곱했을 때, Cg(n)이 항상 f(n)보다 크도록 하는 C를 아무거나 하나 찾아봅니다. 정말 아무거나 골라서 저는 99를 선택했습니다. 그러면 g(n)에 99를 곱한 값은 n ≥ 10인 경우에서 f(n)보다 항상 클까요? 그래프를 통해 확인해 보겠습니다.

위 그래프를 보면 g(n)에 99를 곱한 그래프에 비해 f(n) 그래프는 거의땅을 기어다니고 있습니다. 즉, n ≥ 10인 경우에 대해서 99를 곱한 g(n)은 항상 f(n)보다 큽니다. 이러한 경우에 g(n)을 f(n)의 빅-오라고 합니다.

 

그런데 이렇게 반문할 수도 있습니다. "아무 수나 곱할 수 있으면, 무식하게 큰 수 아무거나 곱해버리면 g(n)이 n이더라도 항상 f(n)보다 클 수 있는 거 아니냐"

 

다음 그래프를 보겠습니다.

위 그래프의 보라색 선은 9999를 곱한 n을 나타내고 있습니다. 어느 구간 내에서는 f(n)보다도 크지만 이내 f(n)에게 따라 잡히는 모습입니다. 이는 9999가 아닌 이보다 더 큰 수를 곱해도 마찬가지로 나타납니다.

 

위와 같은 결과가 나타날 수 밖에 없는 이유는 n이 가지는 증가율이 2n^2+n+500이 가지는 증가율보다 작기 때문입니다. 반면 n^2와 비교하면  2n^2+n+500의 증가율은 절대 n^2의 증가율을 능가할 수 없습니다.

 

즉, 빅-오는 증가율의 상한선을 표현하는 표기법입니다. n^2가 2n^2+n+500의 빅-오라는 것은 다음의 의미를 가집니다.

 

"2n^2+n+500의 증가율은 암만 높아봐야 n^2를 능가할 수는 없다."