알고리즘이 얼마나 오래 실행되는지 추정해 보는 것이 유용한 경우가 많습니다. 물론 알고리즘을 그냥 구현해서 실행해 볼 수도 있지만, 이때 다음과 같은 문제가 생깁니다.
- 컴퓨터마다 실행 시간은 항상 다르게 나타납니다.
- 알고리즘이 실제로 실행될 데이터를 항상 미리 확보할 수 있는 것은 아닙니다.
- 때로는 실행하는 데 몇 시간, 심지어 며칠이 걸리는 알고리즘을 평가해야 할 때도 있습니다.
- 인생은 짧으므로, 여러 가지 알고리즘 선택지가 있다면 그중 어느 것이 더 빠를지 미리 예측하여 그것만 구현하고 싶어집니다.
이를 위해 첫 번째 근사로서 알고리즘의 연산 횟수를 추정해 봅시다. 그러면 정확히 어떤 연산을 셀 것인지에 대한 의문이 생깁니다. 한 가지 방법은 모든 기본 연산을 고려하는 것입니다.
- 수에 대한 산술 연산:
+, -, *, / - 수 비교:
<, >, <=, >=, ==, != - 대입:
a[0] = 3
이때 단순히 줄 수를 세는 것만이 아니라, 언어 자체에서 일부 개별 기능이 어떻게 구현되어 있는지도 고려하는 것이 중요합니다. 예를 들어, 파이썬에서 배열 슬라이스(array[3:10])는 해당 배열을 복사하므로, 이 슬라이스는 7번의 기본 연산이 필요합니다. 또한 예를 들어 swap은 3번의 대입으로 구현할 수 있습니다.
연습 문제. 버블 정렬, 선택 정렬, 삽입 정렬, 계수 정렬에서 최악의 경우 비교와 대입의 정확한 횟수를 세어 보십시오. 이는 배열의 길이인 $n$에 의존하는 어떤 공식이어야 합니다.
모든 기본 연산을 빠짐없이 고려하려면, 예를 들어 for 루프 안에서 1이 몇 번 더해졌는지도 세어야 합니다. 또한 예를 들어 n = len(array)라는 줄도 하나의 동작입니다. 따라서 이것들을 모두 세더라도 이 알고리즘들 중 어느 것이 더 빠르게 동작하는지 바로 알 수 있는 것은 아닙니다. 공식들을 비교하기가 어렵기 때문입니다. 그래서 이 공식들을 다음과 같이 단순화하는 방법을 고안하고자 합니다.
- 최종 실행 시간에 크게 영향을 주지 않는 정보는 고려할 필요가 없어야 합니다;
- 큰 수에 대해 여러 알고리즘의 실행 시간을 쉽게 추정할 수 있어야 합니다;
- 특정 입력 데이터에 어떤 알고리즘이 더 적합한지 알고리즘끼리 쉽게 비교할 수 있어야 합니다.
이를 위해 고안된 것이 O-표기법으로, 정확한 실행 시간 대신 점근적 실행 시간을 나타냅니다(흔히 간단히 점근이라고도 부릅니다).
정의. $f(n)$을 어떤 함수라고 합시다. 어떤 상수 $c$와 $n_0$이 존재하여 모든 $n \geq n_0$에 대해 $g(n) < c \cdot f(n)$이 성립하면, 함수 $g(n) = O(f(n))$이라고 합니다.
예를 들면 다음과 같습니다.
- $\frac{n}{3} = O(n)$
- $\frac{n(n-1)(n-2)}{6} = O(n^3)$
- $1 + 2 + 3 + \ldots + n = O(n^2)$
- $1^2 + 2^2 + 3^2 + \ldots + n^2 = O(n^3)$
- $\log_2{n} + 3 = O(\log n)$
- $179 = O(1)$
- $10^{100} = O(1)$
알고리즘 분석의 맥락에서 “알고리즘이 $O(f(n))$번의 연산으로 동작한다"라는 표현은 어떤 $n$부터는 알고리즘이 수행하는 연산이 $c \cdot f(n)$번을 넘지 않는다는 뜻입니다.
이러한 표기법을 사용하면 다음과 같이 말할 수 있습니다.
- 버블 정렬은 $O(n^2)$에 동작합니다;
- 선택 정렬은 $O(n^2)$에 동작합니다;
- 삽입 정렬은 $O(n^2)$에 동작합니다.
- 계수 정렬은 $O(n + m)$에 동작합니다.
이 표기법은 짧고 이해하기 쉬우며, 상수 곱셈이나 상수 덧셈에 영향을 받지 않는다는 점에서 편리합니다. 예를 들어 어떤 알고리즘이 $O(n^2)$에 동작한다면, 이는 그 알고리즘이 $n^2$, $n^2 + 3$, $\frac{n(n-1)}{2}$, 심지어 $1000 \cdot n^2 + 1$번의 연산으로 동작한다는 뜻일 수 있습니다. 중요한 것은 함수가 $n^2$처럼 행동한다는 점, 즉 $n$이 커질 때 어떤 이차 함수처럼 증가한다는 점입니다. $n$을 10배로 늘리면 프로그램의 실행 시간은 대략 100배로 늘어납니다.
O-표기법의 주요 장점은 swap에 연산이 몇 개 들어가는지, 대입·비교·반복문을 따로 세어야 하는지와 같은 모든 논의가 필요 없어진다는 점입니다. 이러한 질문에 대한 답이 무엇이든 결과는 상수배만큼만 달라지므로, 알고리즘의 점근적 실행 시간은 변하지 않습니다.
그래서 앞의 세 정렬을 이차 정렬이라고 부릅니다. 이 정렬들은 $O(n^2)$ 시간에 동작합니다. 계수 정렬은 훨씬 빠르게 동작할 수 있습니다. 계수 정렬은 $O(n + m)$ 시간에 동작하며, $m \leq n$이면 이는 아예 선형 함수 $O(n)$입니다.