왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까?

 질문이 왔습니다. 왜 확장 유클리드는 최악의 경우에, 대략 log(min(a,b))개의 gcd 함수를 호출하나요? 생각보다 빨리 끝나는 것 같은데. 이 질문에 대한 답을 하기 위해서는 재귀 함수의 기저 조건에서부터 위로 쭉 올라가 보아야 합니다.

 

 

---

 그러면 기저 조건을 먼저 볼 건데요. gcd(2,1)의 값은 1입니다. 2는 1로 나누어 떨어지기 때문입니다.

 

 

 이 때, gcd는 재귀적으로 1번 호출합니다. 유클리드 알고리즘은, a = bQ+r꼴로 표현이 될 때 (단 0<r<b), gcd(a,b)의 값과 gcd(b,r)이 같다는 것을 이용합니다. 그러면 b의 값이 2이고, r의 값이 1일 건데요. 그러면 a = 2Q+1꼴로 표현이 될 겁니다. a>b이면서, 2로 나눴을 때, 나머지가 1인 가장 작은 수는 얼마인가요? 3입니다.

 

 

 그러면, gcd(3,2)를 호출했을 때, 결과 값을 리턴할 때 까지, 2번을 호출합니다. 정말 그런지 확인해 볼까요? gcd(a,b)의 값과 gcd(b,r)의 값이 같다고 했습니다. 3을 2로 나눈 나머지는 1이기 때문에, gcd(3,2)의 값과 gcd(2,1)의 값이 같습니다. 그런데, gcd(2,1)을 호출했을 때, 2가 1로 나누어 떨어지기 때문에, 1이 리턴됩니다.

 

 b의 값을 3, r의 값을 2라고 합시다. 그러면 a = bQ + r꼴로 표현을 했을 때, a = 3Q + 2로 표현할 수 있어요. a>b이면서 3으로 나눴을 때 나머지가 2인 가장 작은 자연수는 얼마인가요? 5입니다. 우리는 b 다음에 a 이렇게 커지는 수열을 생각할 때, a를 최대한 작은 친구를 선택하는 겁니다. 최대한 천천히 증가하게끔.

 

 

 그러면 gcd(5,3)을 호출하였을 때, 내부에서 gcd(3,2)가 호출이 될 겁니다.

 

 

 그러면 gcd(8,5)는 어떨까요? 8을 5로 나눈 나머지는 3이기 때문에, 내부적으로 gcd(5,3)이 호출됩니다. 따라서, 이 때에는 4번 호출이 되겠네요.

 

 

---

 1, 2, 3, 5, 8, 13, ... 이 수열은 상당히 많이 보셨으리라 생각합니다. 바로 피보나치 수열입니다. 그러면 gcd(8,5)라던지, gcd(5,3)은 피보나치 수열에서 인접한 두 수의 gcd를 구한 것과 같을 겁니다.

 

 

 예를 들어서 3과 5의 최대 공약수를 구하라고 했다면, 노란색으로 칠한 3번째 수와 4번째 수를 가지고 연산을 해야 할 겁니다. 5하고 8은 어떨까요? 이 때 재귀 호출 횟수는 총 3입니다.

 

 

 4번째 수와 5번쨰 수를 가지고 연산을 한 것입니다. 이 때, gcd 호출 횟수는 총 4입니다. 즉 fibo[1] = 1이고, fibo[2] = 2이고, gcd(a,b)를 구했을 때 a가 i+1번째 수이고 b가 i번째 수라면, 재귀 호출 횟수는 i번 이라는 것입니다.

 

 

 그러면 위 프로그램을 봅시다. 이것은 i번째 피보나치 수를 출력하는 프로그램인데요. 저는 91번째 수까지 출력을 하였습니다. 왜냐하면 92번째 부터는 long long형이 표현할 수 있는 범위를 넘어가기 때문입니다.

 

 

 이들을 출력해 보면 다음과 같은데요. 7540113804746346429와 4660046610375530309의 최대 공약수를 구하기 위해서, 유클리드 호제법을 이용한 함수를 재귀적으로 몇 번 호출해야 할까요? 답은 90번입니다. 정말 그런지 볼까요?

 

 

 저는 유클리드 함수에 depth라는 인자를 하나 추가했습니다. 이것은 현재 depth가 얼마인지를 나타냅니다.

 

 

 a%b의 값이 0이라면, a가 b로 나누어 떨어진다는 의미이므로, 이 때 depth 값을 출력합니다. 아니라면, 재귀 호출을 하는데요. 이 때 b, a%b, 그러니까 a를 b로 나눈 나머지 r을 넘겨주고, depth+1을 3번째 인자로 넘겨줍니다.

 

 

 실행 결과는 정확하게 90이 나옵니다. 90번 호출을 했다는 의미입니다. 저는 위의 수행 과정에서 b와 r값을 토대로, 조건을 만족하는, a>b이면서, 가장 작은 a의 값을 구했습니다. 그리디하게 접근을 했어요. 그렇기에, long long형 범위에서, 최악의 경우 90회 가량 돈다는 것을 보일 수 있어요.

 

---

 피보나치 수열 a는 n이 매우 커질수록 a(n+1)/a(n)의 값이 수렴한다는 사실이 알려져 있습니다. 그러면 등비수열 꼴로 나타낼 수 있을 겁니다. 다음 방정식을 풀어 봅시다.

 

 

1 : x = x : x + 1 (단 x>1)

 

 

 이 방정식을 풀면 x = (1+sqrt(5))/2가 나와요. 나머지 한 근은 1보다 작으므로 고려되지 않습니다. 즉, 대략적으로 피보나치 수열은 초항이 1이고, 공비가 (1+sqrt(5))/2인 등비로 나타낼 수 있다는 건데요. 정확히는 아니지만요. x^d = t인 d를 구해 봅시다. t = min(a,b)라고 하고요.

 

 그러면 d의 값은 밑이 x인 log(t)일 겁니다. x는 1.618... 이므로 2보다는 작습니다. 따라서, 최악의 경우 밑이 2인 log(t)에1.5의 상수가 붙겠네요. 이 값은 대략 94 ~ 95인데요. 90과 얼추 일치하네요.