유클리드 호제법 알고리즘의 시간복잡도 예측하기

UPD: 자기 전에 생각해보니, 유클리드 호제법은 끝나기 직전을 제외하고 무조건 2 이상의 수로 나눌 수밖에 없어서 log의 밑이 2보다는 크다. 따라서 아래 글은 전부 헛짓이다..

 

오늘 학원에서 공부를 하다가 굉장히 재밌는 논의를 발견했다.

그걸 이용해서 유클리드 호제법 연산 횟수의 상한을 알아내 보았다.

0. 유클리드 호제법 알고리즘 & 왜 이걸 증명하는가

유클리드 호제법은 다음 사실에 기반한다:

 

$a, b$가 $a\geq b$를 만족하는 정수이고, $a=bq+r$이 성립할 때, $gcd(a, b) = gcd(b, r)$이다.

 

그런데, $gcd(a, 0)=a$임을 알고 있고, $r$은 $b$보다 작으므로 $min(a, b)$는 자연수의 감소수열이 되고, 언젠가 0이 되므로

저 방식을 계속 쓰다 보면 $gcd(a, b)$를 언젠가는 알 수 있다는 결론을 내릴 수 있다.

 

또한, 계속 어떤 숫자로 나눠나가므로 시간복잡도가 대강 $O(log a)$정도라고 생각해 볼 수 있다. 

여기서 의문이 생긴다:

어떤 절묘한 $a$와 $b$를 잡아서, 밑이 1에 무한히 가까워지게 할 수 있지 않을까? 나누는 숫자가 계속 바뀌니까.. 

그러면 예상치 못한 시간 초과가 발생할 수도 있지 않을까?

 

이 글에서는 그게 불가능하다는 것을 보일 것이며, 밑의 하한은 1.5이다.

1. 점화식으로 표현하기

$r_n$을 다음과 같이 정의하자:

 

$r_{n+1}=r_{n} - \lfloor{r_{n} \over r_{n-1}}\rfloor r_{n-1}\,\,\,(r_1 = a, r_2 = b, a\geq b, a, b$는 정수$)$

 

이러면 $r_n$은 유클리드 호제법을 n-2번 실행할 때 나타나는 나머지가 된다. 

또, 나머지는 젯수보다 작기 때문에 $r_n$은 항상 감소함을 알 수 있으며, $r_n$은 0보다 크거나 같은 정수이므로 언젠가는 0이 된다.

 

이제 $r_{n_0} >0$, $r_{n_0+1}=0$인 $n_0$를 잡자.

2. $r_n$에 대한 부등식 잡기

조금 뜬금없지만 피보나치 수열 $f_n$을 다음과 같이 정의하자:

$f_1=0$, $f_2=1$, $f_n = f_{n-1}+f_{n-2}$

 

그러면, 다음과 같은 식이 성립한다:

 

$r_{n_0-k+2} \geq f_k \,(1 \leq k \leq n_0+1)$

 

증명) 수학적 귀납법으로 접근한다. 

 

1. $k=1, 2$ : 넣어 보면 성립한다.

 

2. $k = p, p+1$에서 성립한다고 가정하자.

그러면, $r_{n_0-p+2}\geq f_p$, $r_{n_0-p+1}\geq f_{p+1}$이 성립한다. 

 

3. $k = p+2$에서 성립함을 보이자.

$k$에 $p+2$를 대입하면, $r_{n_0-k+2} = r_{n_0-p}$

$r_{n_0-p} = qr_{n_0-p+1}+r_{n_0-p+2} \geq r_{n_0-p+1} + r_{n_0-p+2} \geq f_p+f_{p+1} = f_{p+2} $

 

따라서, 수학적 귀납법에 의해 $r_{n_0-k+2} \geq f_k$가 항상 성립한다.

3. 피보나치 수에 대한 부등식 잡기

Claim) $f_n \geq ({3 \over 2})^n $

 

증명) 마찬가지로 수학적 귀납법으로 가능하다.

 

1. $n=1, 2$ : 대입하면 성립한다.

 

2. $n=k, k+1$에서 성립한다고 가정하자.

따라서 $f_{k} \geq ({3 \over 2})^{k} $, $f_{k+1} \geq ({3 \over 2})^{k+1} $이 성립한다.

 

3. $n=k+2$에서 성립함을 보이자.

 

$f_{k+2} = f_{k+1}+f_k \geq ({3 \over 2})^{k} + ({3 \over 2})^{k+1} = {5 \over 2}({3 \over 2})^k \geq {9 \over 4} ({3 \over 2})^{k} = ({3 \over 2})^{k+2}$

 

따라서 $f_{k+2} \leq ({3 \over 2})^{k+2}$가 성립하고 모든 자연수 $n$에 대해 Claim이 성립한다.

4. 상한 잡기

아까 2.에서 $r_{n_0-k+2} \geq f_k$임을 보였다.  

$k=n_0+1$을 대입하자. 그러면 $r_1 = a \geq f_{n_0+1}$이 성립한다.

또, 3.에서 $f_{n_0+1} \geq ({3 \over 2})^{n_0+1}$이 성립한다.

따라서, $r_1 = a \geq f_{n_0+1} \geq ({3 \over 2})^{n_0+1}$이고, 

양변에 $log_{1.5}$를 취하고 이항하면 $log_{1.5}a -1 \geq n_0$가 성립한다.

 

그런데, 아까 전에 $n_0$는 $r_{n_0} >0$, $r_{n_0+1}=0$인 $n_0$를 만족한다고 했고,

$r_n$은 유클리드 호제법을 $n-2$번 시행했을 때 더 작은 수를 나타내는 수열이므로, 

$gcd(a, b)$를 구할 때 대략 $n_0$번의 나눗셈을 시행하면 알고리즘이 종료됨을 알 수 있다.

 

그런데, 방금 $n_0$가 $log_{1.5}a -1$보다 작거나 같음을 보였다. 따라서 아무리 $a, b$를 잘 잡아도 연산 횟수에 붙는 $log$의 밑은 1.5보다 커질 수 없음이 증명되었다.

 

따라서, 유클리드 호제법 알고리즘은 상수가 작은 $O(logN)$에 최대공약수를 구할 수 있다. 끝!