유클리드 호제법 시간복잡도 증명

시간복잡도 증명

\(gcd(a,\,b)=g\) 라고 하자, 이때 \(g\)는 \(a\), \(b\) 의 최대공약수이다.

그리고 \(a\) 를 \(b\) 로 나눈 몫을 \(q\), 나머지를 \(r\) 라고 해보자. 그러면 \(a=qb+r\) 가 된다.

유클리드 호제법은 기존의 \((a,\;b)\) 를 \((b,\;r)\) 로 축소 해나가게 되면서 결국 \((g,\;0)\) 의 형태가 나오게 된다.

\[gcd(a,\,b)=gcd(b,\,r)=...=gcd(g,\;0)=g\]

이 때 \(gcd(a,\,b)\)에서 \(a\)가 \(b\)보다 작다면 \(a\%b\) 가 \(a\)이므로,
\(gcd(a,\,b) = gcd(b,\,a)\) 가 된다.

그러므로 첫번째 인자는 항상 두번째인자보다 클 수 있다.

따라서 \(a \geq b\) 라고 가정하고 아래의 식이 전개되는 것을 확인해보자

\[1 \le q\] \[2 \le q+1\] \[2r \le rq+r\] \[rq+r \le qb+r\] \[\because r < b\] \[\therefore 2r \le qb+r\]

이때, \(a=qb+r\) 이므로, \(a\)는 \(r\)의 2배 이상임을 알 수 있다.

결론

1. 유클리드 호제법는 순서쌍의 곱이 0이 될 때 까지 풀이를 진행한다.
2. (a, b) 에서 (b, r) 로 축소될 때, 순서쌍의 곱은 \(a \times b \ge 2(b \times r)\) 이므로 2배 이상 줄어든다.
3. 따라서 최소 2배씩 감소하므로 시간복잡도는 \(O(max(loga,\,logb))\) 이다.