시간복잡도

백준같은 곳에서 알고리즘을 공부하다 보면 필연적으로 시간복잡도라는 개념을 한 번쯤은 보게 된다. 단순히 어떤 알고리즘의 시간복잡도가 \(\mathcal{O}(n^2)\)라는 것을 입력의 크기가 \(n\)일 때 최악의 경우에 실행 시간이 \(n^2\)에 비례한다는 것만 알아도 알고리즘 문제를 푸는 것에는 큰 영향이 없지만, 이 글에서는 시간복잡도의 수학적 정의에 대해서 알아보고자 한다.

시간복잡도를 나타내는 방법은 Big \(\mathcal{O}\), Big \(\theta\), Big \(\Omega\)로 크게 3가지가 있다.

Big $\mathcal{O}$

\[\text{어떤 양의 상수 } M, c\text{과 } M \text{이상의 모든 } x\text{에 대해 } \vert f(x)\vert \le c\vert g(x)\vert\text{일 때 } f(x)\in \mathcal{O}(g(x))\]

보통 위의 정의를 만족할 때 이해하기 쉽도록 \(f(x)=\mathcal{O}(g(x))\)라고 표기하는 경우도 있지만, 여기서는 좀 더 엄밀하게 하기 위해 \(f(x) \in \mathcal{O}(g(x))\)로 표기하도록 하겠다.

위 그림에서 보면, \(n\)이 \(n_0\)보다 큰 모든 경우에 \(\vert f(n)\vert \le c\vert g(n)\vert\)이므로 \(f(n) \in \mathcal{O}(g(n))\) 이다.

예를 들어 \(f(x) = x^2\)라고 하자.

만약 \(g(x) = x^3\)이라면 \(c\)가 어떤 양수가 되더라도 충분히 큰 \(M\)가 있어 모든 \(M\)보다 큰 \(x\)에 대해 \(f(x) \le cg(x)\)이므로 \(f(x) \in \mathcal{O}(g(x))\)이다.

만약 \(g(x) = x^2 - 3x\)이라면 \(c\)가 모든 양수는 아니더라도 충분히 큰 \(c, M\)이 있어 \(M\)보다 큰 모든 \(x\)에 대해 \(f(x) \le cg(x)\)이므로 \(f(x) \in \mathcal{O}(g(x))\)이다.

하지만 \(g(x) = x\)이라면 \(c\)가 어떤 수가 되더라도 충분히 큰 \(x\)에 대해 \(f(x) > cg(x)\)이므로 \(f(x) \notin \mathcal{O}(g(x))\)이다.

Big $ \Omega $

\[\text{어떤 양의 상수 } M, c\text{과 } M \text{이상의 모든 } x\text{에 대해 } \vert f(x)\vert \ge cg(x)\text{일 때 } f(x)\in \Omega(g(x))\]

즉, \(Big \mathcal{O}\)와 반대라고 생각하면 편하다.

이번에도 예를 들어 \(f(x) = x^2\)라고 하자.

만약 \(g(x) = x^3\)이라면 \(c\)가 어떤 양수가 되더라도 충분히 큰 \(x\)에 대해 \(\vert f(x)\vert < c\vert g(x)\vert\)이므로 \(f(x) \notin \Omega(g(x))\)이다.

만약 \(g(x) = x^2 - 3x\)이라면 \(c\)가 모든 양수는 아니더라도 충분히 작은 \(c\)와 충분히 큰 \(M\)가 있어 \(M\)보다 큰 모든 \(x\)에 대해 \(\vert f(x)\vert \ge c\vert g(x)\vert\)이므로 \(f(x) \in \Omega(g(x))\)이다.

그리고 \(g(x) = x\)이라면 충분히 큰 \(M\)이 있고 \(c\)가 어떤 양수가 되더라도 충분히 큰 \(x\)에 대해 \(\vert f(x)\vert \ge c\vert g(x)\vert\)이므로 \(f(x) \in \Omega(g(x))\)이다.

Big $\theta$

\[f(x) \in \mathcal{O}(g(x)) \text{이고 } f(x) \in \Omega(g(x)) \text{일 때 } f(x) \in \theta(g(x))\]

사실 Big \(\theta\)는 이게 끝이다.

성질

Big \(\mathcal{O}\), Big \(\Omega\), Big \(\theta\) 표기법에는 여러 성질들이 있다.

1. 반사성

\[f(x) \in \mathcal{O}(f(x)), f(x) \in \Omega(f(x)), f(x) \in \theta(f(x))\]

2. 전이성

\[f(x) \in \mathcal{O}(g(x)), g(x) \in \mathcal{O}(h(x)) \text{이면 } f(x) \in \mathcal{O}(h(x))\]

\[f(x) \in \Omega(g(x)), g(x) \in \Omega(h(x)) \text{이면 } f(x) \in \Omega(h(x))\]

\[f(x) \in \theta(g(x)), g(x) \in \theta(h(x)) \text{이면 } f(x) \in \theta(h(x))\]

3. 대칭성

\[f(x) \in \theta(g(x)) \Leftrightarrow g(x) \in \theta(f(x))\]

4. 전치 대칭성

\[f(x) \in \mathcal{O}(g(x)) \Leftrightarrow g(x) \in \Omega(f(x))\]

5. 덧셈 규칙

위에서 추측할 수 있듯이, \(\mathcal{O}(f(x)), \Omega(f(x)), \theta(f(x))\)는 전부 다 집합이다.

\[\mathcal{O}(f(x)) + \mathcal{O}(g(x)) = \mathcal{O}(f(x) + g(x))\]

\[\Omega(f(x)) + \Omega(g(x)) = \Omega(f(x) + g(x))\]

\[\theta(f(x)) + \theta(g(x)) = \theta(f(x) + g(x))\]

예를 들어 \(\mathcal{O}(x^2) + \mathcal{O}(x) = \mathcal{O}(x^2+x) \text{이고, } \mathcal{O}(x^2+x) = \mathcal{O}(x^2)\)이므로 \(x\)가 충분히 큰 수라고 생각했을 때

\[\mathcal{O}(f(x)) + \mathcal{O}(g(x)) = \mathcal{O}(max(f(x), g(x)))\]

으로 써도 무방하다. 마찬가지로

\[\Omega(f(x)) + \Omega(g(x)) = \Omega(min(f(x), g(x)))\]

도 성립한다.

6. 곱셈 규칙

\[\mathcal{O}(f(x)) \cdot \mathcal{O}(g(x)) = \mathcal{O}(f(x) \cdot g(x))\]

\[\Omega(f(x)) \cdot \Omega(g(x)) = \Omega(f(x) \cdot g(x))\]

\[\theta(f(x)) \cdot \theta(g(x)) = \theta(f(x) \cdot g(x))\]

\(f(x) = x^2, g(x) = log(x)\)라 하자. \(x\)가 충분히 클 때 \(\mathcal{O}(f(x))\)에 속한 함수는 \(f(x)\)보다 작거나 같고, \(\mathcal{O}(g(x))\)에 속하는 함수는 \(g(x)\)보다 작거나 같다. 당연히 이 둘의 곱은 \(\mathcal{O}(f(x) \cdot g(x))\)보다 작거나 같다.

어떤 알고리즘이 좋을까?

잠시 정보과학의 영역으로 넘어와 보자. 알고리즘의 시간복잡도는 알고리즘의 효율성을 따질 때 중요한 지표 중 하나인데, 맨 처음에도 말했듯이 Big \(\mathcal{O}\) 표기법으로 나타낼 수 있다. \(0 < a < b\)인 \(a, b\)가 존재하고 \(x\)가 충분히 클 때, 알고리즘의 시간복잡도 별 걸리는 시간은 아래와 같다.

\[\mathcal{O}(1) < \mathcal{O}((log(x))^a) < \mathcal{O}((log(x))^b) < \mathcal{O}(x^a) < \mathcal{O}(x^b) < \mathcal{O}(a^x) < \mathcal{O}(b^x) < \mathcal{O}(x!)\]

위의 부등식들과 덧셈 규칙, 곱셈 규칙을 잘 결합하면 알고리즘이 얼마나 효율적인 것인지 알 수 있을 것이다.

결론

처음에는 수학적으로 엄밀하게 시간복잡도를 정의하고 그의 성질들도 엄밀하게 설명하려 했지만, 글을 써내려 갈수록 어쩔 수 없이 직관을 요하는 부분이 많았던 것도 사실이다. 이 점은 독자의 양해를 바란다. 이 글을 다 읽었다면 앞으로는 Big \(\mathcal{O}\) 표기법이 나와도 두려워 할 것 없다. 그러니 여러 알고리즘들을 배울 때 시간복잡도 표기가 나오면 위의 정의와 성질들을 곱씹으며 그것이 무엇을 의미하는지 확실히 이해하기를 바란다.