Fibonacci Number

Q: Quelle est la complexité temporelle de la fonction récursive de Fibonacci ?

La récursion naïve effectue 2 × F(n+1) - 1 appels, un nombre qui croît comme 1.618^n et que l’on écrit généralement O(2^n) . Pour n = 45 , cela représente environ 3.7 × 10^9 appels. En stockant chaque résultat une seule fois, dans un tableau ou dans deux variables, on ramène ce nombre à O(n) .

Q: Comment résoudre le problème de Fibonacci avec la programmation dynamique ?

Partez de la récurrence F(n) = F(n-1) + F(n-2) et calculez les valeurs par ordre croissant de n , en stockant chacune d’elles. Vous pouvez remplir un tableau de bas en haut, ou conserver la fonction récursive et mettre ses résultats en cache, ce qu’on appelle la mémoïsation. Dans les deux cas, chaque valeur est calculée une seule fois, donc le travail total est O(n) .

Q: Peut-on calculer Fibonacci avec un espace O(1) ?

Oui. Chaque nombre dépend uniquement des deux précédents, donc deux variables suffisent. Conservez les deux dernières valeurs et faites-les avancer à chaque étape. Cela donne un temps en O(n) avec un espace supplémentaire en O(1) .

Q: Existe-t-il une méthode plus rapide que O(n) ?

Oui. La matrice [[1, 1], [1, 0]] élevée à la puissance n contient F(n) dans son coin supérieur droit, et l’exponentiation par élévation au carré répétée calcule cette puissance en O(log n) multiplications matricielles. Il existe également une formule fermée faisant intervenir les puissances du nombre d’or, mais elle utilise des nombres à virgule flottante et perd en précision lorsque n augmente ; les méthodes entières sont donc préférables.

DébutantProgrammation dynamique Récursivité

+10

Les nombres de Fibonacci commencent par F(0) = 0 et F(1) = 1, et chaque nombre suivant est la somme des deux qui le précèdent : F(n) = F(n-1) + F(n-2). La suite commence par 0, 1, 1, 2, 3, 5, 8, 13. Votre fonction reçoit n et renvoie F(n).

Fonction

fib(n: integer) → integer

ninteger: la position dans la suite de Fibonacci, en comptant à partir de 0
Renvoieinteger: le nombre de Fibonacci F(n)

Contraintes

0 ≤ n ≤ 45
La réponse tient dans un entier signé de 32 bits : F(45) = 1134903170.

Exemples

Entrée: n = 4
Sortie: 3
Explication: Compte à partir du début : F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, et F(4) = 2 + 1 = 3.

Entrée: n = 10
Sortie: 55
Explication: La séquence à partir de l’indice 0 est 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Le nombre à l’indice 10 est 34 + 21 = 55.

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu calculer F(n) en O(log n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La définition est déjà une fonction récursive, et l’écrire sous cette forme donne la bonne réponse. Le piège, c’est le temps d’exécution : les deux appels récursifs refont le travail l’un de l’autre, et le nombre d’appels augmente de façon exponentielle avec n. La programmation dynamique résout ce problème en calculant chaque nombre de Fibonacci une seule fois, en partant du bas. La dernière étape ne conserve que les deux nombres dont le suivant a besoin.

La récursion directement à partir de la définition

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Traduisez la définition mot à mot. fib(0) vaut 0, fib(1) vaut 1, et toute valeur supérieure renvoie fib(n-1) + fib(n-2). Chaque chaîne d’appels se termine dans l’un des deux cas de base, donc la réponse est correcte.

Maintenant, comptons les appels. fib(5) appelle fib(4) et fib(3), mais fib(4) appelle de nouveau fib(3). Au final, fib(3) s’exécute deux fois, fib(2) trois fois et fib(1) cinq fois, et fib(5) effectue 15 appels au total. Les mêmes valeurs sont recalculées encore et encore.

Le nombre d’appels suit les nombres de Fibonacci eux-mêmes : le calcul de F(n) effectue 2 × F(n+1) - 1 appels. Pour n = 45, cela représente environ 3.7 × 10^9 appels, bien trop pour respecter une limite de temps. La borne s’écrit généralement O(2^n) ; la croissance exacte est d’environ 1.618^n. La récursion n’a que n niveaux de profondeur, donc la pile nécessite un espace de O(n).

Algorithme

Si n est 0 ou 1, renvoie n.
Sinon, appelle la fonction sur n-1 et sur n-2.
Renvoie la somme des deux résultats.

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

Remplir un tableau de bas en haut

Intuition

La récursion est lente uniquement parce qu’elle oublie. Si tu notes chaque nombre de Fibonacci la première fois que tu le calcules, chacun ne coûte qu’une seule addition. Crée un tableau f avec des emplacements pour les indices de 0 à n, définis f[0] = 0 et f[1] = 1, puis remplis le reste de gauche à droite avec f[i] = f[i-1] + f[i-2].

C’est l’ordre de gauche à droite qui permet à la méthode de fonctionner : quand tu arrives à f[i], les deux nombres dont il a besoin sont déjà dans le tableau. Pour n = 10, le tableau se remplit ainsi : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, et la réponse se trouve dans le dernier emplacement.

C’est la programmation dynamique dans sa forme la plus simple : une relation de récurrence et un tableau de réponses aux cas plus petits. Il y a n-1 additions, une complexité temporelle de O(n), et le tableau contient n + 1 nombres, soit un espace de O(n). n = 45 ne nécessite désormais que 44 additions au lieu de milliards d’appels.

Algorithme

Si n vaut 0 ou 1, renvoie n.
Crée un tableau de n + 1 nombres avec f[0] = 0 et f[1] = 1.
Pour i de 2 à n, définis f[i] = f[i-1] + f[i-2].
Renvoie f[n].

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]

Conservez uniquement les deux derniers nombres

Intuition

Observez ce que lit la boucle sur la table. Pour remplir f[i], elle a besoin de f[i-1] et de f[i-2], et de rien de plus ancien : toutes les cases précédentes sont donc inutiles. Utilisez deux variables au lieu d’une table : prev contient le nombre situé deux étapes en arrière et curr, celui situé une étape en arrière.

Commencez avec prev = 0 et curr = 1, qui correspondent à F(0) et F(1). À chaque étape, calculez next = prev + curr, puis faites avancer la paire : prev prend l’ancienne valeur de curr, et curr prend next. Pour n = 4, la paire passe de (0, 1) à (1, 1), (1, 2) et (2, 3), et curr = 3 est la réponse.

Le travail reste le même : n-1 additions, un temps de O(n), et trois entiers en mémoire, soit un espace de O(1). L’ordre des mises à jour est important : si vous écrasez prev avant de l’additionner, la somme utilise la mauvaise valeur.

Algorithme

Si n vaut 0 ou 1, retourne n.
Définis prev = 0 et curr = 1.
Répète n-1 fois : calcule next = prev + curr, puis définis prev = curr et curr = next.
Retourne curr.

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

Pièges et cas limites

Fibonacci est le premier problème classique de programmation dynamique, et la plupart des bogues viennent de la récursion ou des deux premières valeurs.

Remettre la version récursive naïve. Elle passe les petits tests, puis nécessite des milliards d’appels pour n = 45. Stockez les résultats dans un tableau ou dans deux variables.
Se tromper sur le début. Ici, F(0) = 0 et F(1) = 1, donc F(2) = 1 et F(10) = 55. Commencer la séquence par 1, 1 décale chaque réponse d’un indice.
Construire le tableau sans vérifier les petites valeurs de n. Pour n = 0, un tableau de taille n + 1 = 1 ne contient pas de case pour f[1], et y écrire dépasse ses limites. Retournez immédiatement n lorsque n < 2.
Mettre à jour la paire dans le mauvais ordre. prev = curr suivi de curr = prev + curr additionne le nouveau prev et double curr. Calculez d’abord la somme dans next, ou utilisez une affectation simultanée si le langage le permet.
Exécuter une étape de trop. Une boucle qui calcule aussi F(n+1) atteint F(46) = 1836311903 à la limite, ce qui tient encore sur 32 bits par chance. Ce n’est pas le cas de F(47).

Questions fréquentes4

Quelle est la complexité temporelle de la fonction récursive de Fibonacci ?

La récursion naïve effectue 2 × F(n+1) - 1 appels, un nombre qui croît comme 1.618^n et que l’on écrit généralement O(2^n). Pour n = 45, cela représente environ 3.7 × 10^9 appels. En stockant chaque résultat une seule fois, dans un tableau ou dans deux variables, on ramène ce nombre à O(n).

Comment résoudre le problème de Fibonacci avec la programmation dynamique ?

Partez de la récurrence F(n) = F(n-1) + F(n-2) et calculez les valeurs par ordre croissant de n, en stockant chacune d’elles. Vous pouvez remplir un tableau de bas en haut, ou conserver la fonction récursive et mettre ses résultats en cache, ce qu’on appelle la mémoïsation. Dans les deux cas, chaque valeur est calculée une seule fois, donc le travail total est O(n).

Peut-on calculer Fibonacci avec un espace O(1) ?

Oui. Chaque nombre dépend uniquement des deux précédents, donc deux variables suffisent. Conservez les deux dernières valeurs et faites-les avancer à chaque étape. Cela donne un temps en O(n) avec un espace supplémentaire en O(1).

Existe-t-il une méthode plus rapide que O(n) ?

Oui. La matrice [[1, 1], [1, 0]] élevée à la puissance n contient F(n) dans son coin supérieur droit, et l’exponentiation par élévation au carré répétée calcule cette puissance en O(log n) multiplications matricielles. Il existe également une formule fermée faisant intervenir les puissances du nombre d’or, mais elle utilise des nombres à virgule flottante et perd en précision lorsque n augmente ; les méthodes entières sont donc préférables.