webentwicklung-frage-antwort-db.com.de

Zeitliche Komplexität des Euklid-Algorithmus

Ich habe Schwierigkeiten zu entscheiden, wie zeitlich die Komplexität des größten gemeinsamen Nenners von Euclid ist. Dieser Algorithmus im Pseudocode lautet:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Es scheint von a und b abzuhängen. Ich denke, dass die Zeitkomplexität O ist (a% b). Ist das korrekt? Gibt es einen besseren Weg, das zu schreiben?

76
Donald Taylor

Ein Trick zur Analyse der zeitlichen Komplexität des Euclid-Algorithmus besteht darin, zwei Iterationen durchzuführen:

a', b' := a % b, b % (a % b)

Jetzt werden a und b anstatt nur einer kleiner, was die Analyse erleichtert. Sie können es in Fälle einteilen:

  • Winzig A: 2a <= b
  • Winziger B: 2b <= a
  • Klein A: 2a > b aber a < b
  • Kleines B: 2b > a aber b < a
  • Gleich: a == b

Jetzt zeigen wir, dass jeder einzelne Fall die Summe a+b um mindestens ein Viertel verringert:

  • Winzig A: b % (a % b) < a und 2a <= b, also b wird um mindestens die Hälfte verringert, also a+b wird um mindestens 25% verringert
  • Winzig B: a % b < b und 2b <= a, also wird a um mindestens die Hälfte verringert, also a+b um mindestens 25% verringert
  • Klein A: b wird b-a, was weniger als b/2 ist, und verringert a+b um mindestens 25%.
  • Small B: a wird zu a-b, was kleiner als a/2 ist und a+b um mindestens 25% verringert.
  • Gleich: a+b fällt auf 0, was offensichtlich a+b um mindestens 25% verringert.

Daher verringert sich bei der Fallanalyse jeder Doppelschritt a+b um mindestens 25%. Dies kann maximal so oft vorkommen, bis a+b gezwungen wird, 1 zu unterschreiten. Die Gesamtzahl der Schritte (S) bis wir 0 treffen, muss (4/3)^S <= A+B erfüllen. Jetzt einfach arbeiten:

(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)

Die Anzahl der Iterationen ist also in Bezug auf die Anzahl der Eingabestellen linear. Für Zahlen, die in CPU-Register passen, ist es sinnvoll, die Iterationen so zu modellieren, dass sie konstante Zeit benötigen, und so zu tun, als ob die Gesamtlaufzeit der GCD linear ist.

Wenn Sie mit großen ganzen Zahlen arbeiten, müssen Sie natürlich berücksichtigen, dass die Moduloperationen innerhalb jeder Iteration keine konstanten Kosten verursachen. Grob gesagt, wird die gesamte asymptotische Laufzeit das N ^ 2-fache eines polylogarithmischen Faktors betragen. So etwas wien^2 lg(n) 2^O(log* n). Der polylogarithmische Faktor kann vermieden werden, indem stattdessen ein binärer gcd verwendet wird.

65
Craig Gidney

Eine geeignete Methode zur Analyse eines Algorithmus besteht darin, die Worst-Case-Szenarien zu bestimmen. Der schlimmste Fall der Euklidischen GCD tritt auf, wenn Fibonacci-Paare beteiligt sind. _ [_] void EGCD(fib[i], fib[i - 1]), wobei i> 0 ist.

Zum Beispiel entscheiden wir uns für den Fall, dass die Dividende 55 beträgt und der Divisor 34 ist (erinnern wir uns daran, dass es sich immer noch um Fibonacci-Zahlen handelt).

enter image description here

Wie Sie vielleicht bemerken, kostete dieser Vorgang 8 Iterationen (oder rekursive Aufrufe).

Versuchen wir es mit größeren Fibonacci-Zahlen, nämlich 121393 und 75025. Wir können auch hier feststellen, dass 24 Iterationen (oder rekursive Aufrufe) erforderlich waren.

enter image description here

Sie können auch feststellen, dass jede Wiederholung eine Fibonacci-Zahl ergibt. Deshalb haben wir so viele Operationen. Wir können ähnliche Ergebnisse nur mit Fibonacci-Zahlen erzielen.

Daher wird die zeitliche Komplexität diesmal durch kleine Oh (obere Grenze) dargestellt. Die untere Grenze ist intuitiv Omega (1): Fall von 500 geteilt durch 2.

Lösen wir die Wiederholungsbeziehung:

enter image description here

Wir können dann sagen, dass die Euklidische GCD eine log (xy) -Operation höchstens durchführen kann.

Es gibt einen tollen Blick auf den Wikipedia-Artikel .

Es gibt sogar eine schöne Darstellung der Komplexität für Wertepaare.

Es ist nicht O(a%b)

Es ist bekannt (siehe Artikel), dass es nie mehr als fünfmal so viele Ziffern in der kleineren Anzahl gibt. Die maximale Anzahl von Schritten wächst also mit der Anzahl der Ziffern (ln b). Die Kosten für jeden Schritt nehmen auch mit der Anzahl der Ziffern zu, sodass die Komplexität an O(ln^2 b) gebunden ist, wobei b die kleinere Zahl ist. Das ist eine Obergrenze, und die tatsächliche Zeit ist normalerweise geringer.

16
JoshD

Siehe hier .

Insbesondere dieser Teil:

Lamé zeigte, dass die Anzahl der Schritte, die erforderlich sind, um den größten gemeinsamen Teiler für zwei Zahlen kleiner als n zu erreichen, ist 

alt text

O(log min(a, b)) ist also eine gute obere Schranke.

11
IVlad

Hier ist ein intuitives Verständnis der Laufzeitkomplexität von Euclids Algorithmus. Die formalen Beweise werden in verschiedenen Texten behandelt, wie beispielsweise Einführung in Algorithmen und TAOCP Vol. 2.

Denken Sie zuerst darüber nach, was passiert, wenn wir versuchen, die gcd von zwei Fibonacci-Zahlen F (k + 1) und F (k) zu nehmen. Sie werden schnell feststellen, dass der Euklid-Algorithmus zu F(k) und F (k-1) iteriert. Das heißt, mit jeder Wiederholung bewegen wir uns um eine Zahl in der Fibonacci-Reihe nach unten. Da die Fibonacci-Zahlen O (Phi ^ k) sind, wobei Phi der Goldene Schnitt ist, können wir feststellen, dass die Laufzeit von GCD O (log n) war, wobei n = max (a, b) und log die Basis von Phi hat. Als Nächstes können wir beweisen, dass dies der schlimmste Fall wäre, wenn wir beobachten, dass die Fibonacci-Zahlen konstant Paare erzeugen, bei denen der Rest bei jeder Iteration groß genug bleibt und nie Null wird, bis Sie am Anfang der Serie angelangt sind.

Wir können O (log n) machen, wobei n = max (a, b) noch enger gebunden ist. Nehmen wir an, dass b> = a, damit wir gebunden an O schreiben können (log b). Beobachten Sie zuerst, dass GCD (ka, kb) = GCD (a, b) ist. Da die größten Werte von k gcd (a, c) sind, können wir b durch b/gcd (a, b) in unserer Laufzeit ersetzen, was zu einer engeren Bindung von O führt (log b/gcd (a, b)).

8
Shital Shah

Der schlimmste Fall des Euklid-Algorithmus liegt vor, wenn die Reste bei jedem Schritt so groß wie möglich sind, d. für zwei aufeinander folgende Terme der Fibonacci-Sequenz.

Wenn n und m die Anzahl der Stellen von a und b sind, nimmt der Algorithmus unter der Annahme von n> = m O(m) Divisionen an.

Beachten Sie, dass die Komplexität immer in Form der Größen der Eingaben angegeben wird, in diesem Fall der Anzahl der Ziffern.

4
Alexandre C.

Der schlimmste Fall tritt auf, wenn sowohl n als auch m aufeinanderfolgende Fibonacci-Zahlen sind.

gcd (Fn, Fn-1) = gcd (Fn-1, Fn-2) = ⋯ = gcd (F1, F0) = 1 und nte Fibonacci-Zahl ist 1,618 ^ n, wobei 1,618 das Goldene Verhältnis ist.

Um gcd (n, m) zu finden, ist die Anzahl der rekursiven Aufrufe Θ (logn).

2
Arnav Attri

Für den iterativen Algorithmus haben wir jedoch:

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Bei Fibonacci-Paaren besteht kein Unterschied zwischen iterativeEGCD() und iterativeEGCDForWorstCase(), wobei letztere wie folgt aussieht:

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Ja, mit Fibonacci Pairs, n = a % n und n = a - n ist es genau das Gleiche.

Wir wissen auch, dass in einer früheren Antwort auf dieselbe Frage ein abnehmender Faktor vorherrscht: factor = m / (n % m).

Um die iterative Version der Euklidischen GCD in einer definierten Form zu gestalten, können wir sie als "Simulator" wie folgt darstellen:

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Basierend auf der Arbeit (letzte Folie) von Dr. Jauhar ALi ist die obige Schleife logarithmisch.

enter image description here

Ja, klein Oh, da der Simulator die Anzahl der Iterationen höchstens angibt. Nicht-Fibonacci-Paare würden eine geringere Anzahl von Iterationen benötigen als Fibonacci, wenn sie mit Euklidischer GCD untersucht wurden.

Gabriel Lames Theorem begrenzt die Anzahl der Schritte durch log (1/sqrt (5) * (a + 1/2)) - 2, wobei die Basis des Logs (1 + sqrt (5))/2 ist. Dies ist für den ungünstigsten Fall für den Algorithmus und tritt auf, wenn die Eingaben aufeinanderfolgende Fibanocci-Zahlen sind.

Eine etwas liberalere Grenze ist: log a, wobei die Basis des Protokolls (sqrt (2)) von Koblitz impliziert wird.

Für kryptographische Zwecke berücksichtigen wir normalerweise die bitweise Komplexität der Algorithmen, wobei zu berücksichtigen ist, dass die Bitgröße ungefähr durch k = loga angegeben wird.

Hier ist eine detaillierte Analyse der bitweisen Komplexität des Euklid-Algorithmus:

Obwohl in den meisten Referenzen die bitweise Komplexität des Euklid-Algorithmus durch O (loga) ^ 3 gegeben ist, existiert eine engere Grenze, die O (loga) ^ 2 ist.

Erwägen; r0 = a, r1 = b, r0 = q1.r1 + r2. . . , ri-1 = qi.ri + ri + 1,. . . , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

beachten Sie, dass: a = r0> = b = r1> r2> r3 ...> rm-1> rm> 0 .......... (1)

und rm ist der größte gemeinsame Teiler von a und b.

Durch einen Anspruch in Koblitz Buch (Ein Kurs in Zahlentheorie und Kryptographie) kann nachgewiesen werden, dass: ri + 1 <(ri-1)/2 ................. ( 2)

Auch in Koblitz ist die Anzahl der Bitoperationen, die erforderlich sind, um eine positive k-Bit-Ganzzahl durch eine positive 1-Bit-Ganzzahl (unter der Annahme, dass k> = 1 ist) geteilt wird, gegeben als: (k-l + 1) .l ...... .............(3)

Bei (1) und (2) ist die Anzahl der Unterteilungen O(loga), und bei (3) beträgt die Gesamtkomplexität O (loga) ^ 3.

Dies kann nun durch eine Bemerkung in Koblitz auf O (loga) ^ 2 reduziert werden.

betrachte ki = logri +1

durch (1) und (2) haben wir: ki + 1 <= ki für i = 0,1, ..., m-2, m-1 und ki + 2 <= (ki) -1 für i = 0 , 1, ..., m-2

und durch (3) sind die Gesamtkosten der m Abteilungen begrenzt durch: SUM [(ki-1) - ((ki) -1))] * ki für i = 0,1,2, ..., m

um dies neu zu ordnen: SUM [(ki-1) - ((ki) -1))] * ki <= 4 * k0 ^ 2

Die bitweise Komplexität des Algorithmus von Euklid ist also O (loga) ^ 2.

0
esra