AnalyseNotion · Glossaire
complexité spatiale
La complexité spatiale d'un algorithme est la quantité de mémoire nécessaire à son exécution en fonction de la taille de l'entrée. Selon la convention annoncée, on compte soit l'espace total, entrée comprise, soit le seul espace auxiliaire : variables, structures temporaires et pile d'appels récursifs. Son ordre de croissance, exprimé en notation asymptotique grand O, aide à déterminer si l'algorithme reste utilisable quand les données grandissent ou lorsque la mémoire est limitée.
Sommaire
Ce que vous allez apprendre
- Distinguer espace total et espace auxiliaire.
- Reproduire le décompte de mémoire d'une copie de tableau.
- Lire O(1) et O(n) comme des ordres de croissance, non comme des nombres d'octets.
- Comparer complexité spatiale et complexité temporelle.
En clair
Imaginez un algorithme qui parcourt huit nombres. S'il crée une seconde rangée de huit cases pour les recopier, il lui faut huit cases supplémentaires. S'il modifie directement la rangée d'origine, quelques variables peuvent suffire, quel que soit le nombre de valeurs.
La complexité spatiale décrit la manière dont cette mémoire nécessaire évolue quand l'entrée grandit. Elle ne donne pas d'abord un nombre d'octets : elle classe une croissance, par exemple constante ou proportionnelle à la taille de l'entrée.
Définition
La complexité spatiale mesure la croissance de la mémoire mobilisée pendant l'exécution d'un algorithme en fonction de la taille de son entrée. La taille de l'entrée est notée n. Selon la convention annoncée, on compte soit l'espace total, entrée comprise, soit seulement l'espace auxiliaire créé par l'algorithme. Cette distinction doit toujours être précisée.
L'espace total inclut les données d'entrée, les variables intermédiaires, les structures auxiliaires et la pile des appels récursifs. Si un tableau de n cases est recopié dans un second tableau de même taille et si c désigne un nombre constant de cases de contrôle, le décompte abstrait est :
L'espace total et l'espace auxiliaire croissent alors tous deux en O(n), même si leurs coefficients diffèrent.
La notation grand O décrit un ordre de croissance lorsque n devient grand ; elle masque les constantes et les termes de plus faible ordre. Elle ne fournit donc ni la mémoire exacte en octets ni, à elle seule, la limite réelle d'une machine. Le type des données, leur représentation et l'environnement d'exécution restent nécessaires pour obtenir cette valeur.
Un exemple, pas à pas
Un programme reçoit un tableau de 8 nombres et en produit une copie. Les données sont : une entrée de 8 cases ; une sortie de 8 cases ; deux variables de contrôle, supposées occuper une case chacune.
1. Comptez l'entrée : 8 cases.
2. Comptez la copie auxiliaire : 8 cases.
3. Ajoutez les variables de contrôle : 2 cases.
4. L'espace total vaut donc 8 + 8 + 2 = 18 cases abstraites. L'espace auxiliaire vaut 8 + 2 = 10 cases.
2. Comptez la copie auxiliaire : 8 cases.
3. Ajoutez les variables de contrôle : 2 cases.
4. L'espace total vaut donc 8 + 8 + 2 = 18 cases abstraites. L'espace auxiliaire vaut 8 + 2 = 10 cases.
Pour une entrée de n nombres, les mêmes comptes donnent 2n + 2 cases au total et n + 2 cases auxiliaires. Les deux quantités sont en O(n), car doubler n double leur terme dominant.
Une version qui transforme le tableau sur place conserve 8 cases d'entrée et 2 cases de contrôle : son espace total reste linéaire, mais son espace auxiliaire devient constant, O(1). Le schéma compare ces trois décomptes sans les confondre.
Contrôle refaisable : remplacez 8 par 16. La copie utilise 34 cases au total et 18 cases auxiliaires, tandis que la version sur place utilise toujours 2 cases auxiliaires.
En pratique
Sur un appareil à mémoire limitée, on préfère une transformation sur place à une copie complète lorsque les données d'origine n'ont pas besoin d'être conservées. Le critère observable est le pic de mémoire auxiliaire pendant l'exécution.
Pour de très grands volumes de données, un traitement par flux peut remplacer le chargement intégral. Ce choix convient lorsque chaque élément peut être traité sans garder toute la collection en mémoire.
Face à une procédure récursive profonde, une version itérative peut éviter l'accumulation d'appels dans la pile. Il faut toutefois comparer les structures réellement conservées : une boucle accompagnée d'une grande pile explicite ne garantit pas un gain.
À ne pas confondre
Complexité temporelle. Elle classe la croissance du nombre d'opérations, tandis que la complexité spatiale classe celle de la mémoire mobilisée. Deux algorithmes qui terminent après un nombre comparable d'opérations peuvent conserver des quantités de données très différentes.
Mémoire exacte. Une borne en O(n) n'annonce pas un nombre précis d'octets. Deux programmes de même complexité spatiale peuvent avoir des coefficients, des représentations de données et des surcoûts d'exécution différents ; une mesure sur la machine les départage.
Limites et pièges
Convention non annoncée. Dire seulement « O(n) en espace » peut masquer le choix entre espace total et espace auxiliaire. Pour la version sur place de l'exemple, ils valent respectivement O(n) et O(1) : il faut nommer celui qui est évalué.
Pile récursive oubliée. Chaque appel encore actif peut conserver des paramètres, des variables et une adresse de retour. Lorsque la profondeur des appels augmente avec n, cette pile doit entrer dans le compte, même sans tableau auxiliaire visible.
Grand O pris pour une consommation réelle. O(1) signifie que l'espace ne croît pas avec n, pas qu'il occupe une seule case. Pour savoir si un programme tient en mémoire, il faut mesurer ou borner les octets avec la représentation et l'environnement retenus.
Pire cas implicite. La mémoire peut dépendre des données autant que de leur taille. Une analyse doit préciser si elle donne une borne de pire cas, de meilleur cas ou une valeur attendue ; sinon, deux exécutions de même taille peuvent sembler contredire l'estimation.
Pour aller plus loin
complexité temporelle — Mettre en regard mémoire et nombre d'opérations pour comparer les compromis entre deux algorithmes.
Grand O — Approfondir la notation asymptotique qui classe la croissance de l'espace quand la taille de l'entrée augmente.
algorithme — Revenir à la notion de procédure dont on analyse les ressources nécessaires à l'exécution.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres