GCD 함수의 반복 실행 시간 (유클리드 알고리즘)

Question

gcd 함수를 반복적으로 반복적으로 구현하는 방법에 대한 게시물 만 찾을 수 있었지만 찾을 수 없었습니다. 나는 Stackoverflow에 있다고 확신하지만 그것을 찾을 수 없기 때문에 중복 된 게시물 인 경우 사과드립니다.

---

나는 위키 백과 (here)의 분석에보고하고 재발 관계를 이해할 수 없었다.

C에서 반복적으로 구현되는 GCD 함수의 다음 구현을 고려해보십시오. 두 숫자는 모두 양수 여야하지만 실행 시간과 관련이없는 사전 조건이 있습니다. 모든 작업이 O (1) 따라서 우리가 알고있는 점화식 지금까지 인 것을 나는 발견 실행 시간에 분석을 수행

int gcd(int const a, int const b) { 
    // Checks pre conditions. 
    assert(a >= 0); 
    assert(b >= 0); 

    if (a < b) return gcd(b, a); 

    if (b == 0) return a; 

    return gcd(b, a % b); 
} 

: T를 (N) = O (1) + ???. 이제는 재귀 호출을 분석하기 위해 재귀 관계를 올바르게 설명하는 재귀 호출로 a (mod b)를 해석하는 방법을 모르겠습니다.

Answer 1

각 재귀 단계에서 gcd은 인수 중 하나를 절반 (최대)으로 자릅니다. 이를 확인하려면이 이가지 경우를 보면 : 다음 단계에 당신이 a에서 b 이상을 제거 할 % 조작 이후 a' = b 및 b' < a/2을해야합니다

b >= a/2합니다.

b < a/2 경우 다음 단계에서 당신은 가장 b - 1 반환 할 수 % 조작 이후 a' = b 및 b' < a/2을해야합니다.

따라서 각 재귀 단계에서 gcd은 인수 중 하나를 절반 (최대)으로 자릅니다. 이것은 O (log (N)) 단계입니다. 여기서 N은 초기 a 및 b의 최대 값입니다.

Answer 2

유클리드 GCD를 분석하려면 다음과 같은 피보나치 쌍을 사용해야합니다. gcd (Fib [n], Fib [n - 1]) - 최악의 시나리오.

위의 유클리드 GCD를 테스트하면 결국 24 개의 재귀 호출이 생성됩니다. 당신이 관계 해결을 재발 익숙한 경우

, 다음이 당신을 관심 있습니다

을이 연구로, 하나는 (배당금/제수 쌍에 대해 반복의 정확한 수를 추론 할 수 없습니다 따라서 작은 오 표기법), 그러나이 상한이 유효하다는 것을 보장합니다. 일반적으로 하한은 Omega (1)입니다 (제수가 인 경우).

Answer 3

간단한 분석과 증거는 다음과 같이 진행됩니다
이

1. 표시하는 Euclid(a,b) 다음 이상의 N 단계, F(i) 피보나치 수 번째 i입니다 a>=F(n+1) 및 b>=F(n)를 취합니다.
   이것은 쉽게 유도로 수행 할 수 있습니다.

2. 쇼 유도에 의해 다시 F(n) ≥ φ N-1, 즉. 1 단계 및 2

3. 사용한 결과, 우리는 로그 _φ B ≥ N-1 F(n) ≥ φ ^{N-1 양쪽 대수 촬영}
   ≥ ㄴ있다.
   
   따라서 입증 ≤ N + 1이 로그 결합이 향상 될 수

_φ B.
EUCLID(ka,kb)의 재귀 호출 수는 EUCLID(a,b)과 동일하며, k은 정수입니다. 따라서, 결합은 1 + log _φ (b/gcd (a, b))로 개선된다.