Fibonacci Sequence
La suite de Fibonacci a chaque terme égal à la somme des deux précédents (0,1,1,2,3,5,8...) ; elle est liée au nombre d'or et apparaît largement dans la nature et les algorithmes.
Objectif
Décrire des motifs de croissance, présents dans les phénomènes naturels et l'analyse de complexité algorithmique.
Mécanisme
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Forme close (formule de Binet) : F(n)=(φ^n-ψ^n)/√5, où φ=(1+√5)/2 est le nombre d'or. L'exponentiation matricielle ou la méthode de doublement rapide la calcule en O(log n). La récursion naïve est exponentiellement lente, en O(φ^n).
Cas d’usage
- Analyse de complexité algorithmique
- Calcul d'indicateurs techniques (retracement de Fibonacci)
- Modélisation de motifs naturels
- Enseignement de la programmation dynamique
Exemples
- entrée
F(10)Output550,1,1,2,3,5,8,13,21,34,55
Erreurs courantes
- Naive recursion recomputes subproblems and runs exponentially slow
- Use memoization or fast matrix exponentiation
Termes associés
Factorial
La factorielle n! = n×(n-1)×...×1 fonde les permutations et combinaisons ; elle croît extrêmement vite, 20! dépassant déjà la plage des entiers 64 bits. GLOSSAIRE
Big O Notation
La notation grand O décrit la borne supérieure asymptotique d'une fonction, utilisée pour analyser la complexité temporelle/spatiale des algorithmes en ignorant les constantes et les termes d'ordre inférieur. GLOSSAIRE
BigInteger
BigInteger est un type d'entier à précision arbitraire, non limité par une taille de mot fixe, utilisé pour des calculs au-delà de la plage des entiers natifs (comme la cryptographie et la combinatoire). GLOSSAIRE