Zeitkomplexität von GCD Code

Question

Ich versuche, die Zeit Komplexität für den folgenden Code zu verstehen:

int gcd(int n, int m) { 
    if (n%m ==0) return m; 
    if (n < m) swap(n, m); 
    while (m > 0) { 
     n = n%m; 
     swap(n, m); 
    } 
    return n; 
} 

ich die Komplexität des obigen Codes lesen ist Θ (log n). Kann mir jemand die Logik dahinter erklären?

Answer 1

Betrachten Sie zwei beliebige Schritte des Algorithmus.

Irgendwann haben Sie die Zahlen (a, b) mit a> b. Nach dem ersten Schritt zu machen diese (b, c) mitc = a mod b, und nach dem zweiten Schritt werden die beiden Zahlen (c, d) mitd = b mod c sein.

Jetzt denke rückwärts. Als d = b mod c wissen wir, dass b = kc + d für einige k> 0. Die kleinste Möglichkeit ist k = 1, also b ≥ 1c + d = c + d.

Von diesem Ergebnis und aus a> b wir bekommen a> c + d. Wenn wir die letzten zwei Ungleichungen addieren, die wir gerade abgeleitet haben, erhalten wir (a + b)> 2 (c + d). In Worten, nach zwei aufeinander folgenden Schritten verringert sich die Summe der beiden Zahlen auf weniger als die Hälfte ihrer ursprünglichen Größe.

Sehen Sie sich jetzt den allerersten Schritt des Algorithmus an. Zu Beginn haben wir einige (a, b) mit a> b. Nach dem allerersten Schritt haben wir (b, c) mit c = a mod b und deutlich b> c. Daher sind nach dem ersten Schritt beide Zahlen höchstens gleich der kleineren der beiden eingegebenen Zahlen.

Wenn wir diese beiden Ergebnisse zusammenführen, können wir schließen, dass die Anzahl der Iterationen (rekursive Aufrufe in anderen Implementierungen) in der kleineren Eingangsnummer höchstens logarithmisch ist. Mit anderen Worten, die Anzahl der Iterationen ist höchstens linear in der Anzahl der Ziffern in der kleineren Eingangsnummer.