Fibonacci Number

Q: Wie hoch ist die Zeitkomplexität der rekursiven Fibonacci-Funktion?

Die naive Rekursion führt 2 × F(n+1) - 1 Aufrufe aus, eine Anzahl, die wie 1.618^n wächst und üblicherweise als O(2^n) geschrieben wird. Für n = 45 sind das etwa 3.7 × 10^9 Aufrufe. Wenn jedes Ergebnis einmal in einer Tabelle oder in zwei Variablen gespeichert wird, sinkt die Anzahl auf O(n) .

Q: Wie löst man Fibonacci mit dynamischer Programmierung?

Beginne mit der Rekurrenz F(n) = F(n-1) + F(n-2) und berechne die Werte in aufsteigender Reihenfolge von n , wobei du jeden Wert speicherst. Du kannst eine Tabelle von unten nach oben füllen oder die rekursive Funktion beibehalten und ihre Ergebnisse zwischenspeichern – das nennt man Memoisierung. In beiden Fällen wird jeder Wert nur einmal berechnet, sodass der Gesamtaufwand O(n) beträgt.

Q: Kann Fibonacci mit O(1) Speicherplatz berechnet werden?

Ja. Jede Zahl hängt nur von den beiden vorherigen ab, daher reichen zwei Variablen aus. Behalte die letzten beiden Werte bei und schiebe sie bei jedem Schritt weiter. Das ergibt eine Laufzeit von O(n) bei zusätzlichem Speicherplatz von O(1) .

Q: Gibt es einen schnelleren Weg als O(n)?

Ja. Die Matrix [[1, 1], [1, 0]] , potenziert mit n , enthält F(n) in ihrer oberen rechten Ecke, und wiederholtes Quadrieren berechnet diese Potenz mit O(log n) Matrixmultiplikationen. Es gibt auch eine geschlossene Formel mit Potenzen des Goldenen Schnitts, aber sie arbeitet mit Gleitkommazahlen und verliert an Genauigkeit, wenn n wächst. Daher werden die ganzzahligen Methoden bevorzugt.

EinsteigerDynamische Programmierung Rekursion

+10

Die Fibonacci-Zahlen beginnen mit F(0) = 0 und F(1) = 1, und jede spätere Zahl ist die Summe der beiden vorherigen: F(n) = F(n-1) + F(n-2). Die Folge beginnt mit 0, 1, 1, 2, 3, 5, 8, 13. Deine Funktion erhält n und gibt F(n) zurück.

Funktion

fib(n: integer) → integer

ninteger: die Position in der Fibonacci-Folge, von 0 an gezählt
Gibt zurückinteger: die Fibonacci-Zahl F(n)

Einschränkungen

0 ≤ n ≤ 45
Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl: F(45) = 1134903170.

Beispiele

Eingabe: n = 4
Ausgabe: 3
Erklärung: Zähle vom Anfang aus weiter: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 und F(4) = 2 + 1 = 3.

Eingabe: n = 10
Ausgabe: 55
Erklärung: Die Folge ab Index 0 lautet 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Die Zahl am Index 10 ist 34 + 21 = 55.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du F(n) in O(log n) Zeit berechnen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Definition ist bereits eine rekursive Funktion, und wenn man sie als solche formuliert, erhält man die richtige Antwort. Der Haken ist die Laufzeit: Die beiden rekursiven Aufrufe wiederholen gegenseitig ihre Arbeit, und die Anzahl der Aufrufe wächst exponentiell mit n. Dynamische Programmierung behebt das, indem sie jede Fibonacci-Zahl genau einmal berechnet, von unten nach oben. Im letzten Schritt werden nur die beiden Zahlen behalten, die für die nächste benötigt werden.

Rekursion direkt aus der Definition

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Übersetze die Definition Wort für Wort. fib(0) ist 0, fib(1) ist 1, und alles Größere gibt fib(n-1) + fib(n-2) zurück. Jede Aufrufkette endet in einem der beiden Basisfälle, also ist die Antwort korrekt.

Zähle nun die Aufrufe. fib(5) ruft fib(4) und fib(3) auf, aber fib(4) ruft fib(3) erneut auf. Am Ende wird fib(3) zweimal ausgeführt, fib(2) dreimal und fib(1) fünfmal, und fib(5) führt insgesamt 15 Aufrufe aus. Dieselben Werte werden immer wieder neu berechnet.

Die Anzahl der Aufrufe folgt den Fibonacci-Zahlen selbst: Die Berechnung von F(n) führt zu 2 × F(n+1) - 1 Aufrufen. Für n = 45 sind das etwa 3.7 × 10^9 Aufrufe, viel zu viele für ein Zeitlimit. Die Schranke wird üblicherweise als O(2^n) geschrieben; das exakte Wachstum beträgt etwa 1.618^n. Die Rekursion ist nur n Ebenen tief, daher benötigt der Stack O(n) Speicherplatz.

Algorithmus

Wenn n 0 oder 1 ist, gib n zurück.
Andernfalls rufe die Funktion mit n-1 und n-2 auf.
Gib die Summe der beiden Ergebnisse zurück.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Eine Tabelle von unten nach oben ausfüllen

Idee

Die Rekursion ist nur deshalb langsam, weil sie vergisst. Wenn du jede Fibonacci-Zahl beim ersten Berechnen aufschreibst, kostet jede einzelne nur eine Addition. Lege eine Tabelle f mit Plätzen für die Indizes 0 bis n an, setze f[0] = 0 und f[1] = 1 und fülle den Rest von links nach rechts mit f[i] = f[i-1] + f[i-2].

Die Reihenfolge von links nach rechts macht es möglich: Wenn du f[i] erreichst, stehen die beiden benötigten Zahlen bereits in der Tabelle. Für n = 10 füllt sich die Tabelle mit 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, und die Antwort ist der letzte Eintrag.

Das ist dynamische Programmierung in ihrer einfachsten Form: eine Rekursionsgleichung plus eine Tabelle mit Antworten auf kleinere Fälle. Es gibt n-1 Additionen, der Zeitaufwand beträgt O(n), und die Tabelle enthält n + 1 Zahlen, der Speicherbedarf beträgt also O(n). n = 45 erfordert jetzt 44 Additionen statt Milliarden von Aufrufen.

Algorithmus

Wenn n 0 oder 1 ist, gib n zurück.
Erstelle eine Tabelle mit n + 1 Zahlen, wobei f[0] = 0 und f[1] = 1 gilt.
Setze für i von 2 bis n f[i] = f[i-1] + f[i-2].
Gib f[n] zurück.

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Behalte nur die letzten zwei Zahlen

Idee

Sieh dir an, welche Werte die Tabellenschleife liest. Um f[i] zu berechnen, braucht sie f[i-1] und f[i-2] und nichts Älteres, daher sind alle früheren Einträge überflüssig. Verwende statt einer Tabelle zwei Variablen: prev enthält die Zahl von zwei Schritten zuvor und curr die Zahl von einem Schritt zuvor.

Beginne mit prev = 0 und curr = 1, also F(0) und F(1). Berechne bei jedem Schritt next = prev + curr und verschiebe dann das Paar nach vorn: prev übernimmt den alten Wert von curr, und curr übernimmt next. Für n = 4 bewegt sich das Paar von (0, 1) über (1, 1) und (1, 2) zu (2, 3), und curr = 3 ist die Antwort.

Der Aufwand bleibt bei denselben n-1 Additionen, O(n) Laufzeit und drei Ganzzahlen im Speicher, also O(1) Speicherplatz. Die Reihenfolge der Aktualisierungen ist wichtig: Wenn du prev überschreibst, bevor du es addierst, verwendet die Summe den falschen Wert.

Algorithmus

Wenn n 0 oder 1 ist, gib n zurück.
Setze prev = 0 und curr = 1.
Wiederhole n-1-mal: Berechne next = prev + curr, setze dann prev = curr und curr = next.
Gib curr zurück.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Stolperfallen und Grenzfälle

Fibonacci ist das klassische erste Problem der dynamischen Programmierung, und die meisten Fehler entstehen bei der Rekursion oder bei den ersten beiden Werten.

Die naive Rekursion abgeben. Sie besteht kleine Tests und benötigt dann bei n = 45 Milliarden Aufrufe. Speichere die Ergebnisse in einer Tabelle oder in zwei Variablen.
Mit den falschen Startwerten beginnen. Hier gilt F(0) = 0 und F(1) = 1, also F(2) = 1 und F(10) = 55. Wenn die Folge mit 1, 1 beginnt, verschiebt sich jede Antwort um einen Index.
Die Tabelle ohne Schutz für kleine Werte von n aufbauen. Für n = 0 hat eine Tabelle der Größe n + 1 = 1 keinen Platz für f[1], und der Schreibzugriff liegt außerhalb des gültigen Bereichs. Gib sofort n zurück, wenn n < 2.
Das Wertepaar in der falschen Reihenfolge aktualisieren. Auf prev = curr gefolgt von curr = prev + curr wird der neue Wert von prev addiert und curr verdoppelt. Berechne die Summe zuerst in next, oder verwende eine simultane Zuweisung, sofern die Sprache eine solche unterstützt.
Einen Schritt zu weit gehen. Eine Schleife, die auch F(n+1) berechnet, erreicht am Grenzwert F(46) = 1836311903, was nur durch Glück noch in 32 Bit passt. F(47) passt nicht.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der rekursiven Fibonacci-Funktion?

Die naive Rekursion führt 2 × F(n+1) - 1 Aufrufe aus, eine Anzahl, die wie 1.618^n wächst und üblicherweise als O(2^n) geschrieben wird. Für n = 45 sind das etwa 3.7 × 10^9 Aufrufe. Wenn jedes Ergebnis einmal in einer Tabelle oder in zwei Variablen gespeichert wird, sinkt die Anzahl auf O(n).

Wie löst man Fibonacci mit dynamischer Programmierung?

Beginne mit der Rekurrenz F(n) = F(n-1) + F(n-2) und berechne die Werte in aufsteigender Reihenfolge von n, wobei du jeden Wert speicherst. Du kannst eine Tabelle von unten nach oben füllen oder die rekursive Funktion beibehalten und ihre Ergebnisse zwischenspeichern – das nennt man Memoisierung. In beiden Fällen wird jeder Wert nur einmal berechnet, sodass der Gesamtaufwand O(n) beträgt.

Kann Fibonacci mit O(1) Speicherplatz berechnet werden?

Ja. Jede Zahl hängt nur von den beiden vorherigen ab, daher reichen zwei Variablen aus. Behalte die letzten beiden Werte bei und schiebe sie bei jedem Schritt weiter. Das ergibt eine Laufzeit von O(n) bei zusätzlichem Speicherplatz von O(1).

Gibt es einen schnelleren Weg als O(n)?

Ja. Die Matrix [[1, 1], [1, 0]], potenziert mit n, enthält F(n) in ihrer oberen rechten Ecke, und wiederholtes Quadrieren berechnet diese Potenz mit O(log n) Matrixmultiplikationen. Es gibt auch eine geschlossene Formel mit Potenzen des Goldenen Schnitts, aber sie arbeitet mit Gleitkommazahlen und verliert an Genauigkeit, wenn n wächst. Daher werden die ganzzahligen Methoden bevorzugt.

Python

def fib(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

n = 4

Erwartet

Fibonacci Number

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Rekursion direkt aus der Definition

Eine Tabelle von unten nach oben ausfüllen

Behalte nur die letzten zwei Zahlen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben