차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
유클리드알고리즘 [2011-04-25 03:42] lifthrasiir 새로 만듦 |
유클리드알고리즘 [2011-05-30 18:25] (현재) |
||
|---|---|---|---|
| 줄 15: | 줄 15: | ||
| 첫번째 성질은 현대적인 $$\gcd$$의 정의를 쓰면 $$\gcd(a,0) = \gcd(0,a) = a$$로 바꿀 수 있으며, 두번째는 여러 번의 [[뺄셈]] 대신 [[나머지연산]]을 써서 $$\gcd(a,b) = \gcd(a \mod b,b)$$로 바꿀 수 있다. 두번째와 세번째를 합치면 $$a > b$$일 때 $$\gcd(a,b) = \gcd(b,a \mod b)$$라는 결과를 얻을 수도 있다. | 첫번째 성질은 현대적인 $$\gcd$$의 정의를 쓰면 $$\gcd(a,0) = \gcd(0,a) = a$$로 바꿀 수 있으며, 두번째는 여러 번의 [[뺄셈]] 대신 [[나머지연산]]을 써서 $$\gcd(a,b) = \gcd(a \mod b,b)$$로 바꿀 수 있다. 두번째와 세번째를 합치면 $$a > b$$일 때 $$\gcd(a,b) = \gcd(b,a \mod b)$$라는 결과를 얻을 수도 있다. | ||
| - | 유클리드 알고리즘이 모든 자연수에 대해서 끝난다는 점은 매 시점에서 두 자연수 중 하나는 항상 줄어 든다는 점, 또는 두 자연수의 합이 항상 [[감조단소]]한다는 점에서 쉽게 증명할 수 있다. (이 경우 두번째와 세번째 성질을 합쳐서 항상 "감소"하도록 만드는 게 증명에 유리하다.) 유클리드 알고리즘이 옳다는 점은 위의 성질로부터 거의 곧바로 유도된다. | + | 유클리드 알고리즘이 모든 자연수에 대해서 끝난다는 점은 매 시점에서 두 자연수 중 하나는 항상 줄어 든다는 점, 또는 두 자연수의 합이 항상 [[단조감소]]한다는 점에서 쉽게 증명할 수 있다. (이 경우 두번째와 세번째 성질을 합쳐서 항상 "감소"하도록 만드는 게 증명에 유리하다.) 유클리드 알고리즘이 옳다는 점은 위의 성질로부터 거의 곧바로 유도된다. |
| 유클리드 알고리즘은 최악의 경우 나눗셈이 $$O(\log \min\{a,b\})$$회 필요하다. 이 최악의 경우란 두 인접한 [[피보나치수]]를 입력으로 주었을 경우이며, 따라서 로그의 밑수는 [[황금비]]가 된다. 좀 더 일반적으로 생각해서, 자연수가 [[임의정밀도정수]]일 때 필요한 연산의 수는 $$O\left((\log \min\{a,b\})^2\right)$$회이다. 후자는 눈꼽만큼 개선이 가능하나 아주 큰 숫자가 아니면 별 쓸모가 없다. | 유클리드 알고리즘은 최악의 경우 나눗셈이 $$O(\log \min\{a,b\})$$회 필요하다. 이 최악의 경우란 두 인접한 [[피보나치수]]를 입력으로 주었을 경우이며, 따라서 로그의 밑수는 [[황금비]]가 된다. 좀 더 일반적으로 생각해서, 자연수가 [[임의정밀도정수]]일 때 필요한 연산의 수는 $$O\left((\log \min\{a,b\})^2\right)$$회이다. 후자는 눈꼽만큼 개선이 가능하나 아주 큰 숫자가 아니면 별 쓸모가 없다. | ||
저작권자 © 1999–2012 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?