Fibonacci Sequence
Die Fibonacci-Folge hat jedes Glied gleich der Summe der beiden vorherigen (0,1,1,2,3,5,8...); sie hängt mit dem goldenen Schnitt zusammen und tritt in Natur und Algorithmen vielfach auf.
Zweck
Wachstumsmuster beschreiben, die in Naturphänomenen und in der Komplexitätsanalyse von Algorithmen auftreten.
Mechanismus
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Geschlossene Form (Binet-Formel): F(n)=(φ^n-ψ^n)/√5, wobei φ=(1+√5)/2 der goldene Schnitt ist. Matrixpotenzierung oder Fast Doubling berechnen sie in O(log n). Naive Rekursion ist exponentiell langsam mit O(φ^n).
Anwendungsfälle
- Komplexitätsanalyse von Algorithmen
- Berechnung technischer Indikatoren (Fibonacci-Retracement)
- Modellierung natürlicher Muster
- Unterricht zur dynamischen Programmierung
Beispiele
- Eingabe
F(10)Output550,1,1,2,3,5,8,13,21,34,55
Häufige Fehler
- Naive recursion recomputes subproblems and runs exponentially slow
- Use memoization or fast matrix exponentiation
Verwandte Begriffe
Factorial
Die Fakultät n! = n×(n-1)×...×1 ist die Grundlage von Permutationen und Kombinationen; sie wächst extrem schnell, 20! überschreitet bereits den 64-Bit-Integer-Bereich. GLOSSAR
Big O Notation
Die Big-O-Notation beschreibt die asymptotische obere Schranke einer Funktion und dient der Analyse der Zeit-/Speicherkomplexität von Algorithmen unter Vernachlässigung von Konstanten und niedrigeren Termen. GLOSSAR
BigInteger
BigInteger ist ein Ganzzahltyp mit beliebiger Genauigkeit, der nicht an eine feste Wortbreite gebunden ist, und dient Berechnungen jenseits des nativen Integerbereichs (etwa Kryptographie und Kombinatorik). GLOSSAR