4.1 Définition de la mémorisation et ses concepts clés
La mémorisation est une technique d'optimisation qui permet de sauvegarder les résultats des fonctions coûteuses pour pouvoir les réutiliser lors des appels suivants avec les mêmes arguments. Cela réduit le nombre de calculs répétés, augmentant ainsi les performances.
Concepts clés :
1. Mise en cache :
Stockage des résultats d'une fonction dans une certaine structure de données (par exemple, un dictionnaire ou un tableau), afin que lors d'un appel ultérieur avec les mêmes arguments, le résultat déjà sauvegardé puisse être retourné, au lieu de le recalculer.
2. Table de consultation (Lookup Table) :
Structure de données utilisée pour stocker les résultats des appels précédents d'une fonction. Cela pourrait être une table de hachage (dictionnaire) ou un tableau.
3. Appels récursifs :
La mémorisation est particulièrement utile pour les fonctions récursives, où les mêmes sous-tâches peuvent être exécutées plusieurs fois avec les mêmes paramètres.
Complexité temporelle et spatiale des algorithmes optimisés :
Complexité temporelle :
Pour de nombreuses tâches récursives, la mémorisation réduit la complexité temporelle en diminuant le nombre de calculs répétés. Par exemple, le calcul récursif des nombres de Fibonacci a une complexité temporelle de O(2^n), et avec la mémorisation, c'est O(n).
Complexité spatiale :
La complexité spatiale augmente en raison du stockage des résultats dans le cache. C'est généralement O(n) pour une tâche nécessitant la mémorisation.
Résumé :
La mémorisation est une technique puissante d'optimisation des algorithmes récursifs, permettant d'améliorer considérablement leur performance en réduisant le nombre de calculs répétés.
Elle est particulièrement utile pour les tâches où les mêmes sous-tâches sont exécutées plusieurs fois avec les mêmes paramètres. Comprendre les concepts de la mémorisation et son application pratique permet de résoudre efficacement des tâches à forte charge de calcul.
4.2 Exemples d'optimisation
Exemples d'optimisation d'algorithmes récursifs utilisant la mémorisation
Exemple 1 : Nombres de Fibonacci
L'algorithme récursif pour calculer les nombres de Fibonacci sans mémorisation a une complexité temporelle exponentielle. L'utilisation de la mémorisation améliore considérablement les performances.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Exemple d'utilisation :
print(fibonacci(10)) # Sortie : 55
Important ! Note que nous utilisons memo=None comme valeur par défaut, puis créons un dictionnaire vide à l'intérieur de la fonction si memo n'est pas passé. Cela permet d'éviter le problème avec un objet modifiable comme valeur par défaut.
Exemple 2 : Somme de sous-ensembles
Il est nécessaire de déterminer s'il existe un sous-ensemble d'un ensemble donné, dont la somme des éléments est égale à une valeur donnée.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# Exemple d'utilisation :
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Sortie : True
La mémorisation est en fait la mise en cache des résultats des sous-tâches.
Par exemple, le nombre de Fibonacci F(10) == F(9) + F(8), mais pour calculer F(9), il faut calculer F(8) et F(7). C'est-à-dire que F(8) doit être calculé deux fois : comme premier terme pour F(9) et comme second terme pour F(10). Pour ne pas le calculer deux fois, il faut le mettre en cache après le premier calcul.
GO TO FULL VERSION