Wie viel Zeit braucht Fibonacci Algorithmus zu berechnen F (n)

Question

Ich habe '8.1.1 Fibonacci-Zahlen durch Rekursion' Abschnitt in 'The algorithm design manual' Buch von Skiena gelesen.

Ich konnte unten Absatz in diesem Abschnitt nicht verstehen.

Wie viel Zeit braucht dieser Algorithmus, um F (n) zu berechnen? Da Fn + 1/Fn ≈ φ = (1 + √5)/2 ≈ 1,61803, bedeutet dies, dass Fn> 1,6^n ist. Da unser Rekursionsbaum nur 0 und 1 als Blätter hat, müssen wir bei einer so großen Zahl unter mindestens 1,6 n Blätter oder Prozeduraufrufe haben! Dieses bescheidene kleine Programm benötigt exponentielle Zeit!

Kann jemand meine Fragen unten von diesem Absatz erklären.

• Warum wird Fn + 1/Fn zur Berechnung der Algorithmuszeit verwendet?
• Warum Fn> 1.6^n
• Wie werden wir 1,6 n Blätter oder Prozeduren aufrufen?

Bitte erläutern beispielhaft als F (4)

Answer 1

Hier ist meine Antwort auf meine Frage nehmen. Wenn Sie Rekursion verwenden, um Fibonacci-Zahlen zu berechnen, ist die Berechnungszeit F(N)+F(N-1)+F(N-2)+...+F(1) = F(N+2)-2 = O(F(N+2)).Binet's FormulaF(N) nearly equal sqrt(1/5) * φ^N beweist, und diese Formel auch dies zu beweisen.

• F (k + 1)/F (k) fast gleich φ.
• Sie können F (k)> = 1,6^k beweisen, wenn Sie nach kleinen k suchen.

Aber ich schlage vor, Fibonacci-Zahlen für diesen Algorithmus zu berechnen.

1. Verwendung Dynamische Programmierung
Fibonacci-Folge für die dynamische Programmierung berechnen kann, und die Zeit ist O (N).
Es ist offensichtlich, weil es eine Beziehung F (N) = F (N-1) + F (N-2) gibt.

2. Verwenden von Matrix-Exponentation
Eigentlich ((1 1) (1 0))^N = ((F(N+2) F(N+1)) (F(N+1) F(N))).
Wenn Sie exponentation-by-quadriert-Algorithmus verwenden, können Sie den Wert für O (log N) berechnen, so dass Sie für berechnen kann F (N) O (log (N)).

Abschließend ist Binets Formel nicht gut, weil es Fließkommawert verwendet, so verursacht es Präzisionsfehler.
Ich schlage vor, dass dynamische Programmierung oder Matrix-Exponentiation für dieses Problem gut ist.

Answer 2

Ich wechsle von n nach m für den ersten Teil der Antwort.

F (m + 1)/F (m) ist ein Verhältnis, das verwendet wird, um einen ungefähren Wert für F (m) zu erhalten, nicht die Zeit. Beginnend bei m> = 1, wenn m zunimmt, konvergiert das Verhältnis F (m + 1)/F (m) schnell zu φ = (1 + sqrt (5))/2 ~ = 1,61803. Dies kann als F (m + 1) ~ = φ F (m) wiedergegeben werden.Dann ist F (m + 2) ~ = φ F (m + 1) ~ = φ (φ F (m)) ~ = φ^2 F (m) und allgemein F (m + k) ~ = φ^k F (m), eine vernünftige Näherung für m> = 10, wie in der Tabelle am Ende dieser Antwort gezeigt. Der Absatz macht dann einen plötzlichen Sprung zu der Aussage, dass F (n)> 1,6^n, was nur für n> = 72 gilt. Der Absatz adressiert dann den Rekursionsbaum, der nur Addition beinhaltet, und stellt fest, dass Die Blattknoten des Rekursionsbaums geben nur 0 (F (0)) oder 1 (F (1)) zurück, sodass Sie mindestens 1,6^n (nicht 1,6n) Blattknoten benötigen (1,6^n Blattknoten, die 1 zurückgeben) um eine Summe> = 1,6^n zu erzeugen. (Man beachte, dass F (n)> 1,6^n nur für n> = 72 gilt).

Wie bei einem schnelleren Algorithmus ähnelt eine Lucas-Sequenzmethode einer optimierten Matrixexponentiation durch die Quadrierungsmethode. Der Maximalwert für eine 64-Bit-Ganzzahl ohne Vorzeichen ist fib (93) == 12200160415121876738 (was im folgenden Code 7 Schleifen erfordern würde).

/* lucas sequence method */ 
uint64_t fib(uint64_t n) { 
    uint64_t a, b, p, q, aq, qq; 
    a = q = 1; 
    b = p = 0; 
    while(1){ 
     if (n & 1) { 
      aq = a*q; 
      a = b*q + aq + a*p; 
      b = b*p + aq; 
     } 
     n >>= 1; 
     if (n == 0) 
      break; 
     qq = q*q; 
     q = p*q*2 + qq; 
     p = p*p + qq; 
    } 
    return b; 
} 

Um eine Vorstellung davon, wie genau die Näherung F (m + k) geben ~ = φ^k F (m) wird unter Verwendung von F (100) als Testfall im Vergleich zu Werte von m (10, 20 , 30, 40).

F(100)/(φ^90 F(10)) ~= 1.0000661 
F(100)/(φ^80 F(20)) ~= 1.00000000437 
F(100)/(φ^70 F(30)) ~= 1.000000000000289 
F(100)/(φ^60 F(40)) ~= 1.0000000000000000191