Complessità spaziale e compromessi
Misuri lo spazio ausiliario per gli stack delle chiamate e le strutture dati ausiliarie e riconosca i compromessi tra tempo e spazio nella memoisation e negli algoritmi in-place
Complessità spaziale e compromessi è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Che cosa misura la complessità spaziale?
La complessità spaziale misura la memoria aggiuntiva oltre all'input, chiamata spazio ausiliario. Alcune variabili richiedono O(1); un array risultato o una mappa hash richiedono O(n). Veda il codice.
# 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]Spazio dello stack delle chiamate nella ricorsione
Ogni chiamata ricorsiva aggiunge un frame allo stack, quindi è la profondità a determinare lo spazio. La ricorsione lineare è O(n); la DFS su un albero bilanciato è O(log n). Una versione iterativa può gestire meglio questo aspetto.
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)) # 5050Spazio del merge sort: O(n)
Il merge sort richiede spazio aggiuntivo O(n) per i suoi array temporanei. È il prezzo da pagare per un ordinamento stabile O(n log n): l'heap sort risparmia spazio, ma non è stabile. Veda il codice.
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 nAlgoritmi in-place: spazio O(1)
Un algoritmo in-place modifica direttamente l'input senza usare memoria aggiuntiva proporzionale, come quando si inverte un array con due puntatori. In questo modo lo spazio resta O(1). Veda il codice.
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]Compromesso tempo-spazio: Two-Sum
Il compromesso tempo-spazio è ovunque. Two-sum richiede O(n^2) in termini di tempo e O(1) di spazio, oppure O(n) di tempo e O(n) di spazio usando una mappa hash. Indichi entrambe le alternative e chieda quale aspetto sia più importante.
# 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]Spazio di memoization e tabulazione
La memoization top-down richiede O(n) per la memo e O(n) per lo stack; la tabulazione bottom-up evita lo stack. Conservando solo le ultime righe, lo spazio si riduce a O(1): è la programmazione dinamica ottimizzata nello spazio.
# 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)) # 55Spazio della mappa hash: O(n)
Una mappa hash è il costo spaziale O(n) più comune nelle soluzioni: un insieme degli elementi già visti per i visitati, una mappa delle frequenze per il conteggio. Lo indichi sempre: "tempo O(n), spazio O(n)" è la risposta completa.
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']))Analisi dello spazio per gli algoritmi sui grafi
I grafi richiedono spazio reale: una lista di adiacenza è O(V + E), l'insieme dei visitati e la coda della BFS sono O(V), mentre la ricorsione della DFS può raggiungere una profondità O(V). Indichi lo spazio dei grafi usando V ed 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]Problemi nell'allocazione di stringhe e array
Le allocazioni nascoste possono introdurre uno spazio O(n): lo slicing crea una nuova lista e l'operatore + sulle stringhe all'interno di un ciclo è O(n^2). sorted() crea una copia, mentre lst.sort() modifica la lista in-place. Veda il codice.
# 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]Riconoscere i compromessi spaziali nei colloqui
Dichiari subito la complessità spaziale. Se l'intervistatore desidera ridurla, due strategie comuni sono usare la programmazione dinamica bottom-up invece della memoization oppure un ordinamento in-place invece di una mappa hash. Veda il codice.
# 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 FalseModello per dichiarare la complessità complessiva
Fornisca sempre una dichiarazione completa, indicando tempo e spazio: "tempo O(n), spazio aggiuntivo O(1)". Menzioni i compromessi quando esistono. È questo che distingue i candidati più esperti.
# 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]]Verifica rapida
Verifica rapida: vediamo quanto sono state comprese le idee sulla complessità spaziale. È pronto per questa prova. ✅
Riepilogo della lezione
Riepilogo: lo spazio ausiliario si conta separatamente dall'input, la ricorsione usa spazio nello stack pari a O(profondità) e il compromesso tempo-spazio orienta la maggior parte delle scelte nella progettazione degli algoritmi.
Domande Frequenti
La lezione «Complessità spaziale e compromessi» è gratuita?
Sì — il testo completo di «Complessità spaziale e compromessi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Complessità spaziale e compromessi»?
Misuri lo spazio ausiliario per gli stack delle chiamate e le strutture dati ausiliarie e riconosca i compromessi tra tempo e spazio nella memoisation e negli algoritmi in-place Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Complessità spaziale e compromessi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- La notazione Big-O dalle basi
- Analizzare cicli e cicli annidati
- Ricorsione e metodo dell'albero ricorsivo
- Complessità spaziale e compromessi