Fibonacci comme exemple de programmation dynamique

La récurrence de Fibonacci est

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.$$

Une récursion naïve développe plusieurs fois les mêmes sous-problèmes et prend un temps exponentiel. La mémoïsation réduit l'ensemble accessible à $n+1$ états ; une évaluation ascendante rend explicite l'ordre de leurs dépendances.

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

Compression de l'état

Pour calculer $F_n$, une table conserverait toutes les valeurs de $F_0$ à $F_n$. La transition ne lit que les deux précédentes : deux variables suffisent donc.

• temps : $O(n)$ opérations arithmétiques ;
• état auxiliaire : $O(1)$ variables entières ;
• la taille en bits des entiers augmente tout de même avec $n$ : pour de très grands indices, la complexité en bits d'une addition n'est pas constante.

Ce que montre cet exemple

Fibonacci aide à reconnaître les sous-problèmes qui se chevauchent et les compressions de mémoire sûres, mais ne représente pas bien les problèmes d'optimisation. En exploitant une structure algébrique supplémentaire, la méthode de doublement rapide ou les matrices calculent $F_n$ avec une profondeur de récurrence en $O(\log n)$.

Dans les exemples Python mémoïsés, évitez un dictionnaire mutable comme argument par défaut : la propriété et la durée de vie du cache doivent être explicites.

Trace et coût des entiers

Avant l'itération k, (previous, current) vaut (F_k, F_(k+1)). L'affectation simultanée préserve cet invariant ; après n itérations, previous est la réponse. Pour n=5, les paires successives sont (0,1), (1,1), (1,2), (2,3), (3,5), (5,8) : le résultat est 5. Pour n=0, la boucle ne s'exécute pas et renvoie 0 ; un n négatif est refusé. L'entrée doit être entière.

Les deux variables représentent un nombre constant d'entiers, pas un nombre constant de mots machine de taille fixe pour tout n. Les nombres de Fibonacci occupent Θ(n) bits. Avec une addition linéaire en leur taille, la boucle coûte donc O(n²) opérations sur les bits et O(n) bits auxiliaires.

assert fibonacci(0) == 0
assert fibonacci(5) == 5

Source

• MIT OpenCourseWare : programmation dynamique I

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.