[algorithm] 유클리드 알고리즘의 시간 복잡성
Euclid의 최대 공통 분모 알고리즘의 시간 복잡도를 결정하는 데 어려움이 있습니다. 의사 코드의이 알고리즘은 다음과 같습니다.
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
a 와 b 에 의존하는 것 같습니다 . 내 생각은 시간 복잡도가 O (a % b)라는 것입니다. 그 맞습니까? 그것을 작성하는 더 좋은 방법이 있습니까?
답변
Euclid 알고리즘의 시간 복잡성을 분석하는 한 가지 트릭은 두 번의 반복에서 발생하는 일을 따르는 것입니다.
a', b' := a % b, b % (a % b)
이제 a와 b가 모두 감소하므로 분석이 더 쉬워집니다. 케이스로 나눌 수 있습니다.
- 작은 A :
2a <= b - 작은 B :
2b <= a - 작은 A :
2a > b하지만a < b - 작은 B :
2b > a하지만b < a - 같은:
a == b
이제 모든 단일 케이스가 합계 a+b를 최소 1/4 만큼 감소시키는 것을 보여줍니다 .
- Tiny A :
b % (a % b) < a및2a <= b, 그래서b최소한 절반으로a+b감소 하므로 최소한25% - Tiny B :
a % b < b및2b <= a, 그래서a최소한 절반으로a+b감소 하므로 최소한25% - 작은 A는 :
b될 것입니다b-a보다 작은,b/2감소,a+b최소한으로25%. - 작은 B는 :
a될 것입니다a-b보다 작은,a/2감소,a+b최소한으로25%. - 같음 :로
a+b떨어집니다0. 이는 분명히a+b적어도25%.
따라서 사례 분석에 따르면 모든 이중 단계 a+b는 최소한 25%. a+b아래로 떨어질 때까지이 문제가 발생할 수있는 최대 횟수가 있습니다 1. S0에 도달 할 때까지 의 총 단계 수 ( )는을 충족해야합니다 (4/3)^S <= A+B. 이제 작업하십시오.
(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
따라서 반복 횟수는 입력 자릿수에서 선형입니다. cpu 레지스터에 맞는 숫자의 경우 반복을 일정한 시간을 취하는 것으로 모델링 하고 gcd 의 총 실행 시간이 선형 인 척하는 것이 합리적 입니다.
물론, 큰 정수를 다루는 경우 각 반복 내의 모듈러스 연산에 일정한 비용이 발생하지 않는다는 사실을 고려해야합니다. 대략적으로 말하면 총 점근 적 실행 시간은 다대수 인자의 n ^ 2 배가 될 것입니다. 같은 것 n^2 lg(n) 2^O(log* n) . 대신 이진 gcd 를 사용하여 다대수 인자를 피할 수 있습니다 .
답변
알고리즘을 분석하는 적절한 방법은 최악의 시나리오를 결정하는 것입니다. 유클리드 GCD의 최악의 경우는 피보나치 쌍이 관련 될 때 발생합니다.
void EGCD(fib[i], fib[i - 1]), 여기서 i> 0.
예를 들어, 배당이 55이고 제수가 34 인 경우를 선택해 봅시다 (우리는 여전히 피보나치 수를 처리하고 있음을 기억하십시오).
아시다시피이 작업에는 8 번의 반복 (또는 재귀 호출)이 필요했습니다.
더 큰 피보나치 수, 즉 121393과 75025를 시도해 봅시다. 여기에서도 24 번의 반복 (또는 재귀 호출)이 필요하다는 것을 알 수 있습니다.
또한 각 반복이 피보나치 수를 산출한다는 것을 알 수 있습니다. 그것이 우리가 많은 작업을하는 이유입니다. 실제로 피보나치 수만으로는 비슷한 결과를 얻을 수 없습니다.
따라서 시간 복잡도는 이번에는 작은 Oh (상한선)로 표시 될 것입니다. 하한은 직관적으로 Omega (1)입니다. 예를 들어 500을 2로 나눈 경우입니다.
반복 관계를 해결해 보겠습니다.
그러면 유클리드 GCD가 최대 log (xy) 연산 을 할 수 있다고 말할 수 있습니다 .
답변
위키피디아 기사 에서 이것에 대한 훌륭한 모습이 있습니다.
값 쌍에 대한 복잡한 복잡성도 있습니다.
그렇지 않습니다 O(a%b).
더 작은 숫자의 자릿수보다 5 배 이상 더 많은 단계를 거치지 않는 것으로 알려져 있습니다 (기사 참조). 따라서 최대 단계 수는 자릿수에 따라 증가합니다 (ln b). 각 단계의 비용은 자릿수에 따라 증가하므로 복잡성은 O(ln^2 b)b가 더 작은 수에 의해 제한됩니다 . 이는 상한이며 실제 시간은 일반적으로 더 적습니다.
답변
를 참조하십시오 여기 .
특히이 부분 :
Lamé는 n보다 작은 두 수에 대해 최대 공약수에 도달하는 데 필요한 단계의 수는 다음과 같습니다.
따라서 O(log min(a, b))좋은 상한선입니다.
답변
다음은 Euclid 알고리즘의 런타임 복잡성에 대한 직관적 인 이해입니다. 공식 증명은 알고리즘 소개 및 TAOCP Vol 2와 같은 다양한 텍스트에서 다루어집니다.
먼저 두 개의 피보나치 수 F (k + 1) 및 F (k)의 gcd를 취하려고 시도하면 어떻게 될지 생각해보십시오. Euclid의 알고리즘이 F (k) 및 F (k-1)까지 반복되는 것을 빠르게 관찰 할 수 있습니다. 즉, 반복 할 때마다 피보나치 시리즈에서 한 숫자 아래로 이동합니다. 피보나치 수는 Phi가 황금비 인 O (Phi ^ k)이므로 GCD의 실행 시간은 O (log n)이고 여기서 n = max (a, b)이고 log는 Phi의 밑수를가집니다. 다음으로, 피보나치 수는 각 반복에서 충분히 큰 나머지가 연속으로 시작될 때까지 0이되지 않는 쌍을 일관되게 생성한다는 것을 관찰함으로써 이것이 최악의 경우임을 증명할 수 있습니다.
n = max (a, b) 바인딩 된 O (log n)를 더욱 단단하게 만들 수 있습니다. b> = a라고 가정하면 O (log b)에 바운드를 쓸 수 있습니다. 먼저 GCD (ka, kb) = GCD (a, b)를 관찰하십시오. k의 가장 큰 값은 gcd (a, c)이므로 런타임에서 b를 b / gcd (a, b)로 대체하여 O (log b / gcd (a, b))의 경계를 더 좁힐 수 있습니다.
답변
Euclid 알고리즘의 최악의 경우는 나머지가 각 단계에서 가능한 가장 큰 경우입니다. 피보나치 수열의 두 연속 항에 대해.
n과 m이 a와 b의 자릿수 일 때 n> = m이라고 가정하면 알고리즘은 O (m) 나눗셈을 사용합니다.
복잡성은 항상 입력 크기 ,이 경우 자릿수 측면에서 제공됩니다.
답변
n과 m이 모두 연속적인 피보나치 수일 때 최악의 경우가 발생합니다.
gcd (Fn, Fn−1) = gcd (Fn−1, Fn−2) = ⋯ = gcd (F1, F0) = 1이고 n 번째 피보나치 수는 1.618 ^ n이며, 여기서 1.618은 황금 비율입니다.
따라서 gcd (n, m)을 찾으려면 재귀 호출 수는 Θ (logn)이됩니다.
