[알고리즘] - Big O (O) notation의 의미

오늘은 간단히 컴퓨터 과학 분야에서 흔히 사용되는 Big O notation의 의미를 얘기해보고자 한다. Big O notation이 사용되는 대상은 알고리즘에 대한 것이다. 어떤 알고리즘의 복잡도(complexity)가 얼마나 되느냐고 묻는 것과 같다. 조금 더 세분화해서 들어가면 복잡도는 1) 계산 복잡도, 2) 저장 복잡도로 얘기가 되기도 한다. 하지만 여기서는 그냥 계산 복잡도를 얘기하도록 하겠다. 어차피 계산 방식은 같기 때문에 Big O가 어떻게 계산되는지 알면 세분화된 내용들은 자동적으로 이해된다.

---

Big O notation은 알고리즘의 복잡도를 설명할 때 사용되는 방식인데, 일단 2가지 방식으로 설명해보련다.

첫번째는 쉬운 방법으로 이해하면, Big O notation은 일종의 어림잡은 복잡도라는 것이다. 근사라는 말에 대해서 들어보았을 것이다. 무치 어떤 수렴하는 수열을 무한대로 보내면 어떤 값이나 방정식으로 수렴하는 것처럼, Big O도 그렇게 계산된다. 그래서 영어로 asymptotic이라는 말을 쓰는데, 쉽게 말하면 주어진 알고리즘 (수학적으로 말하면 "함수")의 input 값을 무한대로 보냈을 경우 어떻게 되는지를 묻는 것과 같다.

첫번째 설명은 일종의 직관을 얻기 위해서 설명하는 방법이라고 하겠다. 그렇다면 이제 두번째, 진짜 정의에 대해서 알아보자.

---

$$ f(n) = O(g(n)) \Leftrightarrow \exists c > 0, n_0 s.t. ~ |f(n)| \leq c \cdot g(n) \forall n \geq n_0 $$

이 수식이 Big O의 수학적 정의라고 할 수 있는데, 차근차근 설명해보겠다.
먼저, 여기서 우리가 복잡도를 정의하려는 함수는 $f(n)$이다. $g(n)$은 우리가 $f(n)$의 복잡도를 설명할 함수가 된다. 여기서 $g(n)$과 $f(n)$의 관계를 보면, 만일 $g(n)$에 0보다 큰 어떤 상수 $c$를 곱해서 $f(n)$의 값보다 큰 값을 가질 수 있으면 $f(n)$의 복잡도를 $g(n)$이라고 한다는 것이다.

그렇다면 가볍게 예를 들어보자.
만일 우리의 알고리즘의 계산량이 $f(n) = 4n^2 + 3$와 같은 2차 함수라고 한다면, 실질 복잡도는 무엇일까? 위에서처럼 $g(n)$을 $n$으로 놓는다면 n을 무한대로 보냈을 때, 어떠한 c를 가져와도 언제나 $f(n)$이 더 클 것이다. 그러므로 조건을 만족하지 못한다. 하지만 $n^2$일 경우에는 어떤가? 만일 상수가 5나 6보다 더 큰 수를 놓을 경우 언제나 $f(n)$보다 크게 된다. 일종의 upper bound가 되는 것이다. 그러므로 $f(n)$의 복잡도는 $O(n^2)$이 되는 것이다.

또, 하나 짚고 넘어가고 싶은게 있는데 computer science에서, 알고리즘을 논할 때 =(등호)는 일종의 집합 관계에서 포함관계를 대체하기도 한다. 엄밀히 말하면 그렇게 해서는 안되지만 이 분야의 관행이라 아직도 논문에서는 종종 그렇게 쓸 때가 있다.
예를 들어, $O(f(n)) = O(n^2)$ 라고 하는 것은 둘이 같다고 하는게 아니라, $f(n)$이 $O(n^2)$에 속한다는 뜻으로 이해하면 된다는 것이다.

그렇다면 오늘은 여기까지!