Complexité spatiale : Comment les algorithmes utilisent la mémoire

La complexité spatiale évalue l'utilisation de la mémoire par les algorithmes à mesure que la taille des données d'entrée augmente. Il est donc essentiel de bien comprendre la complexité spatiale pour gérer efficacement les ressources dans des environnements soumis à des contraintes.

Dans cet article, je vais expliquer en détail ce qu'est la complexité spatiale, comment la calculer et comment la minimiser. De plus, j'aborderai les applications concrètes et présenterai les fondements théoriques.

Comprendre la complexité spatiale

Avant de nous plonger dans les calculs et les optimisations, clarifions ce que signifie réellement la complexité spatiale et pourquoi vous devriez vous y intéresser.

Qu'est-ce que la complexité spatiale ?

La complexité spatiale correspond à la mémoire totale requise par l'algorithme par rapport à la taille de l'entrée. Il est pertinent pour analyser l'empreinte mémoire dans le pire des cas pour l'évolutivité du système, et l'espace total comprend l'entrée, l'espace auxiliaire et la surcharge, tandis que l'espace auxiliaire est la mémoire supplémentaire excluant l'entrée et la sortie. Prenons l'exemple du tri d'un tableau : L'espace total comprend le tableau lui-même, tandis que l'espace auxiliaire peut être l'espace temporaire dans le tri par fusion.

Pourquoi la complexité spatiale est-elle importante ?

Dans l'informatique moderne, l'efficacité de l'espace est souvent essentielle. En optimisant la complexité spatiale, vous garantissez que vos algorithmes fonctionnent sur des appareils dotés d'une mémoire RAM limitée, tels que les systèmes embarqués dans l'IoT ou les smartphones, ou même les grands systèmes avec des procédures gourmandes en ressources où chaque bit de RAM compte.

Prenons l'exemple des applications mobiles : l'optimisation de la complexité spatiale contribue à éviter les plantages lors du traitement des images. Ou considérez les économies réalisées grâce au cloud computing en matière de stockage ou de streaming de données, et l'obtention d'analyses en temps réel sans chargement complet des données.

Analyse asymptotique et notation O grand pour l'espace

Dans cette section, je vais expliquer comment les notations asymptotiques telles que Big O décrivent la croissance de l'espace, et vous fournir des outils pour limiter et comparer l'utilisation de la mémoire.

Introduction à la notation Big O

Mathématiquement, une fonction f(n) est dominée par une fonction g(n) s'il existe une constante c et k, telles que pour tout k>n, 0 ≤ |f(n)| ≤ |g(n)|.

Dans ce cas, nous écrivons f(n)=O(g(n)), et nous affirmons que f(n) est un grand O de g(n).

En termes plus simples, cela signifie que f(n) ne croît pas plus rapidement que g(n) à partir d'un certain indice.

La notation Big O représente la limite supérieure de l'espace en fonction de la taille d'entrée n, ce qui nous permet de nous concentrer sur les termes dominants pour les grandes valeurs de n.  Cette notation permet de classer les algorithmes. Par exemple, O(n) signifie que l'espace double lorsque l'entrée double.

Il existe une idée fausse courante chez les débutants selon laquelle le Big O pour l'espace ignore les constantes telles que 2n est O(n), mais en pratique, les constantes sont importantes pour les petits n.

Notations asymptotiques associées

Il existe différentes méthodes pour modéliser la complexité et différentes notations. Par exemple, Big Omega fournit une borne inférieure qui est utile pour démontrer des besoins minimaux en espace, comme par exemple le tri qui nécessite au moins Ω(n). Une autre notation est le Big Theta, qui fournit une limite stricte lorsque les valeurs supérieure et inférieure correspondent, ce qui le rend idéal pour une analyse précise, comme O(n) = Θ(n) pour l'espace linéaire.

Autres conventions de notation

Il existe quelques autres conventions de notation pertinentes pour la littérature sur la complexité spatiale, telles que la notation Soft-O Õ, qui ignore les facteurs polylog. Il est courant dans les algorithmes avancés tels que le traitement de graphes, où les journaux sont négligeables. Il apparaît dans des articles théoriques traitant de complexités approximatives telles que Õ pour l'espace sous-linéaire dans les algorithmes de streaming.

Composantes de la complexité spatiale

La complexité spatiale comporte de nombreux facteurs et points d'optimisation dans la conception d'algorithmes. Examinons cela :

Exigences en matière d'espace de saisie

Les données d'entrée occupent un espace proportionnel à leur taille, par exemple O(n) pour un tableau ou pour l'analyse d'un ensemble de données volumineux tel que des séquences génomiques.

Dans les entretiens de codage réels, il est courant d'exclure l'espace d'entrée lors du calcul de l'espace auxiliaire et de se concentrer uniquement sur la mémoire supplémentaire utilisée par l'algorithme. Dans la programmation compétitive, cependant, l'espace total inclut généralement l'entrée.

Espace auxiliaire et mémoire temporaire

L'espace auxiliaire est la mémoire supplémentaire dont un algorithme a besoin pour effectuer ses opérations. Cela influe directement sur la conception de l'algorithme.

Par conséquent, vous pouvez, par exemple, utiliser O(n) pour le tableau temporaire dans un algorithme de tri par fusion. Un autre exemple serait les tableaux de hachage pour les doublons (O(n)), les piles de récursivité pour la correspondance des parenthèses (O(n)), et bien d'autres encore.

Parmi les exemples classiques d'espace auxiliaire, on peut citer les méthodes à deux pointeurs (O(1)), les algorithmes à fenêtre glissante utilisant une file double (O(k)) et le BFS, qui nécessite un espace O(V) pour son ensemble visité et sa file d'attente.

Le code suivant présente un exemple d'opération de tri par fusion sur le tableau temporaire pendant l'étape de fusion :

def merge(left_half, right_half):
    merged = [0] * (len(left_half) + len(right_half))  # O(n) auxiliary space
    left_idx = right_idx = merged_idx = 0
    # merging logic...

La pile d'appels et l'espace de récursivité

Chaque appel récursif ajoute un cadre de pile (adresse de retour + paramètres + variables locales).

D'autre part, la récursivité linéaire, comme la factorielle ou le DFS sur une liste chaînée, a une pile O(n).

La récursivité binaire, comme la récursivité naïve de Fibonacci ou la récursivité arborescente, présente un O(n) dans le pire des cas.

L'optimisation des appels en queue, prise en charge dans Scheme, Rust et parfois Python avec des décorateurs, se réduit à O(1). Cependant, le véritable risque réside dans la limite de récursivité par défaut de Python, qui est d'environ 1 000, ce qui pourrait entraîner un débordement de la pile dans les arborescences profondes.

Voici un exemple de Fibonacci récursif naïf qui illustre la croissance de la pile :

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # O(n) stack depth

Nous vous invitons à consulter notre blog sur l'analyse de la complexité du code à l'aide de Python pour en savoir plus sur l'analyse de complexité de Python.

Surcoût lié à la structure des données

L'avantage de la surcharge liée à la structure des données réside dans sa simplicité, car toutes les structures ajoutent des coûts fixes/par élément, comme la surcharge minimale d'un tableau, le double espace des pointeurs des listes liées, et bien d'autres exemples. 

Quoi qu'il en soit, le langage de programmation exerce une influence considérable. Les listes Python ont une surcharge dynamique, contrairement aux tableaux C. Par exemple, les tables de hachage avec un facteur de charge de 75 % gaspillent de l'espace sur les crochets vides.

Types de complexité spatiale

Complexité spatiale constante : O(1)

La complexité spatiale constante constitue la solution fondamentale et optimale lorsqu'elle est identifiée. De nombreux algorithmes connus ont une complexité véritablement constante, comme les simples permutations de variables illustrées dans l'exemple ci-dessous, qui est une simple permutation sur place utilisant le déballage de tuples Python :

def swap_numbers(first, second):
    first, second = second, first  # O(1) — only two variables
    return first, second

D'autres algorithmes à complexité constante connus sont la partition du drapeau néerlandais dans le tri rapide et le parcours de Morris pour les arbres. Cependant, il existe une limite pratique où vous pouvez avoir quelques dizaines de variables avant que cela ne soit efficace, car selon le matériel du système, dans le pire des cas, O(1) peut parfois ne pas suffire si la mémoire requise dépasse les ressources du système.

Complexité de l'espace linéaire : O(n)

Une complexité spatiale linéaire est simplement définie comme étant proportionnelle à l'entrée. Quelques exemples pourraient être un tableau supplémentaire pour la copie ou un ensemble de hachage pour les éléments uniques. Le cas d'utilisation le plus courant relève des modèles de traitement des données, comme le filtrage de listes.

Complexité logarithmique et sublinéaire de l'espace

Une complexité spatiale logarithmique signifie que la quantité de mémoire utilisée par un algorithme augmente très lentement à mesure que la taille de l'entrée augmente. Plus précisément, elle est proportionnelle au logarithme de la taille de l'entrée.

Par exemple, une récursivité de recherche binaire a une profondeur de pile O(log(n)), tout comme la méthode « diviser pour régner » avec récursivité de queue ou les algorithmes de streaming, qui donnent des résultats approximatifs dans un espace O(log(n)) ou O(sqrt(n)).

Les complexités logarithmiques et sous-linéaires sont peu fréquentes, mais elles sont très efficaces pour les ensembles de données volumineux. Vous pouvez observer un exemple de complexité logarithmique avec la recherche binaire itérative (espace constant) comme le montre le code ci-dessous :

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left <= right:                 # O(1) space total
        mid = (left + right) // 2
        # comparison logic...

Complexité spatiale quadratique : O(n²)

Une complexité spatiale quadratique se produit lorsque les besoins en mémoire évoluent proportionnellement au carré de l'entrée. Un exemple courant serait le tableau de programmation dynamique 2D, qui présente une complexité de O(n²), ou une matrice d'adjacence pour les graphes avec une complexité de O(V²). Il est toutefois important de noter que cette complexité devient impraticable au-delà de plusieurs milliers d'éléments d'entrée.

Complexité exponentielle et factorielle de l'espace

La complexité exponentielle, comme son nom l'indique, rend la croissance de la mémoire requise proportionnelle à la taille de l'entrée exponentiée O(2^n), et cela se produit lorsque, par exemple, vous stockez tous les sous-ensembles ou tous les chemins de l'arbre de décision.

De même, dans la complexité factorielle, la mémoire requise est proportionnelle au factoriel de la taille d'entrée O(n!), et cela se produit lorsque vous énumérez toutes les permutations de l'entrée. Cependant, ces complexités sont généralement très coûteuses et sont presque certainement irréalisables pour n>20-30 dans la plupart des systèmes. Si vous travaillez sur ce sujet, il se peut que vous ayez besoin d'une révision, d'une approximation ou d'une approche différente.

Comment calculer la complexité spatiale

Une analyse systématique identifie toutes les allocations de mémoire et leurs modèles de croissance :

Approche d'analyse ligne par ligne

La première étape consiste à examiner votre code ligne par ligne et à identifier chaque variable, tableau et allocation d'objet. L'étape suivante consiste à déterminer si la taille de chaque allocation dépend des paramètres d'entrée. Ensuite, additionnez la mémoire pour les allocations indépendantes et prenez la valeur maximale pour les branches mutuellement exclusives. Enfin, vous suivez à la fois les allocations de pile pour les variables locales et les allocations de tas pour la mémoire dynamique. Voici un exemple :

def linear_search(arr, target):
    n = len(arr)           # O(1) - single integer
    for i in range(n):     # O(1) - loop variable
        if arr[i] == target:
            return i
    return -1
# Total: O(1) auxiliary space

Analyse de la complexité récursive

La complexité spatiale pour la récursivité est égale à la profondeur maximale de récursivité multipliée par l'espace par cadre d'appel, puis ajoutez toutes les structures de données auxiliaires allouées pendant la récursivité, identifiez le cas de base et analysez comment la profondeur de récursivité est liée à la taille de l'entrée. Par exemple, la méthode naïve de Fibonacci crée une profondeur O(n) avec O(1) par cadre, ce qui totalise un espace de pile O(n). Voici un exemple de calcul d'espace factoriel :

def factorial(n):
    if n <= 1:             # Base case
        return 1
    return n * factorial(n - 1)
# Space: O(n)

Analyse de la complexité de la programmation dynamique

Les tableaux DP standard ont des dimensions correspondant aux paramètres du sous-problème ; par conséquent, un problème unidimensionnel nécessite un espace O(n), et les problèmes bidimensionnels nécessitent un espace O(nxm). Les techniques d'optimisation telles que les tableaux glissants réduisent une dimension à transformer, par exemple, de O(n²) à O(n). La compression d'état exploite les dépendances, donc si la ligne i ne nécessite que i-1, il suffit de stocker deux lignes. Voici un exemple de Fibonacci optimisé en termes d'espace utilisant seulement deux variables :

def fibonacci_optimized(n):
    previous = 0
    current = 1
    for _ in range(2, n + 1):            # O(1) space
        previous, current = current, previous + current
    return current

Si vous êtes intéressé par la dimensionnalité et sa réduction, je vous invite à consulter nos tutoriels sur Maîtriser les dimensions à évolution lente (SCD) et Comprendre la cardinalité : Défis et solutions pour les flux de travail à forte intensité de données.

Étapes pour calculer la complexité spatiale dans la pratique

Pour calculer la complexité spatiale dans la pratique, veuillez suivre les étapes suivantes :

1. Veuillez préciser si l'espace de saisie est inclus en fonction du contexte.
2. Comptez les variables et les constantes de taille fixe. Ils contribuent à O(1)
3. Mesurer les structures auxiliaires telles que les tableaux et les tables de hachage par rapport à la taille des données d'entrée.
4. Calculer la profondeur de récursivité maximale pour la contribution à l'espace de la pile
5. Veuillez combiner tous les composants et exprimer le résultat en utilisant la borne asymptotique la plus stricte.

La complexité spatiale des algorithmes courants

Exigences en matière d'espace pour les algorithmes de tri

L'algorithme de tri par fusion nécessite un espace auxiliaire O(n) pour les tableaux temporaires pendant la fusion. D'autre part, Quicksort n'utilise en moyenne qu'un espace de pile O(log n), mais O(n) dans le pire des cas sans optimisation. Alors que le tri par tas n'utilise qu'un espace auxiliaire O(1) en effectuant le tri sur place, comme le montre le code suivant :

def heapify(array, heap_size, root_index):
    largest = root_index
    left_child = 2 * root_index + 1
    right_child = 2 * root_index + 2
    # comparison & swap logic...       # O(1) auxiliary space

Enfin, le tri par comptage nécessite un espace O(k), où k est la plage de valeurs, mais il n'est pas pratique lorsque k >> n.

Complexité spatiale des algorithmes graphiques

Le parcours de graphes implique divers algorithmes. Par exemple, la recherche en largeur (BFS) maintient une file d'attente nécessitant un espace O(V) pour les sommets, tandis que la recherche en profondeur (DFS) utilise un espace de pile O(V) dans le pire des cas pour une profondeur maximale.  L'algorithme de Dijkstra, quant à lui, nécessite O(V) pour la file d'attente prioritaire et le suivi de la distance pour chacun. La représentation graphique est importante car la matrice d'adjacence utilise O(V²) tandis que la liste d'adjacence utilise O(V+E). 

Caractéristiques de l'espace de structure des données

Il existe différentes structures de données et chacune nécessite des allocations de mémoire différentes. Par exemple, les tableaux et les listes de tableaux stockent n éléments dans une mémoire contiguë O(n), les listes liées nécessitent un espace O(n) plus une surcharge de pointeurs pour chaque nœud, les arbres binaires utilisent un espace O(n) avec 2 à 3 pointeurs par nœud, ce qui ajoute une surcharge importante, les tables de hachage consomment un espace O(n) multiplié par un facteur de charge qui varie généralement entre 1,5 et 3 fois, et les listes d'adjacence offrent une efficacité d'espace O(V+E) pour les graphes clairsemés.

Exemple de calculs de complexité spatiale

Voici des exemples de calcul de la complexité spatiale.

# O(1): In-place string reversal
left = 0
right = len(text) - 1
while left < right:
    text[left], text[right] = text[right], text[left]  # O(1)
    left += 1
    right -= 1

# O(n): Detect duplicate using hash set
seen_numbers = set()                                      # O(n)
for num in array:
    if num in seen_numbers:
        return True
    seen_numbers.add(num)

# O(log n): Recursive binary tree height
def tree_height(root):
    if not root:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))  # O(log n) stack

# O(n²): Floyd-Warshall distance matrix
distance = [[float('inf')] * vertices for _ in range(vertices)]  # O(n²)
for i in range(vertices):
    distance[i][i] = 0

Complexité spatiale par rapport à Complexité temporelle

Le temps et l'espace représentent des dimensions distinctes des ressources qui doivent être équilibrées en fonction des contraintes du système :

Principales différences et similitudes

À première vue, la complexité spatiale et temporelle peuvent sembler similaires, mais elles sont également différentes, car la complexité temporelle mesure les opérations de calcul, tandis que la complexité spatiale mesure la consommation de mémoire. Bien qu'ils utilisent tous deux une notation asymptotique et des cadres d'analyse mathématique identiques, il est important de noter que les algorithmes peuvent être optimaux dans une dimension tout en étant inefficaces dans une autre. L'optimisation implique souvent de privilégier un gain d'espace au détriment d'un gain de temps, ou inversement.

Comprendre le compromis fondamental

Lorsque vous échangez de l'espace contre du temps, vous stockez des résultats précalculés qui éliminent les calculs redondants. D'un autre côté, échanger du temps contre de l'espace implique de recalculer les valeurs à la demande au lieu de les stocker. Les tableaux de consultation échangent un investissement ponctuel en espace contre un accès répété O(1). Il peut exister des contraintes spécifiques, telles que des limites de mémoire et des exigences de performance, qui déterminent quelle ressource doit être prioritaire par rapport à une autre.

Mémorisation et optimisation de la programmation dynamique

La mémorisation fonctionne en enregistrant les valeurs plutôt qu'en les recalculant ; elle est efficace en termes de temps, mais peu avantageuse en termes d'espace. Il ajoute, par exemple, un cache O(n) à la fonction récursive de Fibonacci, mais réduit le temps de calcul de O(2^n) à O(n), comme dans l'exemple ci-dessous sur la fonction mémorisée de Fibonacci, évitant ainsi de devoir recalculer :

memory = {}
def fibonacci_memory(n):
    if n in memo:
        return memory[n] # O(n) space, O(n) time
    if n <= 1:
        return n
    memory[n] = fibonacci_memory(n-1) + fibonacci_memory(n-2)
    return memory[n]

La programmation dynamique ascendante, quant à elle, effectue des calculs itératifs afin d'éliminer la surcharge liée à la pile de récursivité. Afin d'optimiser l'espace, il est recommandé de ne conserver que les états précédents nécessaires au calcul actuel. Par exemple, la distance d'édition peut être réduite de O(nxm) tableaux à O(min(n,m)) en conservant une seule ligne.

Techniques d'algorithmes sur place

Les algorithmes sur place modifient directement les données d'entrée plutôt que d'allouer de nouvelles structures mémoire, ce qui, en cas d'itération, contribue considérablement à l'allocation de mémoire et réduit ainsi la complexité spatiale, comme le montre l'exemple ci-dessous sur la rotation de tableau sur place (algorithme d'inversion) :

def rotate_array(nums, k):
    n = len(nums)
    k = k % n
    reverse(nums, 0, k - 1)  # all operations O(1) auxiliary
    reverse(nums, k, n - 1)
    reverse(nums, 0, n - 1)

D'autres techniques en place réduisent considérablement l'utilisation de la mémoire. Par exemple, la technique des deux pointeurs manipule les tableaux avec un espace auxiliaire O(1), et le tri cyclique traite les problèmes de permutation dans un espace O(1) en échangeant les éléments pour les placer aux positions correctes. Il convient toutefois de noter que la modification sur place peut détruire les données d'entrée, ce qui affecte la réutilisabilité et la clarté du code.

Sélection de la structure de données pour une utilisation optimale de l'espace

Il existe de nombreuses structures de données différentes, chacune offrant un compromis différent. Par conséquent, par exemple, il est préférable d'utiliser des tableaux plutôt que des listes chaînées lorsque la taille est connue, d'éliminer la surcharge des pointeurs par élément et de manipuler des bits pour stocker des indicateurs booléens avec une compression 8 fois supérieure à celle des tableaux d'octets. Les essais partagent des préfixes communs afin d'optimiser l'espace pour les grandes collections de chaînes. Pour les graphes clairsemés, il est préférable d'utiliser des listes d'adjacence plutôt que des matrices afin d'obtenir un espace O(V+E) au lieu de O(V²).

Considérations pratiques et réalités de mise en œuvre

La complexité spatiale réelle dépend des langages de programmation, de l'architecture matérielle et des environnements d'exécution.

Facteurs liés à la langue et à l'environnement d'exécution

Les langages de haut niveau tels que Python et Java ajoutent des métadonnées et une surcharge par objet, contrairement au C et au C++, qui offrent une gestion manuelle de la mémoire pour un contrôle précis, mais au prix d'une certaine complexité. C'est probablement pour cette raison que les frameworks d'optimisation du machine learning tels que PyTorch utilisent le langage C++ pour les calculs.

La taille maximale de la pile varie généralement entre 1 et 8 Mo, ce qui limite la profondeur maximale de récursivité. Veuillez noter que les systèmes 64 bits utilisent des pointeurs de 8 octets, tandis que les systèmes 32 bits utilisent des pointeurs de 4 octets, ce qui double la taille de la structure des pointeurs. Pour en savoir plus sur l'impact des données à haute dimension sur les performances des algorithmes, veuillez consulter notre tutoriel «orial » : Le défi de la dimensionnalité dans l'apprentissage automatique.

Hiérarchie de la mémoire et effets de cache

L'utilisation de l'espace algorithmique et les performances dépendent fortement de la hiérarchie de la mémoire. L'accès à la mémoire vive (RAM) prend environ 100 nanosecondes, tandis que l'accès au cache du processeur (CPU) prend entre 1 et 10 nanosecondes, ce qui est 100 fois plus rapide. De plus, l'accès séquentiel à la mémoire exploite les lignes de cache où 64 octets sont généralement chargés ensemble.

Les algorithmes présentant une bonne localité spatiale offrent de meilleures performances grâce à l'efficacité du cache. Ainsi, lorsque l'on travaille sur des ensembles volumineux qui dépassent la capacité, cela entraîne un thrashing, ce qui dégrade considérablement les performances.

Collecte des déchets et gestion de la mémoire

Un outil utile pour la gestion de la mémoire est le ramasse-miettes, qui permet de nettoyer les données qui ne sont plus utiles. En d'autres termes, les ramasse-miettes ajoutent une surcharge mémoire pour le suivi des objets et la gestion de la génération.

L'utilisation maximale de la mémoire dépasse la taille des données actives en raison des allocations effectuées avant les cycles de collecte. De plus, le GC générationnel optimise les objets à courte durée de vie en conservant les jeunes générations dans des espaces plus restreints. Toutefois, si vous souhaitez un contrôle plus déterministe de l'espace, vous pouvez recourir à la gestion manuelle de la mémoire, mais vous devez être conscient des risques que cela comporte, tels que les fuites de mémoire et la fragmentation.

Conclusion et recommandations

Je vous remercie d'avoir lu mon article sur la complexité spatiale. Je vous laisse avec quelques conseils supplémentaires :

• Il est important de toujours préciser si l'analyse de l'espace inclut la taille des entrées afin d'éviter tout malentendu lors des entretiens et des revues de code.
• Veuillez privilégier la précision en premier lieu, puis optimiser l'espace uniquement lorsque le profilage révèle des goulots d'étranglement réels.
• Veuillez prendre en compte les contraintes matérielles et de mémoire dès le début de la conception du système afin d'éviter une refonte coûteuse.
• Veuillez toujours sélectionner les outils de profilage adaptés au langage afin de valider l'analyse théorique par rapport au comportement réel et d'équilibrer l'optimisation de l'espace et la lisibilité du code. Des optimisations trop sophistiquées peuvent également nuire à la maintenabilité.