왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까?
질문이 왔습니다. 왜 확장 유클리드는 최악의 경우에, 대략 log(min(a,b))개의 gcd 함수를 호출하나요? 생각보다 빨리 끝나는 것 같은데. 이 질문에 대한 답을 하기 위해서는 재귀 함수의 기저 조건에서부터 위로 쭉 올라가 보아야 합니다. 그러면 기저 조건을 먼저 볼 건데요. gcd(2,1)의 값은 1입니다. 2는 1로 나누어 떨어지기 때문입니다. 이 때, gcd는 재귀적으로 1번 호출합니다. 유클리드 알고리즘은, a = bQ+r꼴로 표현이 될 때 (단 0b이면서 3으로 나눴을 때 나머지가 2인 가장 작은 자연수는 얼마인가요? 5입니다. 우리는 b 다음에 a 이렇게 커지는 수열을 생각할 때, a를 최대한 작은 친구를 선택하는 겁니다. 최대한 천천히 증가하게끔. 그러면 gcd(5,3)을 호출하였을 ..
자료알고/알고리즘
2019. 8. 21. 15:50
최근댓글