0Pricing
Coding Interview Prep · Leçon

Complexité spatiale et compromis

Mesurez l’espace auxiliaire utilisé par les piles d’appels et les structures de données auxiliaires, et reconnaissez les compromis temps-espace dans la mémoïsation et les algorithmes en place.

Complexité spatiale et compromis est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Que mesure la complexité spatiale ?

La complexité spatiale mesure la mémoire supplémentaire au-delà de l’entrée, appelée espace auxiliaire. Quelques variables donnent O(1) ; un tableau de résultats ou une table de hachage donne O(n). Consultez le code.

# O(1) auxiliary space
def sum_array(nums):
    total = 0       # one integer variable
    for n in nums:
        total += n  # constant extra space
    return total

# O(n) auxiliary space
def copy_array(nums):
    return list(nums)  # allocates n slots

print(sum_array([1, 2, 3, 4]))  # 10
print(copy_array([1, 2, 3, 4]))  # [1, 2, 3, 4]

Espace de la pile d’appels en récursivité

Chaque appel récursif ajoute une trame de pile, la profondeur détermine donc l’espace utilisé. Une récursivité linéaire est en O(n) ; un parcours en profondeur d’un arbre équilibré est en O(log n). Une version itérative permet de mieux le contrôler.

import sys

def recursive_sum(n):
    if n == 0: return 0
    return n + recursive_sum(n - 1)
# Space: O(n) stack frames

def iterative_sum(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
# Space: O(1)

print(recursive_sum(100))   # 5050
print(iterative_sum(100))   # 5050

Espace du tri fusion : O(n)

Le tri fusion nécessite un espace supplémentaire en O(n) pour ses tableaux temporaires. C’est le prix à payer pour un tri stable en O(n log n) — le tri par tas économise de l’espace, mais il n’est pas stable. Consultez le code.

import tracemalloc

tracemalloc.start()

def merge_sort(arr):
    if len(arr) <= 1: return arr
    m = len(arr) // 2
    l = merge_sort(arr[:m])    # new list
    r = merge_sort(arr[m:])    # new list
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]: out.append(l[i]); i+=1
        else:             out.append(r[j]); j+=1
    return out + l[i:] + r[j:]

data = list(range(1000, 0, -1))
merge_sort(data)
_, peak = tracemalloc.get_traced_memory()
print(f'Peak memory: {peak} bytes')  # proportional to n

Algorithmes en place : espace en O(1)

Un algorithme en place modifie directement l’entrée sans stockage supplémentaire proportionnel, par exemple en inversant un tableau avec deux pointeurs. L’espace reste ainsi en O(1). Consultez le code.

def reverse_inplace(arr):
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]  # swap
        l += 1
        r -= 1
    # Space: O(1) -- only two pointer variables

def rotate_right(arr, k):
    '''Rotate array right by k positions in-place.'''
    n = len(arr)
    k %= n
    arr.reverse()          # O(1) space
    arr[:k] = arr[:k][::-1]
    arr[k:]  = arr[k:][::-1]

a = [1, 2, 3, 4, 5]
rotate_right(a, 2)
print(a)  # [4, 5, 1, 2, 3]

Compromis temps-espace : two-sum

Le compromis temps-espace est omniprésent. Le problème de somme de deux nombres prend O(n^2) en temps et O(1) en espace, ou O(n) en temps et O(n) en espace grâce à une table de hachage. Mentionnez les deux options et demandez ce qui compte le plus.

# O(n^2) time, O(1) space
def two_sum_slow(nums, target):
    for i in range(len(nums)):          # O(n)
        for j in range(i+1, len(nums)): # O(n)
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# O(n) time, O(n) space
def two_sum_fast(nums, target):
    seen = {}                    # O(n) space
    for i, n in enumerate(nums):
        comp = target - n
        if comp in seen:         # O(1) lookup
            return [seen[comp], i]
        seen[n] = i
    return []

print(two_sum_fast([2, 7, 11, 15], 9))  # [0, 1]

Espace de la mémoïsation et de la tabulation

La mémoïsation descendante coûte O(n) pour la mémoïsation et O(n) pour la pile ; la tabulation ascendante évite la pile. Ne conserver que les dernières lignes réduit l’espace à O(1) : c’est une DP optimisée pour l’espace.

# Fibonacci: O(n) space with full table
def fib_table(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# O(1) space: keep only last two values
def fib_optimal(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_table(10))    # 55
print(fib_optimal(10))  # 55

Espace d’une table de hachage : O(n)

Une table de hachage est le coût spatial habituel en O(n) dans les solutions : un ensemble des éléments vus pour les éléments visités, une table de fréquences pour les compter. Indiquez-le toujours : « temps en O(n), espace en O(n) » est la réponse complète.

def contains_duplicate(nums):
    # O(n) time, O(n) space
    seen = set()
    for n in nums:
        if n in seen: return True
        seen.add(n)
    return False

def group_anagrams(words):
    # O(n*m) time, O(n) space  (m = avg word length)
    from collections import defaultdict
    groups = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)
    return list(groups.values())

print(contains_duplicate([1,2,3,1]))  # True
print(group_anagrams(['eat','tea','tan','ate','nat','bat']))

Analyse spatiale des algorithmes de graphes

Les graphes consomment un espace réel : une liste d’adjacence est en O(V + E), l’ensemble des éléments visités et la file d’un parcours BFS sont en O(V), et la récursivité d’un parcours DFS peut atteindre une profondeur O(V). Exprimez l’espace d’un graphe en fonction de V et de E.

from collections import deque

def bfs(graph, start):
    # Space: O(V) for visited set + O(V) for queue
    visited = set()      # O(V)
    queue = deque([start])  # O(V) max
    order = []
    while queue:
        node = queue.popleft()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        for nb in graph.get(node, []):
            queue.append(nb)
    return order

g = {0:[1,2], 1:[3], 2:[3], 3:[]}
print(bfs(g, 0))  # [0, 1, 2, 3]

Pièges liés à l’allocation de chaînes et de tableaux

Des allocations cachées peuvent consommer un espace en O(n) : le découpage en tranches crée une nouvelle liste, et + sur des chaînes dans une boucle donne O(n^2). Le tri par copie crée une copie, mais lst.sort() reste en place. Consultez le code.

# Hidden allocations:
nums = [1, 2, 3, 4, 5]

# Creates a NEW list -- O(n) space
slice_copy = nums[1:4]  # [2, 3, 4]

# Creates a NEW sorted list -- O(n) space
sorted_copy = sorted(nums)  # nums unchanged

# Sorts IN PLACE -- O(1) extra space
nums.sort()

print(slice_copy)   # [2, 3, 4]
print(sorted_copy)  # [1, 2, 3, 4, 5]
print(nums)         # [1, 2, 3, 4, 5]

Reconnaître les compromis spatiaux en entretien

Annoncez d’emblée votre complexité spatiale. Si le recruteur souhaite réduire l’espace, les solutions courantes consistent à utiliser une DP ascendante plutôt qu’une mémoïsation, ou un tri en place plutôt qu’une table de hachage. Consultez le code.

# Problem: find if array has duplicates
# Option 1: O(1) time-per-check, O(n) space
def has_dup_hash(nums):
    return len(nums) != len(set(nums))

# Option 2: O(n log n) time, O(1) extra space
def has_dup_sort(nums):
    nums_copy = sorted(nums)  # O(n) space -- still!
    for i in range(1, len(nums_copy)):
        if nums_copy[i] == nums_copy[i-1]:
            return True
    return False

# Option 3: truly O(1) extra -- sort in-place
def has_dup_inplace(nums):
    nums.sort()               # modifies original
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]: return True
    return False

Modèle d’énoncé de la complexité totale

Donnez toujours l’énoncé complet — temps et espace : « temps en O(n), espace supplémentaire en O(1) ». Mentionnez les compromis lorsqu’il y en a. C’est ce qui distingue les candidats expérimentés.

# Complete complexity example: Merge Intervals
def merge_intervals(intervals):
    # Time: O(n log n) for sort + O(n) for merge = O(n log n)
    # Space: O(n) for output (could be n/2 to n intervals)
    intervals.sort(key=lambda x: x[0])  # O(n log n)
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Vérification rapide

Vérification rapide — voyons si les notions de complexité spatiale sont bien acquises. Vous êtes prêt pour la suite. ✅

Récapitulatif de la leçon

Récapitulatif : l’espace auxiliaire se compte séparément de l’entrée, la récursivité utilise un espace de pile en O(profondeur), et le compromis temps-espace guide la plupart des choix de conception des algorithmes.

Questions Fréquemment Posées

La leçon « Complexité spatiale et compromis » est-elle gratuite ?

Oui — le texte complet de « Complexité spatiale et compromis » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Complexité spatiale et compromis » ?

Mesurez l’espace auxiliaire utilisé par les piles d’appels et les structures de données auxiliaires, et reconnaissez les compromis temps-espace dans la mémoïsation et les algorithmes en place. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Complexité spatiale et compromis » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. La notation grand O depuis le début
  2. Analyser les boucles et les boucles imbriquées
  3. Récursivité et méthode de l’arbre de récursion
  4. Complexité spatiale et compromis
← Retour à Coding Interview Prep