Lycée > Terminale > NSI > Étudier la complexité mémorielle

Étudier la complexité mémorielle

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Connaitre la différence entre la complexité temporelle et la complexité spatiale.
Savoir estimer la complexité spatiale d’un algorithme.

Points clés

La complexité temporelle d’un algorithme est une estimation du temps d’exécution de cet algorithme, qui dépend de la taille de la donnée traitée.
La complexité spatiale d’un algorithme, ou complexité en mémoire, est une estimation de la mémoire utilisée pour exécuter cet algorithme, qui dépend de la taille de la donnée traitée.
La récursivité augmente considérablement la complexité spatiale.

Pour bien comprendre

Programmer de manière dynamique.

1. La différence entre la complexité temporelle et la complexité spatiale

a. Complexité temporelle

Étudier la complexité temporelle d’un algorithme consiste à estimer le temps d’exécution de cet algorithme.

La complexité temporelle d’un algorithme dépend directement de la taille de la ou des données traitées.

Étudier ce cout en temps revient à estimer le nombre d’affectations, le nombre de comparaisons et d’opérations nécessaires à l’exécution de l’algorithme.

Une affectation est une procédure qui permet d’attribuer une valeur à une variable.
Une comparaison est une instruction qui met en jeu deux variables et qui renvoie True ou False (vrai ou faux).
Une opération est une instruction utilisant +, -, *, /, //, % ou **.

Exemple
La complexité temporelle du tri par sélection est quadratique. C’est-à-dire que, pour un tableau de taille n, l’ordre de grandeur du temps du tri est n². On dit que le tri par insertion est en O(n²).

b. Complexité spatiale

Étudier la complexité spatiale d’un algorithme, ou complexité en mémoire, consiste à estimer la quantité de mémoire dont va avoir besoin l'algorithme pour s'exécuter.

Comme pour la complexité temporelle, la complexité spatiale d’un algorithme dépend directement de la taille de la ou des données traitées.

Étudier ce cout en espace revient à estimer le nombre de cases mémoires utilisées pendant l’exécution de l’algorithme.

On conviendra que :

on utilise une case mémoire lorsqu’une variable est créée ;
on utilise n cases mémoires lorsqu’un tableau de taille n est créé ;
on utilise une case mémoire lorsque, en récursivité, on ajoute un appel récursif à la pile d’exécution.

Exemple
La complexité spatiale du tri par sélection est linéaire, en O(1). On considère en effet la fonction de tri par sélection suivante.

Python	Explication
def tri_selection(Tab):	1 case mémoire est créée pour la fonction tri_selection.
n = len(Tab)	1 case mémoire est créée pour la variable n.
for i in range(0, n–1):	1 case mémoire est créée pour la variable i.
i_mini = i	1 case mémoire est créée pour la variable i_mini.
for j in range(i+1, n):	1 case mémoire est créée pour la variable j.
if Tab[j] < Tab[i_mini]:	Les cases mémoires de Tab[j] et Tab[i_mini] existent déjà dans le tableau Tab.
i_mini = j	La case mémoire de i_mini existe déjà.
temp = Tab[i]	1 case mémoire est créée pour la variable temp.
Tab[i] = Tab[i_mini]	La case mémoire de Tab[i] existe déjà.
Tab[i_mini] = temp	La case mémoire de Tab[i_mini] existe déjà.

Ainsi le tri par sélection utilise 6 cases mémoires. Sa complexité spatiale est constante, en O(1).

2. L'étude de la complexité spatiale du rendu de monnaie dynamique

a. Rendu de monnaie récursif

En Python, la fonction nb_rendu(pieces, somme) prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.

Cette fonction renvoie le nombre minimum de pièces/billets nécessaires pour rendre la monnaie sur somme.

Python	Explication
def nb_rendu(pieces, somme):	On définit la fonction nb_rendu.
if somme == 0: return 0	Si la somme est nulle, il faut 0 pièce/billet pour le rendu.
else:	Sinon,
nb_pieces = somme	on affecte somme à la variable nb_pieces (pire cas où le rendu ne fait qu’avec des pièces de 1)
for p in pieces:	Pour chaque pièce p de pieces,
if p <= somme:	si p est inférieur à la somme,
n = 1 + nb_rendu(pieces, somme – p)	on affecte à n la somme de 1 et du rendu pour une somme de somme–p,
nb_pieces = min(nb_pieces, n)	on affecte à la variable nb_pieces le minimum de n et de nb_pieces.
return nb_pieces	Enfin, on retourne nb_pieces

Si on étudie le rendu de monnaie avec pieces = [1, 2, 5] et somme = 25, il est facile de voir que le rendu optimal est 25 = 5 + 5 + 5 + 5 + 5.

Voici l’appel de cette fonction sur Python Tutor pour pieces = [1, 2, 5] et pour somme = 25.

L’exécution s’interrompt avec le message suivant :

Stopped since this run produced more than 2MB of data.

Il semble que l'exécution de nb_rendu(pieces, somme) demande trop de mémoire. Cela peut être le cas lorsqu’une fonction est récursive et que le même appel est fait plusieurs fois.

Par exemple :

nb_rendu(pieces, 0) renvoie 0 ;
nb_rendu(pieces, 1) renvoie 1, car une seule pièce est utilisée ;
nb_rendu(pieces, 2) se fait directement ou en appelant deux fois nb_rendu(pieces, 1) qui sera exécuté deux fois ;
nb_rendu(pieces, 3) se fait de différentes manières : en appelant trois fois nb_rendu(pieces, 1) ou en appelant nb_rendu(pieces, 1) et nb_rendu(pieces, 2).

Ainsi, on observe que le rendu de la même somme est calculé plusieurs fois, ce qui augmente considérablement la mémoire utilisée.

Le calcul de la complexité spatiale d’une fonction récursive est très complexe et demande une expertise en mathématiques qui ne relève pas du lycée.

b. Rendu de monnaie dynamique

En Python, la fonction nb_rendu_dyn(pieces, somme) prend en paramètres le système monétaire utilisé pieces et la somme à rendre somme.

Cette fonction renvoie le nombre minimum de pièces/billets nécessaire pour rendre la monnaie sur somme.

Python	Explication
def nb_rendu_dyn(pieces, somme):	1 case mémoire est créée pour la fonction nb_rendu_dyn.
rendu = [0]*(somme + 1)	somme+1 cases mémoires sont créées pour le tableau rendu.
for s in range(1, somme + 1):	1 case mémoire est créée pour la variable s.
rendu[s] = s	La case mémoire de rendu[s] existe déjà.
for p in pieces:	1 case mémoire est créée pour la variable p.
if p <= s:
rendu[s] = min(rendu[s], 1 + rendu[s – p])	La case mémoire de rendu[s] existe déjà.
return rendu[somme]

La fonction nb_rendu_dyn(pieces, somme) utilise donc somme + 4 cases mémoires. Ainsi la complexité spatiale du rendu de monnaie dynamique est de l’ordre de la somme à rendre, en O(somme).