알고리즘은 보아야만 믿을 수 있다.

An algorithm must be seen to be believed.

— 도날드 크누스Donald Knuth (1968)

알고리즘algorithm은 프로그래밍에서 흔하게 접하게 되는 용어입니다. 이 알고리즘이 무엇이냐는 질문에는 ‘문제를 풀기 위한 절차’라고 답할 수 있겠지만, 이 이상 명확하게 말하기는 쉽지 않습니다. 왜냐면 그것이 정확히 무엇인지 합의된 바가 없기 때문입니다.

그 대신 알고리즘의 특징은 살펴볼 수 있습니다. 앞으로의 내용을 통해, 알고리즘을 수행하는 가상의 기계를 생각해보고 얼마나 많은 일이 기계로 불가능한지 보게 될 것입니다. 그리고 그런 기계가 얼마나 많은 동작을 수행하는지 세봄으로써, 소요 시간을 예측하는 방법을 알 수 있게 됩니다.

알고리즘이란

먼저 알고리즘이란 어떻게 생겼는지 소개하고자 하는데, 알고리즘하면 대표적인 예시가 있습니다. 기원전에 유클리드Euclid가 소개한 것으로 알려진 유클리드 알고리즘Euclid’s algorithm입니다. 이 알고리즘은 두 수의 최대 공약수를GCD, greatest common divisor를 구하는 문제의 답을 구하는 절차입니다.

예를 들어, 두 숫자가 $735$ 와 $315$ 로 주어졌다면, 다음과 같이 최대 공약수를 구합니다.

첫 번째 숫자 $735$ 를 두 번째 수 $315$ 로 나눈 나머지 $105$ 를 구합니다.
나머지가 $0$ 이 아니므로, 두 번째 수 $315$ 와 나머지 $105$ 를 각각 첫 번째와 두 번째 것으로 하고 이 과정을 반복합니다.
다시 나머지를 구했더니 $0$ 이므로, 나눈 숫자 $105$ 를 최대 공약수로 하고 끝냅니다.

\begin{align*} &\begin{aligned} 735 \bmod 315 &= 105 \\ 315 \bmod 105 &= 0 \end{aligned} \\ \therefore{} &\textrm{GCD}\,(735, 315) = 105 \end{align*}

최대 공약수는 두 수가 공통으로 가진 소수를 구해 찾을 수도 있습니다. 여기서는 $735 = 3{\cdot}5{\cdot}7^2$ 이고, $315 = 3^2{\cdot}5{\cdot}7$ 이므로, 똑같은 답으로 $105 = 3{\cdot}5{\cdot}7$ 을 구하게 됩니다. 하지만 유클리드 알고리즘은 이렇게 소수를 찾는 대신 나머지 연산을 이용합니다. 그래서 나중에 보겠지만, 두 숫자가 커질수록 유클리드 알고리즘이 비교적 더 빠른 방법이 됩니다.

이 절차는 가상의 프로그래밍 언어로 다음과 같이 표현할 수 있습니다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

$r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

만약

r = 0

이면

리턴 $n$

아니면

리턴 유클리드 알고리즘( $n$ , $r$ )

실제 프로그래밍 코드는 아니지만 이에 가깝게 표현했기 때문에 수도코드pseudocode라고 부릅니다.

이 알고리즘은 입력값으로 $m$ 과 $n$ 을 받아, 첫 번째 줄에서 나머지 연산을 하고 그 결과를 $r$ 에 대입합니다. 여기서는 화살표(‘ $\leftarrow$ ’)가 대입의 의미를 나타냅니다. 또한 마지막 줄에 자기 자신을 다시 언급하는데, 이것을 재귀적인recursive 알고리즘이라고 부릅니다.

이처럼 알고리즘이란 기계적으로 따를 수 있는 절차, 또는 특별한 지식 없이 어떤 사람이라도 따를 수 있는 절차라고 할 수 있습니다. 그러면 어떻게 만들어야 그런 절차라고 부를 수 있을까요? 좀더 구체적으로 제약 사항을 나열해보자면 이렇습니다.

알고리즘은 유한한 단계로 구성되어야 한다. (무한히 많이 있어선 안 된다.)
각 단계가 애매하게 해석될 여지 없이 분명해야 한다.
펜과 종이만 이용해 (즉 특별한 지식을 필요로 하지 않고) 단계를 따를 수 있어야 한다.

이 기준에 비추어 볼 때, 유클리드 알고리즘은 정말로 알고리즘인 것 같습니다.

하지만 이런 설명이 만족스럽지 않을 수 있습니다. 각 단계가 ‘명확해야 한다’는 것은 어느 정도로 해야할까요? ‘특별한 지식’이 없어야 한다는 것도 어느 정도까지 일까요? 물론 각자가 어느 정도의 기준을 갖고 판단할 수도 있겠지만, 곧 소개할 내용처럼 한 가지 기준을 마련해볼 수도 있습니다.

알고리즘의 구체적인 표현

1900년대 초에는 알고리즘이라는 이름 대신 효과적인 방법effective method이라고 부르곤 했습니다. (여기서 ‘효과적’이란 ‘기계적’이라는 뜻이지만, 적절한 번역을 찾지 못했다는 변명을 남겨두겠습니다.) 그리고 다소 불명확한 이 개념을 좀 더 구체화하려는 시도가 있었는데, 그 중 하나는 긴 테이프가 달린 가상의 기계를 떠올린 것이었습니다. 이 기계는 아주 단순해서, 할 수 있는 일이라곤 테이프에 적힌 문자를 하나씩 읽거나 쓰고, 다른 문자를 읽기 위해 테이프를 옆으로 움직이는 것이 전부였습니다.

1930년대에 앨런 튜링Alan Turing이 떠올린 이것은 튜링 머신Turing machine이라고도 부릅니다. 또한 계산이라는 것을 수학적으로 모델링한 것이기 때문에 계산 모델model of computation이라고도 합니다.

당시 튜링은 기계로 계산할 수 있는 것을 효과적으로 계산 가능한effectively computable 것이라고 불렀습니다. 중요한 것은, 어떤 기계를 만들더라도, 그 기계로 효과적으로 계산 가능한 것은 튜링 머신으로도 그렇다고 주장한 것입니다. 다시 말해 튜링 머신이 할 수 없는 일은 다른 기계로도 할 수 없다는 뜻입니다.

처치-튜링 명제Church-Turing thesis라고 부르는 이 주장은 지금까지 남아서 컴퓨터 과학의 기반을 이루는 가설이자 믿음으로 자리잡고 있습니다. 튜링 머신은 앞서 본 것처럼 단순하지만, 이것보다 더 많은 것을 할 수 있는 기계를 여태껏 아무도 생각해내지 못했기 때문입니다.

이런 튜링 머신이 따르는 절차를 알고리즘이라고 볼 수 있을까요? 예를 들어, 다음은 ‘안녕’을 읽었을 때 초록 불을, 그렇지 않으면 빨간 불을 켜도록 만듭니다.

글자가 ‘안’이면 다음 글자를 읽는다. 그렇지 않으면 빨간 불을 켠다.
글자가 ‘녕’이면 초록 불을 켠다. 그렇지 않으면 빨간 불을 켠다.

sample turing machine program — 그림 2. ‘안녕’을 읽으면 초록 불을 켜고, 아니면 빨간 불을 켜는 튜링 머신.

그러면 이 절차는 튜링 머신의 단순함 덕분에 자연스럽게 알고리즘의 특징을 갖게됩니다.

실제로 두 단계 뿐인 유한한 절차만 가집니다.
튜링 머신이 할 수 있는 일은 기껏해야 테이프의 문자를 조작하는 것 뿐이므로, 각 단계는 실제로 명확하게 표현됩니다.
튜링 머신에는 특별히 주입된 지능이라고 할 것이 없습니다. 따라서 실제로 특별한 지식이 필요하지 않습니다.

역사적으로도 이 튜링 머신을 비롯한 계산 모델 덕분에 알고리즘의 구체적인 표현이 가능해졌습니다. 이는 계산 이론theory of computation과 같은 컴퓨터 과학의 분야에서, 기계로 할 수 있는 일이 무엇인지 본격적으로 연구할 수 있는 밑받침이 됐습니다. 그 대표적인 성과로 계산 복잡도computational complexity라는 개념을 통해 알고리즘의 성능을 비교할 수 있는 기준이 마련됐습니다.

계산 복잡도

알고리즘이 풀고자 하는 문제의 답이라면, 이런 질문을 해볼 수 있습니다.

어떤 문제가 있을 때, 이를 풀 수 있는 방법, 즉 알고리즘이 항상 있는가?
있다면, 얼마나 많은 시간과 기억 장치가 필요한가?

여기에는 이미 많은 결과가 나왔고, 정리하자면 이렇습니다.

세상의 모든 문제를 모아놓고 아무거나 골랐을 때, 그것을 푸는 알고리즘이 존재할 확률은 0%이다. (즉 풀 수 없는 문제가 압도적으로 더 많다.)
풀 수 있는 문제 중에서도, 빠르게 풀 수 없어서 현실적으로 풀기 힘든 문제가 존재한다.
빠르게 풀 수 없는 문제 중에서는, 정말로 빠르게 풀 수 없는 것인지조차 모르는 문제가 존재한다.

따라서 어떻게 보면, 문제를 빠르게 풀 수 있다는 것은 큰 행운일지도 모릅니다. 그리고 이런 문제는 트랙터블tractable한 문제라고도 부릅니다.

problems diagram — 그림 3. 문제들과 풀 수 있는 문제, 트랙터블한 문제 간의 관계.

똑같은 문제에는 여러 알고리즘이 존재할 수 있습니다. 그중에 더 나은 알고리즘을 가리기 위해, 얼마나 빠르게 풀 수 있는지를 기준으로 삼기도 합니다.

그런데 여기서 ‘빠르다’는 의미를 가다듬을 필요가 있습니다. 실제 소요되는 시간으로 빠르다는 것을 잰다면, 알고리즘 자체가 느리기 때문인지, 알고리즘을 수행하는 기계가 느리기 때문인지 구분하기가 쉽지 않습니다. 따라서 기계가 물리적으로 어떻게 만들어졌느냐에 상관 없이, 알고리즘 자체가 요구하는 소요 시간을 어떻게 알 수 있느냐가 중요한 문제입니다.

시간 복잡도

알고리즘은 그 단계가 얼마나 많이 수행되느냐에 따라 필요한 시간이 달라진다고 볼 수 있습니다. 따라서 알고리즘의 수행 시간running time, 또는 시간 복잡도time complexity $T$ 라는 것을 수행 단계 개수라고 정의해봅시다.

앞에서 언급한 유클리드 알고리즘을 다시 가져와보겠습니다. 대신 이번에는 각 단계에 순번을 매겨놨습니다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

[단계 1] $r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

[단계 2] 만약 $r = 0$ 이면

[단계 3] 리턴 $n$

아니면

[단계 4] 리턴 유클리드 알고리즘( $n$ , $r$ )

여기서 입력값이 $m = 4$ , $n = 2$ 라고 해봅시다. 그러면 총 몇 개의 단계를 거칠까요? (한번 세보세요.)

나머지 $r = 0$ 을 얻고 $n = 2$ 를 리턴할 때까지 총 세 단계를 거치게 됩니다. 따라서 $T = 3$ 의 시간 복잡도를 가진다고 할 수 있습니다. ( $m$ 이 $n$ 의 배수인 경우에 항상 $T = 3$ 이 되는지 확인해보세요.)

이 시간 복잡도가 커질 수록 소요 시간 또한 길어질 것으로 예상할 수 있을 것입니다. 따라서 시간 복잡도는 알고리즘의 소요 시간을 예측하기 위한 도구가 됩니다.

시간 복잡도를 결정하는 것들

방금의 유클리드 알고리즘 예시로부터 두 가지 사실을 알 수 있습니다.

다른 입력이 주어지면, 다른 시간 복잡도를 얻게 됩니다. 즉 시간 복잡도는 입력값에 의존하는 함수입니다.
모든 단계를 똑같이 하나로 셌습니다. 각 단계가 더 이상 나눠서 수행할 수 없는 기본적인 동작이라고 암묵적으로 가정한 것입니다.

두 번째 사실은, 시간 복잡도는 그것을 수행하는 계산 모델에도 의존한다는 뜻을 담고 있습니다. 달리 말하면, ‘기본적인 동작’으로서 수행하길 바라는 것들이 곧 우리가 계산 모델에 가하는 제약 사항이 되는 것입니다.

사실 이 점은 유클리드 알고리즘을 구체적인 문장으로 표현할 때부터 그대로 나타났습니다. 즉 다음 단계를 ‘기본적인 동작’으로서 수행하기를 바란 것입니다.

[단계 1] $r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

풀어서 말하면, 나머지 연산과 변수 접근을 계산 모델에서 즉각적으로 수행할 수 있다고 가정한 것입니다. 하지만 이것은 튜링 머신과는 명백히 다르기 때문에, 다른 계산 모델이 필요하게 됩니다.

RAM 계산 모델

변수의 값에 빠르게 접근하는 랜덤 엑세스random access는 튜링 머신으로 불가능합니다. 멀리 떨어진 데이터를 읽으려면 테이프를 움직여야 하기 때문입니다. 따라서 앞서 예로 든 유클리드 알고리즘이 튜링 머신을 위한 것이었다면, 테이프 조작을 위한 단계가 추가되어서 알고리즘이 지금보다 길어졌을 것입니다.

한편, RAMrandom access machine이라고 부르는 계산 모델은 튜링 머신에 랜덤 엑세스가 있다고 생각한 것입니다. 이것이 지금의 컴퓨터에 좀더 가깝기 때문에 오늘날 알고리즘을 분석할 때 더 흔히 사용됩니다.

하지만 이런 랜덤 엑세스가 가능하더라도, 튜링 머신이 풀 수 없는 문제를 풀 수 있게 되는 것은 아닙니다. 그랬다면, 다른 기계가 풀 수 있다면 튜링 머신도 풀 수 있다고 주장한 처치-튜링 명제를 버려야 했을 것입니다.

여태까지의 내용은 알고리즘의 시간 복잡도를 말하기 전에 계산 모델을 가정해야 하는 이유가 됩니다. 그래야 계산 모델의 ‘기본적인 동작’을 바탕으로 알고리즘을 표현할 수 있기 때문입니다. 알고리즘을 다루는 여러 책에서 RAM 모델과 같은 것을 먼저 언급하는 이유이기도 합니다. 여기서도 앞으로 이 RAM 모델을 기반으로 알고리즘을 표현할 것입니다.

알고리즘 분석: 소요 시간 예측하기

앞서 언급한 것처럼, 시간 복잡도는 입력값에 의존합니다. 그런데 입력값에 따른 시간 복잡도를 그래프로 그렸을 때, 이것이 반드시 부드러운 곡선을 그릴 것이라는 보장은 없습니다.

유클리드 알고리즘 예시에서 봤던 것처럼, 한 쪽이 다른 쪽의 배수가 되는 경우에 시간 복잡도는 $T=3$ 에 불과합니다. 나머지 경우에서는 입력값이 커짐에 따라 불규칙한 패턴을 나타냅니다.

euclid algorithm time complexity — 그림 4. 유클리드 알고리즘의 입력값에 따른 시간 복잡도 예시.

따라서 좀더 제한된 경우의 시간 복잡도를 분석하기 위해, 다음과 같은 특별한 종류의 입력값에 초점을 둡니다.

최악의 경우worst case: 시간 복잡도가 가장 커지는 경우
최선의 경우base case: 시간 복잡도가 가장 작아지는 경우
평균의 경우average case: 평균적인 시간 복잡도가 필요한 경우

여기서 주로 관심을 갖게 되는 것은 최악의 경우입니다. 왜냐면 최악의 상황에도 보장되는 소요 시간을 알 수 있기 때문입니다.

함수 표기법

입력값 $n$ 에 따른 시간 복잡도 $T(n)$ 이 있다고 해봅시다. 이런 함수를 분석할 때, $n$ 이 커짐에 따라 함수 $T(n)$ 이 어떻게 변하는지 구하는 것을 어심토틱asymptotic 분석이라고도 합니다. 이때 $T(n)$ 에서 차수가 낮은 항lower-order terms은 관심사가 아닙니다. 이를 위해 틸다tilde(‘ $\sim$ ’)를 이용해 차수가 낮은 항을 버린 근사식을 표현하곤 합니다.

4n^{2\mathstrut} + 5n + 6 \sim 4n^2

좀더 간단한 표현으로 빅오big-O를 사용할 수도 있습니다. 빅오는 함수의 집합이고 $O(f(n))$ 로 표기합니다. 수학적인 정의가 따로 있지만, $f(n)$ 보다 빠르게 커지지 않는 함수의 집합이라고 대신 설명하겠습니다. 예를 들면 다음이 성립합니다.

\begin{align*} 4n^{2\mathstrut} + 5n + 6 &= O\!\left(n^2\right) \\ 5n + 6 &= O(n) \end{align*}

집합 관계의 표현으로서 ‘ $\in$ ’ 기호를 쓸 수도 있겠지만 등호(‘ $=$ ’)가 흔히 사용됩니다.

한편, 빅오는 다음 표현도 성립합니다.

4n^{2\mathstrut} + 5n + 6 = O(n^{999})

왜냐면 $n^2$ 은 $n^{999}$ 보다 빠르게 커지지 않기 때문입니다. 이것이 의미하는 바는 빅오는 최고차항의 지수와는 관련이 없을 수 있다는 것입니다.

반대의 것으로 빅오메가big-omega가 있습니다. $g(n) = \Omega(f(n))$ 라는 것은 $g(n)$ 이 적어도 $f(n)$ 만큼은 빠르게 증가한다는 뜻입니다.

\begin{align*} 4n^{2\mathstrut} + 5n + 6 &= \Omega\!\left(n^2\right) \\ 5n + 6 &= \Omega(n) \\ \end{align*}

한편, $n^2$ 은 $1 \,(=n^0)$ 보다 차수가 크므로 다음 또한 성립합니다.

4n^{2\mathstrut} + 5n + 6 = \Omega(1)

만약 $g(n) = O(f(n)) = \Omega(f(n))$ 이라면, 빅세타big-theta로 이 사실을 표현할 수 있습니다.

4n^{2\mathstrut} + 5n + 6 = \Theta(n^2)

사람마다 선호하는 표기법이 다를 수 있기 때문에, 자료마다 다른 표기법 사용을 볼 수 있을 것입니다. 개인적인 의견이지만 대체로 선호되는 표기법은 빅세타처럼 쓰이는 빅오인 것 같습니다. 즉 표기는 빅오로 하되 그 실질적인 의미는 빅세타의 것을 따르는 혼동스러운 표기법입니다. 하지만 $O(n^2)$ 에 속하는 함수가 반드시 $n^2$ 항을 가질 필요는 없다는 사실을 기억해야 합니다.

유클리드 알고리즘 분석하기

앞에서 예로 들었던 유클리드 알고리즘의 시간 복잡도를 구해봅시다.

유클리드 알고리즘 ( $m$ , $n$ ) // 두 수의 최대 공약수를 리턴

$r \leftarrow$ $m$ 을 $n$ 으로 나눈 나머지

만약

r = 0

이면

리턴 $n$

아니면

리턴 유클리드 알고리즘( $n$ , $r$ )

최선의 경우는 시간 복잡도가 $\Theta(1)$ 임을 쉽게 알 수 있습니다. 이는 입력값에 상관 없이 항상 일정한 개수의 단계만 거친다는 뜻이기도 합니다. 실제로, $n=1$ 인 경우를 최선의 경우라고 했을 때, 알고리즘은 세 단계를 거치고 재귀 없이 바로 리턴합니다. 따라서 시간 복잡도 $T(m, n)$ 은 이렇게 표현할 수 있습니다.

T(m, 1) = 3 = \Theta(1)

하지만 나머지 두 경우는 각각 다른 이유 때문에 구하기가 쉽지 않습니다.

평균의 경우는 무엇이 평균적인 입력값인지 정하기가 어렵습니다. ( $1$ 부터 $\infty$ 사이에 어느 숫자가 평균적일까요?) 따라서 이 경우는 생략합시다.

최악의 경우는 수학적으로 어렵습니다. (한번 구해보세요.) 먼저, 유클리드 알고리즘의 시간 복잡도는 다음과 같은 점화식recurrence relation을 갖습니다.

T(m, n) = \begin{cases} T(n, r) + 3 &\textrm{($r > 0$)} \\ 3 &\textrm{($r = 0$)} \end{cases}

이를 통해 $T$ 가 다음처럼 알고리즘의 재귀 횟수 $k$ 로 결정된다는것을 알 수 있습니다.

\tag{Eq.1} T(k) = 3(k+1) = \Theta(k)

따라서 재귀 횟수 $k$ 가 얼마인지 계산해야 합니다.

한편, 무엇이 최악의 입력값인지 생각해보면, 피보나치 수Fibonacci number가 등장합니다. 피보나치 수란 다음과 같이 이전 두 수를 더해 나열한 숫자를 말합니다.

1, 1, 2, 3, 5, 8, 13, 21, \dots

유클리드 알고리즘은 두 수가 연이은 피보나치 수일 때 가장 많이 재귀를 수행하게 됩니다. 재귀의 입력값이 계속 서로소relatively prime가 되기 때문입니다. 예를 들어, $m = 13$ , $n = 8$ 이 입력으로 주어졌다고 해봅시다. 그러면 유클리드 알고리즘은 다음과 같은 입력값들로 재귀를 수행합니다.

(m, n) = (13, 8) \rightarrow (8, 5) \rightarrow (5, 3) \rightarrow (3, 2) \rightarrow (2, 1)

이 예시에서 두 가지를 알 수 있습니다.

다음 재귀의 입력값은 바로 이전의 피보나치 수가 됩니다. 즉, $n$ 번째 피보나치 수를 $f_n$ 이라고 적는다면, 입력값이 $(f_{n+1}, f_{n}) \rightarrow (f_{n},f_{n-1})$ 로 이어지게 만듭니다.
입력값 $(f_{n+3}, f_{n+2})$ 은 총 $n$ 번의 재귀를 만듭니다.

피보나치 수는 대략 지수 함수만큼 빠르게 커집니다. 정확히는 황금비golden ratio $\varphi = (\sqrt{5}+1)/2$ 에 대해, $f_{n+2} \sim \varphi^n/\sqrt{5}$ 의 속도로 커집니다. 이로부터 재귀 횟수 $n = \Theta(\lg{f_{n+2}})$ 을 얻습니다.

그런데 로그 값은 숫자가 몇 자리인지 나타내므로, 재귀 횟수는 $f_{n+2}$ 이 몇 자리 숫자인지에 따라 결정이 된다고 볼 수 있습니다. 사실 똑같은 결과가 정수론number theory에서 라메의 정리Lamé’s Theorem라는 이름으로 있습니다. 이를 참고하면, 입력값 중 작은 쪽을 $\min(m, n)$ 라고 했을 때, 재귀 횟수는 그 로그에 비례하므로, $\textrm{Eq.1}$ 에서 다음 결과를 얻습니다.

T(m, n) = \Theta(\lg \min(m, n))

이처럼 단순해 보이는 알고리즘도 시간 복잡도 분석이 비교적 까다로울 수 있습니다.

그렇다면 이 분석이 정말로 실제 소요 시간을 예측할까요? 직접 알고리즘을 구현해보고 시간을 재서 검증해봅시다.

구현을 통해 검증하기

유클리드 알고리즘을 실제로 구현할 차례입니다. 여기서는 자바Java를 프로그래밍 언어로 선택하겠습니다. 그리고 테스트를 통해 알고리즘이 올바르게 동작하는지 확인하고, 실제로 소요 시간을 측정해보겠습니다.

구현과 테스트

유클리드 알고리즘의 수도코드를 다음과 같이 자바 코드로 옮기겠습니다.

public class Euclid {
  static public int getGCD(int m, int n) {
    // handle bad inputs
    if (m <= 0 || n <= 0) {
      return 0;
    }

    int r = m % n;
    if (r == 0) {
      return n;
    }

    return Euclid.getGCD(n, r);
  }
}

여기선 잘못된 입력값을 처리하기 위한 코드를 맨 위에 추가했습니다. 예외 처리를 위해 다른 방법을 썼을 수도 있겠지만, 여기선 조용히 0을 리턴하는 것으로 대신했습니다.

이 구현이 원하는대로 동작하는지 확인하기 위해 유닛 테스트unit test를 작성하겠습니다. 이를 위해 다음과 같이 JUnit 5 프레임워크를 사용해서 테스트 케이스를 작성합시다. 실행해보면 통과하는 테스트입니다.

  @Test
  public void testLargeNums() {
    int m = 200000000;
    int n = 100000000;
    int gcd = Euclid.getGCD(m, n);

    assertEquals(100000000, gcd);
  }

소요 시간 측정과 시간 복잡도 검증

소요 시간을 직접 측정해서, 최악의 경우의 시간 복잡도를 검증해봅시다. 여기선 간단히 일곱 개의 경우에 대해 구했습니다.

elapsed time plot — 그림 5. 입력값에 대한 소요 시간. 직선은 회귀선.

위 그래프에서 데이터 사이에 선형적인 관계를 볼 수 있습니다. 가로 축은 로그 스케일이기 때문에, 소요 시간이 $\lg\min(m, n)$ 에 비례합니다.

이로부터 분석을 통해 구했던 시간 복잡도가 실제 소요 시간과 비슷하다고 결론을 내릴 수 있을 것입니다. 실제 컴퓨터와 가까운 계산 모델인 RAM 모델로부터, 알고리즘에서 시간 복잡도를 적절히 구했다는 의미로 이해할 수 있습니다. 하지만 일치하지 않을 수도 있습니다. 실제 컴퓨터는 계산 모델보다 훨씬 더 복잡한 기계이기 때문입니다.

복잡도 클래스

앞서 유클리드 알고리즘이 최악의 경우에 시간 복잡도로 $\Theta(\lg \min (m, n))$ 을 갖는 것을 보았습니다. 즉 소요 시간이 대략 로그 함수를 따른다고 볼 수 있습니다.

하지만 어떤 알고리즘은 시간 복잡도가 $T(n) = n^2 + 3$ 과 같이 다항 함수polynomial function일 수도 있습니다. 이 경우, 알고리즘이 다항 시간polynomial time을 가진다고 말합니다. 다시 말해, 시간 복잡도가 $O(n^k)$ 꼴이면 다항 시간 알고리즘에 해당합니다. 한편, 로그 함수 $\lg n$ 은 다항 함수는 아니지만 $O(n)$ 에 속하기 때문에, 이름에 약간 거짓말이 있는 것 같지만 유클리드 알고리즘도 다항 시간 알고리즘에 속합니다.

어떤 문제를 다항 시간 알고리즘으로 풀 수 있다면, 그 문제를 $\textsf{P}$ 문제라고 하거나, 복잡도 클래스complexity class $\textsf{P}$ 에 속한다고 합니다. 따라서 최대 공약수를 구하는 문제는 $\textsf{P}$ 에 속합니다. 유클리드 알고리즘이라는 방법을 찾았기 때문입니다.

한편, 어떤 알고리즘이 $T(n) = 2^n + 3$ 처럼 지수 시간을 시간 복잡도로 가지면, 지수 시간exponential time을 가진다고 말합니다. 즉 시간 복잡도가 $O(2^{f(n)})$ 꼴인 경우입니다. 이렇게 지수 시간 알고리즘으로 풀 수 있는 문제를 모은 클래스를 $\textsf{EXPTIME}$ 이라고도 부릅니다. 한편, 빅오의 정의로 인해, $\textsf{P}$ 문제는 모두 $\textsf{EXPTIME}$ 에 속합니다.

빠르다는 의미

클래스 $\textsf{P}$ 에 속하는 문제를 트랙터블tractable하다고도 부르고, ‘빠르게’ 풀 수 있는 문제를 트랙터블한 문제로 정의하기도 합니다. 반대로 $\textsf{P}$ 에 속하지 않으면 인트랙터블intractable하다고 부릅니다.

다항 시간 알고리즘을 아직 발견하지 못했다고 해서, 그 문제가 트랙터블하지 않다고 결론을 내릴 수가 없습니다. 정말로 다항 시간 알고리즘이 존재하지 않음을 보였을 때, 즉 $\textsf{P}$ 에 속하지 않는다고 보였을 때, 문제가 인트랙터블함을 보인 것입니다. 대표적으로 바둑은 $\textsf{P}$ 가 아닌 $\textsf{EXPTIME}$ 에 속하는 문제로 인트랙터블합니다. 따라서 모든 경우의 수를 조사하는 방법 말고는, 이기는 방법을 ‘빠르게’ 찾아내기란 이론적으로 불가능합니다.

다항 시간 알고리즘이 있는지 아직 모르는 문제도 있습니다. 대표적으로 $\textsf{NP}$ 문제라고 부르는 것들이 그렇습니다. 예를 들어, 다리로 연결된 섬들이 있을 때, 모든 섬을 지나는 경로를 찾는 문제는 소위 해밀턴 경로Hamiltonian path 문제라고 부르는데요. $\textsf{NP}$ 에 속하는 이 문제는 모든 경우의 수를 조사하는 지수 시간 알고리즘 말고는 풀 방법이 아직 없습니다. $\textsf{NP}$ 문제가 $\textsf{P}$ 문제인지 아닌지는 P-NP 문제라는 이름으로 백 만 달러가 걸려있지만 오랜 시간동안 밝혀지지 않았습니다.

따라서 $\textsf{P}$ 문제 외의 것을 마주했다면, 특별한 이유가 없는 한 푸는 시도 자체가 좋은 선택은 아닐 수 있습니다. 튜링 머신이 모든 문제를 풀 수 없듯이, 어떤 문제든 기계로 해결할 수 있다는 가정을 버리고, 트랙터블한 문제에 집중하는 편이 나을 수도 있습니다. 물론 그 특별한 이유를 갖고 미지의 문제에 도전한 덕분에 발전이 생기기도 합니다. 예를 들면, 소수 판별 문제에 다항 시간 알고리즘을 발견함으로써 이것이 $\textsf{P}$ 에 속한다고 밝혀진 사례입니다.

$\textsf{P}$ 문제가 이론적으로 중요한 기준점이 되는 이유는, 튜링 머신이든 RAM 이든 동일한 $\textsf{P}$ 문제를 가지기 때문입니다. 다시 말해, RAM 계산 모델이 튜링 머신보다 더 ‘빠르게’ 풀 수 있는 문제는 없습니다.

입력값 $n$ 이 커짐에 따라, 여러 알고리즘의 시간 복잡도 함수 $T(n)$ 이 얼마나 빨리 커지는지 다음과 같이 그려볼 수 있습니다. 소요 시간이 시간 복잡도 만큼의 초가 걸린다고 했을 때, 입력값 $n$ 에 따라 소요 시간이 얼마나 걸리는지 보여줍니다.

various time complexity — 그림 6. 입력값에 따른 소요 시간 그래프. 로그-로그 스케일. 동일한 소요 시간에 각 시간 복잡도가 얼마나 큰 입력값을 처리할 수 있는지 보여줍니다. 예를 들어, 지수 시간 알고리즘은 초 단위로 해결할 수 있었더라도 입력값이 열 배 정도 커지면 금방 일 년 정도가 필요해집니다. 반면, 로그 함수의 경우 백만 배가 커져도 일 분 미만이 소요됩니다.

지수 시간 알고리즘은 입력값이 열 배 정도 커지면, 소요 시간이 분 단위에서 금방 연 단위로 커집니다. 한편, 로그 함수는 커지는 속도가 비교적 상당히 느립니다.

따라서 유클리드 알고리즘이 빠른 편이라는 사실을 여기서 확인할 수 있습니다. 반대로, 바둑이나 해밀턴 경로 문제같이 다항 시간 알고리즘이 없는 것들은 입력값이 조금만 커져도 해결이 현실적으로는 불가능합니다.

마치며

본문의 자바 코드는 깃허브GitHub에서도 확인할 수 있습니다.

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
Introduction to the Theory of Computation (3rd ed., Michael Sipser, 2012)
Introduction to Automata Theory, Languages, and Computation (3rd ed., John Hopcroft et al., 2006)
Computational Complexity: A Modern Approach (Sanjeev Arora, Boaz Barak, 2009)
Computers and Intractability: A Guide to the Theory of NP-Completeness (Michael R. Garey, David S. Johnson, 1979)
The Art of Computer Programming, Vol. 1 (3rd ed., Donald Knuth, 1997), 또는 The Art of Computer Programming 1 (한빛미디어, 2006)
The Church-Turing Thesis (Spring 2024 ed., Jack Copeland)
On Computable Numbers, with an Application to the Entscheidungsproblem (Alan Turing, 1937)
Elementary Number Theory (6th ed., Kenneth Rosen, 2011)
PRIMES is P (Manindra Agrawal et al., 2004): 소수 판별 문제의 다항 시간 알고리즘.