[ Open Data Structures ] - Asymptotic Notation

Asymptotic Notation

자료구조를 분석함에 있어서 다양한 작업(Operation)들의 Running time에 대해 논할 때가 있다. 당연히 정확한 Running time은 각각 컴퓨터에 따라 다르게 나타난다. 우리가 어떤 Operation의 Running time에 대해 이야기 할 때는 Operation 도중에 수행되는 컴퓨터의 지시(Computer instructions)의 수를 이르는 것이다. 아주 간단한 코드에서도 이 양[量]은 정확하게 계산해내기 힘들다. 따라서 Running time을 정확하게 계산하는 대신에 우리는 소위 말하는 Big-Oh notation을 사용하기로 한다. 어떤 함수 f(n)에 대해서 O(f(n))은 다음과 같은 함수의 집합을 이르는 것이다.

도표로 생각을 해보면 이 집합은 어떤 수 n이 충분히 클 때, 함수 n * f(n)이 함수 g(n)의 함수값보다 커지는 함수 g(n)의 집합이다. (다르게 말하면 충분히 큰 n이 존재할 때, n * f(n)보다 작은 함수 g(n)의 집합)

일반적으로 함수를 간략화하기 위해서 Asymptotic notation을 사용한다. 예를 들어서 5nlogn+8n-200을 O(nlogn)형태로 쓰는 것과 같다. 이는 다음과 같은 과정에 의해 보일 수 있다.

이는 곧 함수 f(n) = 5nlogn + 8n - 200이 c = 13이고 n_0 = 2일 때, O(nlogn)의 집합 안에 포함된다는 뜻이다. Asymptotic notation을 사용할 때 적용할 수 있는 많은 다양한 기법들이 존재한다. c1 < c2일 때 

그리고 모든 상수 a, b, c > 0에 대해서 

이 포함관계들은 어떤 양의 수를 곱하더라도 만족한다. 예를 들어서 어떤 임의의 양수 n을 곱하면 다음과 같다.

길고도 오래된 전통에 의해서 이 notation을 자주 사용하게 될 것인데, 예를 들면 f_1(n) = O(f(n))처럼 사용한다. 조금 더 엄밀하게 말하면 f_1(n)이 O(f(n))의 집합에 포함된다는 것을 뜻한다. 지금껏 그랬듯 앞으로도 "이 Operation(작업)의 Running time O(f(n))이다."라는 말을 "이 operation(작업)의 Running time은 O(f(n))의 집합의 원소다."라는 말처럼 쓸 것이다. 

이 Asymptotic notation을 사용할 때 있어서 한 가지 이상한 Statements를 짚고 넘어가자면 다음과 같은 것이 있다.

이 식을 더 엄밀하게 쓰면 다음과 같다.

O(1)이라는 표현은 다른 문제를 촉발한다. 이 표현엔 변수가 존재하지 않기 때문에 어떤 변수가 충분히 커지고 있는 것인지 명확히 알아내기 힘들 수 있다. 맥락이 없다면 사실상 알아낼 수 없다. 이 예문에서 우리는 유일한 변수가 n이기 때문에 이 statement는 다음과 같이 해석해야 한다는 것을 유추할 수 있다.

Big-Oh notation은 Computer Science에서 특별히 새로운 개념은 아니다. 1894년에 수이론학자인 Paul Bachmann에 의해 사용되었으며 컴퓨터 알고리즘을 기술하는데 있어서 굉장히 유용하게 쓰이고 있다. 다음에 주어진 간단한 코드를 살펴보자.

이 코드의 1회 실행은 다음과 같은 절차들을 포함한다.

1. 한 번의 할당(Assignment, int i = 0;).
2. n+1번의 비교 (i < n)
3. n번의 증가 (i++)
4. n번의 배열 offset 계산 (a[i])
5. n번의 간접할당 (a[i] = i)

따라서 Running time을 T(n)이라고 할 때, 다음과 같이 쓸 수 있다.

이때, a,b,c,d,e는 각각 할당, 비교, 증가연산, Offset연산, 간접할당 연산을 수행할 때 걸리는 시간을 나타내는 임의의 상수이며 이들은 코드를 실행하는 기계에 의존적이다. 그러나 이런 식으로 꼴랑 두 줄의 코드의 Running time을 계산하게 되면 복잡한 코드나 알고리즘의 Running time을 추적하는 것은 상당히 귀찮은 작업이 될 것이다. 따라서 Big-Oh Notation을 사용하면 다음과 같이 다시 쓸 수 있다.

이렇게 쓰는 편이 훨씬 간단할 뿐만이 아니라 오히려 더 충분한 정보를 제공하기도 한다. 왜냐하면 위의 예제를 통해 언급했던 것처럼 상수 a,b,c,d,e에 Running time이 의존한다는 사실은 서로 다른 두 개의 Running time이 존재할 경우에 상수 값을 알지 못하면 어떤 것이 더 빠른지 비교할 수 없다는 바를 시사하기 때문이다. 혹시라도 각 상수의 정확한 값을 알게 된다고 하더라도 그 Running time은 해당 기계에서만 유효한 것이 된다.

Big-Oh notation은 복잡한 함수를 더 높은 차원에서 해석할 수 있도록 도와준다. 만일, 서로 다른 두 개의 알고리즘이 같은 Running time을 갖고 있다면 어떤 알고리즘이 더 빠른지 분별하기 어려울 것이다. 한 알고리즘이 어떤 기계에서 빠르게 작동했다면 다른 기계에서 느릴 수 있고 다른 알고리즘은 해당 기계에서 빠르게 동작할 수도 있는 것이다. 반면에, 서로 다른 두 알고리즘이 다른 Big-Oh Running time을 갖고 있다면 충분히 큰 수 n에 대해서 어떤 임의의 기계에서 작동시키더라도 더 작은 Running time을 가진 알고리즘이 빠를 것이라는 사실을 추측할 수 있다.

두 알고리즘에 대해서 어떤 것이 더 빠를 것인지를 추측하는데 있어서 도움이 될 만한 도표가 있다. 예를 들어서 f1(n) = 15n이고 f2(n) = 2nlogn일 경우를 생각해본다.

f1(n)은 복잡한 선형 시간 알고리즘인 반면에 f2(n) 분할정복 패러다임에 근거한 상당히 간단한 알고리즘일 수도 있다. 이 도표가 시사하는 바는 비록, 작은 수 n에 대해서는 f1(n)이 f2(n)보다 훨씬 느린 것처럼 보이지만 충분히 큰 n에 대해서는 그 반대가 참이라는 점이다. 결과적으로 f1(n)이 f2(n)를 엄청난 차이를 남기며 이기게 된다(속도면에서). 사실, 위에서 각 Big-Oh notation의 포함관계를 설명할 때 예측할 수 있는 결과였다. O(n)은 O(nlogn)에 포함되기 때문에 이러한 결과를 얻을 수 있었던 것이다.

드문 경우에 대해서 앞으로 두 개 이상의 변수에 대해서 Asymptotic notation을 사용할 것이다. 이에 관해서는 마땅히 정석이라고 할만한 것이 없어 보이지만 다음과 같은 정의라면 앞으로 부족함이 없을 것이다.