I. 시간 복잡도와 Big-O Notation

• Time Complexity Analysis
• Asymptotic Notation
• Additional topics and Problems

Time Complexity Analysis

알고리즘 (Algorithm) 과 자료구조 (Data Structure) 를 공부하는 우리의 목표는, 같은 문제를 효율적으로 해결하는 것입니다. 뭔가를 효율적으로 하기 위해서는 항상 효율을 측정하는 기준이 필요할 것입니다.

일반적으로 이 기준에는 다음 두 가지가 가장 중요합니다.

• 프로그램이 얼마나 오래 걸리는가

• 프로그램이 얼마나 많은 자원 (대표적으로 메모리 등) 을 요구하는가

당연하게도, 이 부분은 입력이 무엇인지에 따라 달라집니다. 대표적으로 원소 10개짜리 배열을 정렬하는 것과 100만개짜리 배열을 정렬하는 것의 소요 시간과 소모 메모리는 다를 수밖에 없기 때문입니다. 우리는 이를 위해, 일반적으로 입력이 증가함에 따라, 소요 시간과 메모리가 어떻게 변화하는지 를 알고자 합니다.

특히, 현대의 컴퓨팅 환경에서 중요한 것은 시간입니다. (메모리가 중요하지 않다는 뜻은 아닙니다) 따라서 우리는 알고리즘의 시간 복잡도를 가장 중요하게 볼 것입니다. 즉, 입력의 크기 $n$에 대해, 소요 시간 $T(n)$ 이 얼마나 빨리 증가하는가? 라는 질문을 알고리즘의 효율성으로 이해하고자 합니다. 그런데, 입력의 크기가 $n$으로 같다고 해서 정말 소요 시간이 같을까요?

정렬하는 문제를 생각해 봅시다. 정렬하는 문제에서, 원소 10개짜리 배열을 정렬하는데...

• 1, 2, 3, 4, ... 로 이미 정렬된 배열이 들어오면, 아무것도 할 필요가 없습니다.

• 어쩌면 거꾸로 정렬된 배열이 들어와서 다 엎어야 할수도 있습니다.

• 그렇다면 크기가 $n$인 모든 입력에 대해 평균을 내는것이 합당할까요?

즉, 크기가 $n$인 모든 입력의 집합 $S_n$에 대해, 다음 세 가지는 모두 중요할 수 있습니다. \(\min_{s \in S_n} T(s) \quad\quad\quad \max_{s \in S_n}T(s) \quad\quad\quad \frac{\sum_{s \in S_n}T(s)}{\abs{S_n}}\) 이를 우리는, Best / Worst / Average 시간복잡도라고 부릅니다. 알고리즘에 관한 연구는 수학적으로 엄밀한 것을 목표로 하기 때문에, 일반적으로는 Worst case를 가지고 다루고자 하는 tendency가 있습니다. 그러나 현실에서는 Average case를 잘 푸는 알고리즘도 매우 중요하기 떄문에, 필요하다면 이를 명시하고 사용할 것입니다. Unless otherwise stated, 앞으로 나오는 복잡도는 worst case입니다. 즉, $T(n)$이란, 입력이 $n$인 입력들 중, worst case에 필요한 시간을 의미할 것입니다. 우리는 문제를 단순화하기 위해 $T(n)$을 $\N \to \N$함수로 받아들이겠습니다.

Asymptotic Notation

중요한 사실 하나는, 정확한 $T(n)$은 사실 그렇게 중요하지 않다는 부분입니다. 컴퓨터 구조 를 배우면 알수 있는데, 두 실수의 곱셈은 두 정수의 덧셈보다 수 배 이상 느립니다. 즉 정수덧셈 100만번이 실수곱셈 20만번보다 빠를지도 모른다는 의미입니다. 수학적으로는 보통 FLOP count 라 하여, 실수 연산 몇번으로 bound 되는지를 가지고 관찰하는데, 정수연산만 쓰는 알고리즘을 개발하였다면 이는 조금 불합리하게 느껴질 수 있습니다.

그러나 $n$이 커질 때, $n^2$, $n^2 \log n$, $n^3$ 등은 상당히 큰 차이를 불러일으킵니다. 따라서, 우리는 다음과 같은 Big-O notation을 정의할 것입니다. Big-O notation $O(g)$란, $g : \N \to \N$ 에 대하여, \(f \in O(g) \iff ^\exists N, C \in \N \st ^\forall n \geq N, f(n) \leq Cg(n)\) 이를 잘 생각해 보면 다음과 동치임을 알 수 있습니다. \(f \in O(g) \iff \limsup_{n \to \infty} \frac{f(n)}{g(n)} < \infty\) 대충, 의미를 받아들일 때는 ‘충분히 큰 $n$에 대해, $f$를 $g$의 상수 배로 바운드를 잡을 수 있다’ 라고 생각하시면 됩니다. 예를 들어 $3n^2 + 4n + 6$ 은 $O(n^2)$ 다 라고 말할 수 있는 것입니다.

Big-Omega notation이라는 것이 있습니다. Big-Omega는 반대로, 알고리즘의 하한에 대한 논의입니다. ¹² \(f \in \Omega(g) \iff ^\exists N, C \in \N \st ^\forall n \geq N, f(n) \geq Cg(n) \iff \liminf_{n \to \infty} \frac{f(n)}{g(n)} > 0\)

간혹 Little-o 와 Little-omeaga도 씁니다. \(f \in o(g) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty\)

중요한 notation으로, $f \in O(g)$ 이고 $f \in \Omega(g)$ (또는 $g \in O(f)$) 이면, $f \in \Theta(g)$ 이고 $g \in \Theta(f)$ 라고 씁니다. 대략 시간 복잡도의 관점에서 두 함수는 사실상 같게 취급된다는 의미입니다.

예를 들어, 위에서 본 $3n^2 + 4n + 6$는 $O(n^2)$ 이고 $O(n^3)$ 이지만, $\Theta(n^3)$은 아닙니다. 하지만 $\Theta(n^2)$ 가 됨은 알 수 있습니다.

우리는 편의상 알고리즘을 공부하면서, 1억 = 1초라는 Rule of Thumb을 이용합니다. 즉, $O(n^2)$ 알고리즘이면, 대략 $n = 10000$ 까지는 1초에 작동할 것이라고 믿겠다는 말입니다. 이 규칙이 몇년째 바뀌지 않았다고 들은것 같은데, 그동안 컴퓨터는 빠르게 발전했기 때문에 사실 지금은 1억보다는 더 많이 돌아가기는 합니다만, 우리가 $O(n^2)$이라고 말하더라도 실제로는 $3n^2 + 6n$ 같은 것일 경우가 많으므로 Rule of Thumb으로는 유효하다고 생각합니다.

시간 복잡도는 매우 중요하고 항상 생각해야 하지만, 시간 복잡도가 모든 것을 좌우하지 않음도 꼭 기억해야 합니다. 컴퓨터 구조 같은 수업에서 왜 그런지, 어떻게 그런지 공부하게 됩니다. 어떤 연산은 복잡도에 비해 빠르거나 느립니다.

주의 왜인지 정확히는 모르겠지만 Big-Theta를 의미하면서도 말은 Big-O로 말하는 이상한 Tradition이 있습니다. 저도 그 영향을 받았기 때문에 그렇게 쓰는 일이 많이 있습니다. (추측이 좀 섞여있지만) 사실 중요한 것은 알고리즘이 얼마나 빠른지이므로, Big-O가 가장 중요해서일 것입니다. 예로 $O(n^2)$ 알고리즘을 개발했다면, 이게 실제로 $\Theta(n \log^4 n)$ 인지 tight하게 prove하는 것보다는 ‘아무튼 $n^2$ 이상의 퍼포먼스를 보여준다’ 는 점이 중요하기 때문이 아닌가 합니다. $\Theta$ 를 최대한 사용하려고 노력하겠지만, 일부 그렇지 못한 경우가 있을 수 있습니다.

주의2 $f \in O(g)$ 를 의미하면서 무려 $f = O(g)$ 같은 Abuse of notation도 꽤 흔한 듯 합니다.

Additional topics and Problems

1. Amortized Analysis가 무엇인지 찾아보고, 어떨때 유용할지 생각해 보세요.

2. ($\bigstar$) 알고리즘 수업에서 배우는, Master Theorem이라는 정리가 있습니다.³ 몇가지 알려진 재귀식을 빠르게 해결할 수 있는 방법으로, 알아두면 알고리즘 분석에 많은 도움이 됩니다. 정리를 기술하면 다음과 같습니다.

   ---

   어떤 알고리즘이 $n$ 크기의 입력을 받았을 때, $n/b$ 크기의 입력 $a$개로 문제를 쪼개어 해결한 후, 이를 $f(n)$ 시간에 합친다고 하자. 즉, 시간 복잡도가 다음과 같다고 하자. \(T(n) = aT(n/b) + f(n)\) 이때, $c = \log_b a$ 라고 하자. 다음과 같은 경우, 이 점화식의 다음과 같은 해가 알려져 있다.

   1. $f(n) \in O(n^d),\ d < c$ : $T(n) \in \Theta(n^c)$

   2. $f(n) \in \Theta(n^c \log^k n)$ : Depends on value of $k$.

      • $k > -1$ : $T(n) \in \Theta(n^c \log^{k+1} n)$

      • $k = -1$ : $T(n) \in \Theta(n^c \log \log n)$

      • $k < -1$ : $T(n) \in \Theta(n^c)$

   3. $f(n) \in \Omega(n^d), d > c$ 이고, $^\exists k < 1 \st af(n/b)\geq kf(n)$ for large enough $n$ : $T(n) \in \Theta(f(n))$

   ---

   증명은 알고리즘 수업에서도 (아마도) 다루지 않겠지만, 다음과 같은 사실을 이용합니다. 수학에 관심이 많고 이런걸 보고 증명이 없으면 못 넘어가는 성격이라면 시도해 보세요.⁴
   점화식을 Recursion Tree 형태로 그리면 다음과 같은 사실을 쉽게 알 수 있습니다. \(T(n) = \sum_{i = 0}^{\log_b a} a^i f(n/b^i) + O(n^{\log_b a})\) 이제, 각 Case별로 조건을 나누고 침착하게 Bound를 잡으면 됩니다. 힌트를 조금 드리자면, 1번과 같은 조건을 해석하는 좋은 방법은 $f(n) \in O(n^{c - \epsilon})$ 이라고 생각하는 것입니다.