Gibt es einen Algorithmus zur Berechnung der n-ten Fibonacci-Zahl in sublinearer Zeit?
performance
algorithm
math
time-complexity
fibonacci
Biswajyoti Das
quelle
quelle
Antworten:
Die
n
th Fibonacci-Zahl ist gegeben durchwo
Unter der Annahme , dass die primitiven mathematischen Operationen (
+
,-
,*
und/
) sindO(1)
Sie dieses Ergebnis können Sie die berechnenn
th Fibonacci - Zahl in derO(log n)
Zeit (O(log n)
wegen der Potenzierung in der Formel).In C #:
static double inverseSqrt5 = 1 / Math.Sqrt(5); static double phi = (1 + Math.Sqrt(5)) / 2; /* should use const double inverseSqrt5 = 0.44721359549995793928183473374626 const double phi = 1.6180339887498948482045868343656 */ static int Fibonacci(int n) { return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5); }
quelle
phi^n / sqrt(5) + 1/2
wophi = (1 + sqrt(5)) / 2
. Das ist ein Fakt. Zweitens verstehe ich den Punkt, den andere über die Länge der Antwort machen,O(n)
aber ich habe meiner Antwort eine Bemerkung hinzugefügt, unter der Annahme, dass die primitiven mathematischen Operationen eine konstante Zeit benötigen (ich weiß, dass dies nicht der Fall ist, wenn Sie die Eingaben nicht gebunden haben). Mein Punkt ist, dass wir die n-te Fibonacci-Zahl inO(log n)
arithmetischen Operationen finden können.Aus Pillsys Verweis auf die Matrixexponentiation folgt, so dass für die Matrix
dann
Das Erhöhen von Matrizen auf Potenzen durch wiederholte Multiplikation ist nicht sehr effizient.
Zwei Ansätze zur Matrixexponentiation sind Teilen und Erobern, was M n in O ( ln n ) Schritten ergibt , oder Eigenwertzerlegung, die zeitlich konstant ist, aber aufgrund der begrenzten Gleitkommapräzision Fehler verursachen kann.
Wenn Sie einen exakten Wert wünschen, der größer ist als die Genauigkeit Ihrer Gleitkommaimplementierung, müssen Sie den O (ln n) -Ansatz verwenden, der auf dieser Beziehung basiert:
Die Eigenwertzerlegung auf M findet zwei Matrizen U und Λ, so dass Λ diagonal und ist
Das Erhöhen der Diagonalmatrix Λ auf die n- te Potenz ist eine einfache Sache, bei der jedes Element in Λ auf die n - te Potenz angehoben wird. Dies ergibt eine O (1) -Methode zum Erhöhen von M auf die n- te Potenz. Es ist jedoch unwahrscheinlich, dass die Werte in Λ Ganzzahlen sind, sodass ein Fehler auftritt.Definieren Sie Λ für unsere 2x2-Matrix als
Um jedes λ zu finden , lösen wir
was gibt
mit der quadratischen Formel
Wenn Sie Jasons Antwort gelesen haben, können Sie sehen, wohin das führen wird.
Auflösen nach den Eigenvektoren X 1 und X 2 :
Diese Vektoren ergeben U :
U invertieren mit
also ist U -1 gegeben durch
Gesundheitsüberprüfung:
Der Sanity Check gilt also.
Jetzt haben wir alles, was wir brauchen, um M n 1,2 zu berechnen :
damit
Was mit der an anderer Stelle angegebenen Formel übereinstimmt.
Sie können es aus einer Wiederholungsrelation ableiten, aber beim Engineering-Computing und der Simulation ist die Berechnung der Eigenwerte und Eigenvektoren großer Matrizen eine wichtige Aktivität, da sie Stabilität und Harmonische von Gleichungssystemen bietet und es ermöglicht, Matrizen effizient auf hohe Leistungen anzuheben.
quelle
Wenn Sie die genaue Zahl wollen (die eher ein "Bignum" als ein Int / Float ist), dann fürchte ich das
Es ist unmöglich!
Wie oben angegeben, lautet die Formel für Fibonacci-Zahlen:
Wie viele Ziffern gibt es
fib n
?Da das angeforderte Ergebnis O ( n ) ist, kann es nicht in weniger als O ( n ) berechnet werden.
Wenn Sie nur die unteren Ziffern der Antwort wünschen, können Sie mit der Matrix-Exponentiationsmethode in sublinearer Zeit berechnen.
quelle
O(n*log n)
für die vergleichsbasierte Sortierung einer Folge vonn
Zahlen, bei denen jede ZahlO(log n)
Ziffern hat?Eine der Übungen in SICP befasst sich mit dieser Frage , die hier beschrieben wird .
Im imperativen Stil würde das Programm ungefähr so aussehen
quelle
twisted
Framework).if even(count)
ist korrekt. Die Sequenz beginnt mit Null (nullte Fibonacci-Zahl ist Null): 0,1,1,2,3,5,8,13, ...Sie können dies tun, indem Sie auch eine Matrix von Ganzzahlen potenzieren. Wenn Sie die Matrix haben
dann
(M^n)[1, 2]
wird gleich dern
th Fibonacci-Zahl sein, wenn[]
es sich um einen Matrixindex und eine Matrixexponentiation^
handelt. Für eine Matrix mit fester Größe kann die Exponentiation zu einer positiven Integralleistung in O (log n) -Zeit auf die gleiche Weise wie bei reellen Zahlen erfolgen.BEARBEITEN: Abhängig von der Art der gewünschten Antwort können Sie möglicherweise mit einem Algorithmus mit konstanter Zeit davonkommen. Wie die anderen Formeln zeigen,
n
wächst die th Fibonacci-Zahl exponentiell mitn
. Selbst bei 64-Bit-Ganzzahlen ohne Vorzeichen benötigen Sie nur eine Nachschlagetabelle mit 94 Einträgen, um den gesamten Bereich abzudecken.ZWEITE BEARBEITUNG: Das erste Exponential der Matrix mit einer Eigendekomposition entspricht genau der folgenden Lösung von JDunkerly. Die Eigenwerte dieser Matrix sind
(1 + sqrt(5))/2
und(1 - sqrt(5))/2
.quelle
Wikipedia hat eine geschlossene Lösung http://en.wikipedia.org/wiki/Fibonacci_number
Oder in c #:
quelle
|1 - phi|^n / sqrt(5) < 1/2
whenn
eine nichtnegative Ganzzahl ist.Für wirklich große funktioniert diese rekursive Funktion. Es werden die folgenden Gleichungen verwendet:
Sie benötigen eine Bibliothek, mit der Sie mit großen Ganzzahlen arbeiten können. Ich benutze die BigInteger-Bibliothek von https://mattmccutchen.net/bigint/ .
Beginnen Sie mit einer Reihe von Fibonacci-Zahlen. Verwenden Sie Fibs [0] = 0, Fibs [1] = 1, Fibs [2] = 1, Fibs [3] = 2, Fibs [4] = 3 usw. In diesem Beispiel verwende ich ein Array der ersten 501 (0 zählen). Die ersten 500 Fibonacci-Zahlen ungleich Null finden Sie hier: http://home.hiwaay.net/~jalison/Fib500.html . Es erfordert ein wenig Bearbeitung, um es in das richtige Format zu bringen, aber das ist nicht zu schwierig.
Dann können Sie mit dieser Funktion (in C) eine beliebige Fibonacci-Zahl finden:
Ich habe dies für die 25.000ste Fibonacci-Zahl und dergleichen getestet.
quelle
Hier ist meine rekursive Version, die log (n) mal rekursiv ist. Ich denke, dass es am einfachsten ist, in rekursiver Form zu lesen:
Es funktioniert , weil Sie berechnen kann
fib(n),fib(n-1)
unter Verwendung ,fib(n-1),fib(n-2)
wenn n ungerade ist , und wenn n gerade ist, können Sie berechnen ,fib(n),fib(n-1)
verwendenfib(n/2),fib(n/2-1)
.Der Basisfall und der ungerade Fall sind einfach. Um den geraden Fall abzuleiten, beginnen Sie mit a, b, c als aufeinanderfolgende Fibonacci-Werte (z. B. 8,5,3) und schreiben Sie sie in eine Matrix mit a = b + c. Beachten:
Daraus sehen wir, dass eine Matrix der ersten drei Fibonacci-Zahlen, mal eine Matrix aus drei aufeinanderfolgenden Fibonacci-Zahlen, gleich der nächsten ist. Also wissen wir das:
Damit:
Die Vereinfachung der rechten Seite führt zum geraden Fall.
quelle
mit R.
quelle
Die Festkomma-Arithmetik ist ungenau. Jasons C # -Code gibt eine falsche Antwort für n = 71 (308061521170130 anstelle von 308061521170129) und darüber hinaus.
Verwenden Sie für eine korrekte Antwort ein Computeralgebrasystem. Sympy ist eine solche Bibliothek für Python. Es gibt eine interaktive Konsole unter http://live.sympy.org/ . Kopieren Sie diese Funktion und fügen Sie sie ein
Dann berechnen
Vielleicht möchten Sie versuchen, zu inspizieren
phi
.quelle
Abgesehen von der Feinabstimmung durch mathematische Ansätze besteht eine der besten optimalen Lösungen (glaube ich) darin, ein Wörterbuch zu verwenden, um wiederholte Berechnungen zu vermeiden.
Wir beginnen mit einem einfachen Wörterbuch (die ersten beiden Werte der Fibonacci-Sequenz) und fügen dem Wörterbuch ständig Fibonacci-Werte hinzu.
Die ersten 100000 Fibonacci-Werte (Intel Xeon CPU E5-2680 bei 2,70 GHz, 16 GB RAM, Windows 10-64-Bit-Betriebssystem) dauerten etwa 0,7 Sekunden.
quelle
Siehe hier den Algorithmus zum Teilen und Erobern
Der Link hat einen Pseudocode für die Matrixexponentiation, die in einigen anderen Antworten auf diese Frage erwähnt wurde.
quelle
Sie können die seltsame Quadratwurzelgleichung verwenden, um eine genaue Antwort zu erhalten. Der Grund ist, dass $ \ sqrt (5) $ am Ende herausfällt. Sie müssen nur die Koeffizienten mit Ihrem eigenen Multiplikationsformat verfolgen.
quelle
Hier ist ein Einzeiler, der F (n) unter Verwendung von ganzen Zahlen der Größe O (n) in O (log n) -Arithmetikoperationen berechnet:
Die Verwendung von ganzen Zahlen der Größe O (n) ist sinnvoll, da dies mit der Größe der Antwort vergleichbar ist.
Um dies zu verstehen, sei phi der goldene Schnitt (die größte Lösung für x ^ 2 = x + 1) und F (n) die n-te Fibonacci-Zahl, wobei F (0) = 0, F (1) = F. (2) = 1
Nun ist phi ^ n = F (n-1) + F (n) phi.
Auch Zahlen der Form (a + b * phi), wobei a, b ganze Zahlen sind, werden unter Multiplikation geschlossen.
Mit dieser Darstellung kann man Phi ^ n in O (log n) Integer-Operationen unter Verwendung von Exponentiation durch Quadrieren berechnen. Das Ergebnis ist F (n-1) + F (n) phi, woraus man die n-te Fibonacci-Zahl ablesen kann.
Beachten Sie, dass der Großteil dieses Codes eine Standardfunktion zur Potenzierung durch Quadrieren ist.
Um auf die Einzeiler , die diese Antwort beginnt, kann man feststellen , dass repräsentiert phi durch eine ausreichend große ganze Zahl
X
, kann man durchführen(a+b*phi)(c+d*phi)
als Integer - Operation(a+bX)(c+dX) modulo (X^2-X-1)
. Dannpow
kann die Funktion durch die Standard-Python-pow
Funktion ersetzt werden (die bequemerweise ein drittes Argument enthält,z
das das Ergebnis modulo berechnetz
. DasX
gewählte ist2<<i
.quelle
Ich bin auf einige der Methoden zur Berechnung von Fibonacci mit effizienter Zeitkomplexität gestoßen.
Methode 1 - Dynamische Programmierung Nun ist hier die Unterstruktur allgemein bekannt, daher werde ich direkt zur Lösung springen -
Eine platzoptimierte Version von oben kann wie folgt durchgeführt werden:
Methode 2- (Verwenden der Potenz der Matrix {{1,1}, {1,0}})
Dies ist ein O (n), das auf der Tatsache beruht, dass, wenn wir die Matrix M = {{1,1}, {1,0}} n-mal mit sich selbst multiplizieren (mit anderen Worten die Leistung (M, n) berechnen), dann Wir erhalten die (n + 1) -te Fibonacci-Zahl als Element in Zeile und Spalte (0, 0) in der resultierenden Matrix. Diese Lösung hätte O (n) Zeit.
Die Matrixdarstellung gibt den folgenden geschlossenen Ausdruck für die Fibonacci-Zahlen: Fibonaccimatrix
Dies kann optimiert werden, um in O (Logn) -Zeitkomplexität zu arbeiten. Wir können eine rekursive Multiplikation durchführen, um die Leistung (M, n) in der vorherigen Methode zu erhalten.
Methode 3 (O (log n) Zeit) Nachfolgend finden Sie eine weitere interessante Wiederholungsformel, mit der die n-te Fibonacci-Zahl in O (log n) Zeit ermittelt werden kann.
Wenn n gerade ist, dann ist k = n / 2: F (n) = [2 · F (k - 1) + F (k)] · F (k)
Wenn n ungerade ist, dann ist k = (n + 1) / 2 F (n) = F (k) * F (k) + F (k-1) * F (k-1) Wie funktioniert diese Formel? Die Formel kann aus der obigen Matrixgleichung abgeleitet werden. Fibonaccimatrix
Wenn wir die Determinante auf beiden Seiten nehmen, erhalten wir (-1) n = Fn + 1Fn-1 - Fn2. Da außerdem AnAm = An + m für jede quadratische Matrix A ist, können die folgenden Identitäten abgeleitet werden (sie werden aus zwei verschiedenen Koeffizienten von erhalten das Matrixprodukt)
FmFn + Fm-1Fn-1 = Fm + n-1
Indem Sie n = n + 1 setzen,
FmFn + 1 + Fm-1Fn = Fm + n
Setzen von m = n
F2n-1 = Fn2 + Fn-12
F2n = (Fn-1 + Fn + 1) Fn = (2Fn-1 + Fn) Fn (Quelle: Wiki)
Um die Formel zu beweisen, müssen wir einfach Folgendes tun: Wenn n gerade ist, können wir k = n / 2 setzen. Wenn n ungerade ist, können wir k = (n + 1) / 2 setzen
Methode 4 - Verwenden einer Formel Bei dieser Methode implementieren wir direkt die Formel für den n-ten Term in der Fibonacci-Reihe. Zeit O (1) Raum O (1) Fn = {[(√5 + 1) / 2] ^ n} / √5
Referenz: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
quelle
Wir sollten zunächst beachten Sie, dass Fibonacci - Zahlen
(F(n))
wachsen sehr schnell mitn
und kann nicht in dargestellt werden 64 Bits fürn
größer als 93. So ein Programm für sie für eine solche Berechnungn
Bedarf zusätzliche Mechanismen zu verwenden , auf diesen großen Zahlen zu operieren. Wenn man nur die Anzahl der Operationen (mit großer Anzahl) berücksichtigt, erfordert der Algorithmus, um sie sequentiell zu berechnen, eine lineare Anzahl von Operationen.Wir können von der folgenden Identität über Fibonacci-Zahlen profitieren:
(Ein Symbol wie A ^ 2 bezeichnet das Quadrat von A).
Also, wenn wir wissen ,
F(m)
undF(m+1)
können wir direkt berechnenF(2m)
undF(2m+1)
.Betrachten Sie die binäre Darstellung von
n
. Beachten Sie, dassx = 1
wir beginnend mitx = n
iterativ verdoppeln und möglicherweise 1 hinzufügen könnenx
. Dies kann durch Iterieren über die Bits vonn
und Überprüfen, ob es 0 oder 1 ist, erfolgen.Die Idee ist, dass wir
F(x)
synchron bleiben könnenx
. In jeder solchen Iteration können wir, wenn wir verdoppelnx
und möglicherweise 1 addierenx
, auch den neuen Wert derF(x)
Verwendung des früheren Werts vonF(x)
undF(x+1)
mit den obigen Gleichungen berechnen.Da die Anzahl der Iterationen logarithmisch ist
n
, sind auch die Gesamtoperationen (mit großer Anzahl) logarithmischn
.Weitere Einzelheiten finden Sie im Abschnitt "Verbesserter Algorithmus" dieses Artikels .
quelle