Die Laufzeit von GCD-Funktion Rekursiv (Euklid-Algorithmus)

Habe ich nur in der Lage gewesen zu finden, Beiträge über wie die Umsetzung der gcd-Funktion sowohl rekursiv und iterativ, aber ich konnte nicht finden, diese. Ich bin sicher, dass es auf Stackoverflow allerdings konnte ich es nicht finden, so dass ich entschuldige mich wenn es einen doppelten post.

Ich habe mir bei der Analyse auf Wikipedia (hier) und konnte nicht verstehen, Ihre Wiederholung Bezug.

Betrachten Sie die folgende Implementierung der GCD-Funktion rekursiv implementiert in C. Es hat eine vor-Voraussetzung, dass beide zahlen müssen positiv sein, aber irrelevant für die Laufzeit.

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 );
}

Durchführung einer Analyse über die Laufzeit finde ich, dass jede operation ist O(1) - und daher wissen wir das Wiederauftreten Beziehung so weit ist: T(n) = O(1) + ???. Jetzt analysieren die rekursiven Aufruf, ich bin mir nicht sicher, wie Sie zu interpretieren ist a (mod b), wie meine rekursiven Aufruf korrekt zu sagen, meine Wiederholung Bezug.

en.wikipedia.org/wiki/...

InformationsquelleAutor Jacob Pollack | 2013-08-08

  1. 7

    Bei jedem rekursiven Schritt gcd schneiden eines der Argumente in der Hälfte (bei den meisten). Um dies zu sehen, betrachten diese beiden Fälle:

    Wenn b >= a/2 dann im nächsten Schritt müssen Sie a' = b und b' < a/2 da die % operation entfernen b oder mehr von a.

    Wenn b < a/2 dann im nächsten Schritt müssen Sie a' = b und b' < a/2 da die % Betrieb zurückkehren können, bei den meisten b - 1.

    Also auf jedem rekursiven Schritt gcd schneiden eines der Argumente in der Hälfte (bei den meisten). Dies ist in O(log(N)) Schritte, wobei N die max von der anfänglichen a und b.

    InformationsquelleAutor Doug Currie

  2. 0

    Analysieren euklidischen GGT, die Sie nutzen sollten Fibonacci-Paare: gcd(Fib[n], Fib[n - 1]) - Worst-case-Szenario.

    Wenn Sie Ihren test-euklidischen GCD oben, Sie werden am Ende mit 24 rekursive Aufrufe.

    Wenn Sie daran gewöhnt sind, um das Wiederauftreten Beziehungen zu lösen, die folgenden, die Sie interessieren könnten:

    Die Laufzeit von GCD-Funktion Rekursiv (Euklid-Algorithmus)

    Mit dieser Studie kann man nicht ableiten, die genaue Anzahl der Iterationen für jede dividend/divisor-pair-Mädchen (daher der klein-Oh-notation), aber es garantiert, dass diese Obere Schranke gilt.
    Im Allgemeinen, die untere Schranke von Omega(1) (Wenn der divisor ist 1, zum Beispiel).

    InformationsquelleAutor Mohamed Ennahdi El Idrissi

  3. 0

    Einer einfachen Analyse und der Beweis geht wie folgt:

    1. Zeigen, dass, wenn Euclid(a,b) dauert mehr als N Schritte, dann
      a>=F(n+1) und b>=F(n), wo F(i) ist die ith Fibonacci
      Anzahl.
      Dies kann leicht getan werden, indem Induktion.

    2. Zeigen, dass F(n) ≥ φn-1, wieder durch
      Induktion.

    3. Nutzung der Ergebnisse von Schritt 1 und 2 haben wir b ≥ F(n) ≥
      φn-1
      Logarithmus auf beiden Seiten,
      logφ - b ≥ n-1.

      Damit bewiesen, n ≤ 1 +
      logφb

    Diese Schranke kann verbessert werden.

    Nein. der rekursiven Aufrufe in EUCLID(ka,kb) ist die gleiche wie in EUCLID(a,b), wo k einige integer.

    Also, die gebunden ist, verbesserte sich auf 1 + logφ( b /gcd(a,b) ).

    InformationsquelleAutor anaik

Schreibe einen Kommentar