[Algorithm] Big O, Omega, Theta and its application

우왕 오랜만에 포스팅이다. 요즘은 예전처럼 직장인이 아니다. 다시 학생으로 돌아갔다. 최근 10주간 한 학기 공부하느라 아주아주 재밌었는데.. 그간 공부했던 것들 정래해보려고 한다. 이 글 재목이 Algorithm Big O, Omega, Theta인데... 이거는 사실 학사 과정에서도 배우는 것이다. 그래도 나 나름대로 공부한 성과이니 포스팅해보도록 하겠다. 이거 말고도 학사에서 배우는 주제인데 포스팅하는 것이 여러개 있을 것이다.

아무튼 Big O, Omega, Theta를 설명해보자. 일반적으로 알고리즘의 효율을 측정하기 위해서 사용된다. 알고리즘의 효율은 무엇을 뜻하는가? 시간적인 효율.. 즉 누가 얼마나 빠른가를 의미할 수도 있고, 공간적인 효율.. 즉 누가 얼마나 최소한의 공간으로 수행할 수 있는지를 의미할 수도 있다. 그런데 대부분 일반적으로 시간적인 효율로 더 많이 쓰인다. Big O, Omega, Theta 말고도 Small O, Omega, Theta도 있는데 이 부분은 여기선 생략하도록 하겠다. 근본적으로 비슷한 내용이기도 하고 정의만 살짝 다른 부분이라 크게 설명할 이유도 없거니와 Big O, Omega, Theta가 더 많이 쓰이기도 한다.

우선, Big O, Omega, Theta를 설명하기 전에 이것들을 조금 쉽게 접근하기 위해서 예를 들어보자. 이 예가 주는 원리는 알고리즘에서 가장 기본적으로 사용되는 원리이니 잘 이해해두기 바란다.

f(n) = n^2

f(n) = n

두 개의 함수가 있다. n이 무한대로 커진다고 했을 때, n과 n^2의 차이는 어떻게 될까? n은 절대 n^2을 따라잡을 수 없다. 수학적으로 봤을 때, 둘다 무한대로 가지만, n^2이 항상 크다. 그러면 아래의 두 함수는 어떨까?

f(n) = 2n

f(n) = n

알고리즘에서 위의 두 함수는 같은 비율로 커진다고 본다. "2n이 크잖아요!!" 네 맞습니다. 2n이 큽니다. 그런데 쉽게 생각해서 "거기서 거기다~" 라고 보면 된다. 도토리들끼리 키를 젤때 큰 도토리가 "내가 0.1micrometer 크거든?" 이라고 말해봤자. 우리들 입장에서 "거기서 거기지 뭐~~" 이렇게 된다. 무한대는 우리가 생각하는 그 어떤 숫자보다 무한대만큼 크다. 그 숫자들 입장에서는 2n과 n은 거기서 거기다. 반면 n^2과 n은 차이가 난다고 본다. 이것이 알고리즘에서 효율을 측정하는 가장 기본적인 원리이다.

자 여기서 Big O, Omega, Theta를 설명하는데, 먼저 Big O부터 설명해보자. Big O는 보통 f(n) = O(g(n))이렇게 쓰인다. 이것이 의미하는 바는 f(n)은 죽었다 깨어나도 g(n)보다는 커질 수 없다 라고 생각하면 되겠다. 여기서 바로 Big Omega로 넘어가버리면 재미없지. 수학으로 들어가줘야 조금 재밌지. 수학적으로 Big O는 아래와 같은 정의를 가지고 있다.

이 말을 다시 하면 f(n)은 죽었다 깨어나도 g(n)보다는 커질 수 없다가 된다. 보통 알고리즘 기본서에 예제로 나오는 것들을 몇 개 풀어보자.

a) 3n = O(n^2)

3n <= Cn^2

3n <= 3n^2 <= Cn^2

C = 3 and n0 = 1, Therefore True.

b) 3n^2 = O(n^2)

3n^2 <= Cn^2

3n^2 <= Cn^2

C = 3 and n0 = 1, Therefore True.

c) 2^n = O(n^2)

양쪽에 log를 씌워주면, n <= logC + 2logn

n <= 2 logn <= logC + 2logn

여기서 2 logn <= logC + 2logn은 True이지만, n <= 2 logn는 False이다. 

Therefore False.

1과 2는 True고 3은 False다. 수식 증명은 위에 잘 되어있으니 잘 이해해보시길 바란다. 

이제 Big Omega를 설명해보자. Big Omega는 f(n) = Omega(g(n))이렇게 있을 때, 다음과 같은 의미를 지닌다. f(n)은 최소한 g(n)보다는 크거나 같다. 수학적으로 Big Omega는 아래와 같은 정의를 가지고 있다.

이 말을 다시 하면 f(n)은 최소한 g(n)보다는 크거나 같다가 된다. 예제를 몇 개 풀어보면 아래와 같다.

1) (n + n^2) / 2 = Omega(n^2)

(n + n^2) / 2 >= n^2/2 >= Cn^2

C = 1/2, n0=1, Therefore true

True다. 마지막으로 Big Theta를 보자. Big Theta는 쉽게 말해서 Big O이고 Big Omega이면 Big Theta다. 그래서 수식으로는 아래와 같이 정의된다.

왼쪽의 두 식을 보면 Big O이고 오른쪽의 두 식을 보면 Big Omega이다. 그래서 Big Theta이기 위해서는 Big O이고 Big Omega이어야 한다. 이 말을 풀어쓰면 어떻게 될까? f(n) = Theta(g(n))일 때, f(n)과 g(n)은 같은 비율로 증가한다 라고 볼 수 있다.

자 기본적으로 알고리즘에서 Big O, Omega, Theta가 무엇인지 설명해봤다. 이것을 그러면 어떻게 활용할 것인가? 아래와 같은 코드가 있다고 해보자.

아주 간단한 코드이다. 이 코드는 길이 n의 input array를 가지고 연산을 하는데, input array의 크기에 따라서 operation의 수가 어떻게 증가하는지를 알아보자. 여기서 우선 정의하고 넘어갈 것이 어떤 것을 operation으로 칠 것이냐이다. 아래의 연산들을 operation으로 가정하자.

1) Value assignment, 예를 들어 n=18

2) 사칙연산, 예를 들어 +,-,*,/

3) 값 비교, 예를 들어 i < j

4) 메모리 접근, 예를 들어 A[i]

5) Return value, 예를 들어 return A

위의 operation들을 센다고 가정하고, 코드 실행시마다, Outer loop마다, Inner loop마다 실행되는 operation의 개수는 아래와 같다.

즉, n=1, 2, 3, 4, ....., k일 때를 계산해보면 아래와 같다.

이것을 n에 대한 수식으로 나타내려면 k를 n으로 바꿔주기만 하면 된다.

자, 이것은 Big O로 계산하면 어떻게 되나? f(n) = O(n^2)이다. 알고리즘을 측정할 때 이와 같이 측정을 할 수 있겠다. 다음에는 Master Theorem에 대해서 포스팅해보려고 한다.