Algorytm złożoności czasu Euclida

Question

Mam pytanie dotyczące algorytmu Euklidesa w celu znalezienia największych wspólnych dzielników.

gcd (p, q) gdzie p> q i q to n-bitowa liczba całkowita.

Staram się śledzić czas analizy złożoności algorytmu (wejście jest N-bitów jak wyżej)

gcd(p,q) 
    if (p == q) 
     return q 
    if (p < q) 
     gcd(q,p) 
    while (q != 0) 
     temp = p % q 
     p = q 
     q = temp 
    return p 

już zrozumieć, że suma dwóch liczb, u + v gdzie u i v stand dla wartości początkowych p i q zmniejsza się co najmniej o współczynnik co najmniej 1/2.

Teraz pozwól m być liczbą iteracji dla tego algorytmu. Chcemy znaleźć najmniejszą liczbę całkowitą m taką, że (1/2)^m(u + v) <= 1

Oto moje pytanie. Otrzymuję, że suma dwóch liczb w każdej iteracji jest górna - ograniczona przez (1/2)^m(p + q). Ale tak naprawdę nie widzę powodu, dla którego osiągnięto maks. m, gdy ta liczba to <= 1.

Odpowiedź brzmi: O (n) dla n-bitów q, ale tutaj utknęłam.

Proszę o pomoc!

Answer 1

Wyobraź sobie, że mamy p i q, gdzie p> q. Teraz są dwa przypadki:

1) p> = 2 * q: w tym przypadku p zostanie zredukowane do mniej niż q po modyfikacji, więc suma będzie wynosić co najwyżej 2/3 tego, co było przed.

2) q < p < 2 * q: w tym przypadku operacja mod będzie jak odjęcie q od p, więc znowu ogólna suma będzie wynosić co najwyżej 2/3 tego, co było wcześniej.

Dlatego w każdym kroku kwota ta będzie wynosić 2/3 ostatniej sumy. Ponieważ twoje liczby to n bitów, wielkość tej sumy wynosi 2^{n + 1}; tak więc, z log 2^{n + 1} (podstawa 3/2) kroki, które jest rzeczywiście O (n), suma będzie 0.