Fiche de cours

Étudier la complexité mémorielle

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

Fiche de cours
Quiz et exercices
Vidéos et podcasts

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).

Évalue ce cours !

Note 4.8 / 5. Nombre de vote(s) : 4

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT