JavaScript-Algorithmen: Fibonacci-Folge lösen (LeetCode)

Die allgemein bezeichneten Fibonacci-ZahlenF(n) bilden eine Folge, die als Fibonacci-Folge bezeichnet wird, so dass jede Zahl die Summe der beiden vorhergehenden ist, beginnend mit 0und 1. Die Zahlen in der folgenden ganzzahligen Folge 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Das ist

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Beispiel 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

Zur Lösung dieses Problems gibt es mehrere Möglichkeiten: Rekursionsansatz.

Rekursionsansatz

Eine einfache Methode, die eine direkte rekursive Implementierung einer mathematischen Wiederholungsrelation ist. Der langsamste Weg, dieses Problem zu lösen, da es eine exponentielle Zeitkomplexität : O(2^N) und Raumkomplexität : O(N) erfordert .

Dynamische Programmierung mit Memoisierung (Top-Down-Ansatz)

Wir können die wiederholte rekursive Arbeit vermeiden, indem wir die bisher berechneten Fibonacci-Zahlen speichern. Wir müssen nur alle Werte in einer Karte speichern. Zeitkomplexität : O(N) und Raumkomplexität : O(N) .

Iterationsansatz _

Iteration mit Lösung aller Teilprobleme und Rückgabe der Antwort für N Elemente unter Verwendung bereits berechneter Fibonacci-Werte. Zeitkomplexität : O(N) und Raumkomplexität : O(N) .

Iterationsansatz ( platzoptimiert)

Wir können den Iterationsansatz optimieren, indem wir nur die beiden vorherigen Zahlen speichern, weil das alles ist, was wir brauchen, um die nächste Fibonacci-Zahl in Reihe zu bekommen. Zeitkomplexität : O(N) und Raumkomplexität : O(1) .

Matrix-Potenzierungs-Ansatz

Verwenden Sie die Matrixexponentiation, um die Fibonacci-Zahl aus dem Element bei (0, 0) in der resultierenden Matrix zu erhalten. Um dies zu tun, können wir uns auf die Matrixgleichung für die Fibonacci-Folge stützen, um die N-te Fibonacci-Zahl zu finden:

Wie diese Formel funktioniert, können Sie im Wiki nachsehen

Diese Lösung hat: Zeitkomplexität : O(logN) und Raumkomplexität : O(logN) .

Mathematischer Ansatz

Wir können Folgendes verwenden golden ratio forumula:

Hier ist ein Link , um mehr darüber zu erfahren, wie die Fibonacci-Folge und der Goldene Schnitt funktionieren.

Diese Lösung hat: Zeitkomplexität : O(logN) und Raumkomplexität : O(1) .

Manchmal ist es auch erforderlich, keinen Wert für ein bestimmtes N zurückzugeben, sondern ein Array von Fibonacci-Elementen bis zu einem bestimmten N zurückzugeben.

Beispiel:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

und Dynamische Programmierung mit Memoisierung mit kleinen Änderungen:

Wir haben verschiedene Möglichkeiten zur Lösung des Fibonacci-Problems in Betracht gezogen, die am schwierigsten zu verstehende ist die Matrixexponentiation, aber normalerweise reicht die Kenntnis der 4 vorherigen Methoden für ein Interview aus.

Hoffe, es war nützlich für Sie!

Danke fürs Lesen! Seh dich später.

Weitere Inhalte auf PlainEnglish.io . Melden Sie sich für unseren kostenlosen wöchentlichen Newsletter an . Folgen Sie uns auf Twitter , LinkedIn , YouTube und Discord . Interessiert an Growth Hacking? Schauen Sie sich die Schaltung an .