Terminale · Numérique et sciences informatiques

Utiliser la mémoïsation pour éviter de recalculer des sous-problèmes

Transformer une fonction récursive qui recalcule plusieurs fois les mêmes sous-problèmes en une version mémoïsée avec un dictionnaire, et justifier le gain de complexité obtenu.

Aperçu gratuit
Illustration de la fiche « Utiliser la mémoïsation pour éviter de recalculer des sous-problèmes »

Les points essentiels

  • La mémoïsation consiste à stocker dans une structure (le plus souvent un dictionnaire Python) le résultat de chaque sous-problème déjà résolu, afin de le réutiliser au lieu de le recalculer.
  • Elle n'est utile que si les sous-problèmes se chevauchent : la même instance (mêmes arguments) est demandée plusieurs fois dans l'arbre des appels récursifs.

Les mots à connaître

Sous-problème
Instance plus petite du même problème, dont la solution sert à construire celle du problème initial. Par exemple, calculer fib(5) est un sous-problème de fib(6).
Mémoïsation
Technique qui consiste à enregistrer le résultat d'un appel de fonction pour un jeu d'arguments donné, afin de renvoyer directement ce résultat si les mêmes arguments se présentent de nouveau.

Un exemple pour comprendre

La suite de Fibonacci est définie par fib(0)=0, fib(1)=1 et fib(n)=fib(n-1)+fib(n-2) pour n>=2. Écrire une version récursive naïve, compter les appels pour fib(5), puis écrire une version mémoïsée et compter les calculs effectués.

Version naïve : def fib(n): return n if n < 2 else fib(n-1) + fib(n-2). Pour fib(5), le nombre d'appels C(n) vérifie C(0)=C(1)=1 et C(n)=1+C(n-1)+C(n-2), d'où C(2)=3, C(3)=5, C(4)=9, C(5)=15 : 15 appels, dont fib(3) calculé 2 fois, fib(2) 3 fois, fib(1) 5 fois. Version mémoïsée : def fib_memo(n, memo=None): if memo is None: memo = {}; if n in memo: return memo[n]; if n < 2: return n; memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo); return memo[n]. Les valeurs 2, 3, 4 et 5 ne sont calculées qu'une fois chacune (les cas de base 0 et 1 sont immédiats), donc 4 calculs d'addition au lieu de 14 additions pour la version naïve. Dans la version mémoïsée, le nombre d'appels devient linéaire en n, alors qu'il croît exponentiellement dans la version naïve.

Première page de l’Essentiel : Utiliser la mémoïsation pour éviter de recalculer des sous-problèmes
Ketty