Complexité spatiale

La complexité spatiale mesure le pic de mémoire vivante en fonction de la taille de l'entrée. Précisez si une borne décrit la mémoire totale ou l'espace auxiliaire au-delà de l'entrée et de la sortie requise.

Catégories de mémoire

• Entrée : la représentation fournie à l'algorithme.
• Sortie : les résultats matérialisés, parfois inévitables et dominants.
• État auxiliaire : tables, files, ensembles de sommets visités, tampons et objets temporaires.
• Pile d'appels : une trame active pour chaque appel récursif en cours.

Le pic d'espace n'est pas la somme de toutes les allocations effectuées au fil du temps. Une mémoire libérée avant le début d'une autre phase ne coexiste pas avec celle de cette phase.

Règles d'analyse

• Comptez les objets simultanément vivants, y compris les copies cachées créées par les tranches ou les concaténations immuables.
• Pour la récursion, additionnez la mémoire conservée par tous les appels actifs au même instant. Si chaque trame possède la même borne de taille, ce calcul se ramène à la taille d’une trame multipliée par la profondeur active maximale. Le nombre total d’appels pendant l’exécution ne détermine pas le pic d’espace de pile.
• Distinguez une sortie diffusée progressivement d'un résultat entièrement matérialisé.
• Incluez la représentation : une matrice d'adjacence utilise $\Theta(V^2)$, contre $\Theta(V+E)$ pour des listes d'adjacence.

Un temps exponentiel n'implique pas un espace de pile exponentiel. Une recherche en profondeur peut explorer un nombre exponentiel d'états tout en ne conservant qu'un chemin linéaire, plus les états visités ou mémoïsés.

Calcul en place et compression

« En place » signifie généralement un espace auxiliaire en $O(1)$ pour le réarrangement d'un tableau, mais les piles récursives et les allocations d'objets peuvent contredire une affirmation trop rapide. Précisez la convention.

L'espace d'une programmation dynamique peut être compressé lorsque les transitions futures n'exigent qu'une frontière bornée. Ne supprimez pas les lignes ou les prédécesseurs nécessaires à la reconstruction de la solution demandée.

Compromis temps–espace

La mémoïsation, les index, le hachage et les tables précalculées consomment de la mémoire pour éviter de répéter le travail. Le recalcul, le traitement en flux et les représentations succinctes économisent de la mémoire au prix éventuel de temps ou de complexité d'implémentation. Optimisez selon une contrainte réelle, et non une dimension asymptotique isolée.

Comptes mémoire détaillés

Un tri par insertion en place de $n$ enregistrements garde le tableau d’entrée comme sortie. Ses indices et sa clé sauvegardée prennent $O(1)$ mots auxiliaires, mais le stockage total reste $\Theta(n)$. Renvoyer une liste triée distincte exige $\Theta(n)$ emplacements de sortie avant même l’espace de travail. Comptez une seule fois les objets partagés : copier une liste Python copie des références, pas nécessairement les enregistrements pointés.

Une recherche binaire récursive par indices conserve $O(\log n)$ trames de taille constante. Une version qui copie une demi-liste à chaque appel garde aussi des copies de tailles $n/2+n/4+\cdots<n$, portant l’espace auxiliaire à $O(n)$. Même profondeur ne signifie pas même mémoire. En général, additionnez les tailles des trames vivantes ; « taille de trame fois profondeur » ne s’applique directement qu’avec une borne uniforme sur les trames.

Pour DFS sur un graphe explicite, l’ensemble visité peut contenir tous les sommets accessibles. Sur un arbre implicite de profondeur $d$ et de branchement $b$, sans ensemble visité global, l’exploration peut prendre un temps exponentiel avec $O(d)$ trames si chacune ne garde qu’un itérateur de successeurs de taille constante. Conserver les $b$ successeurs par niveau demande plutôt $O(bd)$ ; mémoïser chaque état exploré peut aussi demander une mémoire exponentielle.

Ces comptes portent sur des mots ou références avec des enregistrements de taille bornée, pas sur des octets exacts. Taille binaire des entiers, en-têtes d’objets, allocations et récupération différée modifient la mémoire réelle. Le pic d’objets vivants ne garantit pas que le runtime rende immédiatement la mémoire libérée au système d’exploitation.

Source

• Open Data Structures

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.