Complessità di spazio: come gli algoritmi usano la memoria

La complessità di spazio misura l'uso di memoria degli algoritmi man mano che cresce la dimensione dell'input. Capirla è fondamentale per gestire le risorse in ambienti con vincoli.

In questo articolo ti spiego in dettaglio cos'è la complessità di spazio, come calcolarla e come ridurla. Inoltre, tratto applicazioni reali e fornisco le basi teoriche.

Capire la complessità di spazio

Prima di entrare in calcoli e ottimizzazioni, chiaramo cosa significa davvero complessità di spazio e perché ti dovrebbe interessare.

Che cos'è la complessità di spazio?

La complessità di spazio è la memoria totale richiesta dall'algoritmo in funzione della dimensione dell'input. È rilevante per analizzare l'impronta di memoria nel caso peggiore ai fini della scalabilità del sistema; lo spazio totale include input, memoria ausiliaria e overhead, mentre lo spazio ausiliario è la memoria extra che esclude input e output. Prendiamo come esempio l'ordinamento di un array: lo spazio totale include l'array stesso, mentre lo spazio ausiliario potrebbe essere la memoria temporanea nel merge sort.

Perché la complessità di spazio conta

Nel computing moderno, l'efficienza di spazio è spesso critica. Ottimizzando la complessità di spazio, ti assicuri che i tuoi algoritmi girino su dispositivi con RAM limitata, come i sistemi embedded nell'IoT o gli smartphone, o anche su grandi sistemi con procedure molto esigenti, dove ogni bit di RAM conta.

Pensa alle app mobile: ottimizzare la complessità di spazio aiuta a evitare crash durante l'elaborazione di immagini. O pensa ai risparmi sui costi di archiviazione nel cloud, o allo streaming dei dati, e ad analisi in tempo reale senza caricare tutti i dati.

Analisi asintotica e notazione Big O per lo spazio

In questa sezione spiego come le notazioni asintotiche come la Big O descrivono la crescita dello spazio, e ti fornisco strumenti per delimitare e confrontare l'uso di memoria.

Introduzione alla notazione Big O

Matematicamente, una funzione f(n) è dominata da una funzione g(n) se esistono costanti c e k tali che per tutti k>n, 0 ≤ |f(n)| ≤ |g(n)|.

In questo caso, si scrive f(n)=O(g(n)) e si dice che f(n) è big O di g(n).

In termini più semplici, significa che f(n) non cresce più velocemente di g(n) a partire da un certo indice.

La notazione Big O rappresenta il limite superiore dello spazio come funzione della dimensione dell'input n, così possiamo concentrarci sui termini dominanti per n grandi. Questa notazione aiuta a classificare gli algoritmi; ad esempio, O(n) significa che lo spazio raddoppia se raddoppia l'input.

C'è un malinteso comune tra i principianti: la Big O per lo spazio ignora le costanti, quindi 2n è O(n); ma nella pratica, le costanti contano per n piccoli.

Notazioni asintotiche correlate

Ci sono diversi modi per modellare la complessità e diverse notazioni. Per esempio, Big Omega fornisce un limite inferiore ed è utile per dimostrare i requisiti minimi di spazio, come nel caso dell'ordinamento che richiede almeno Ω(n). Un'altra notazione è Big Theta, che dà un limite stretto quando superiore e inferiore coincidono, ed è ideale per analisi precise, come O(n) = Θ(n) per lo spazio lineare.

Altre convenzioni notazionali

Esistono altre convenzioni rilevanti nella letteratura sulla complessità di spazio, come la notazione Soft-O Õ, che ignora i fattori polilogaritmici. È comune in algoritmi avanzati come l'elaborazione di grafi, dove i log sono trascurabili. Compare negli articoli teorici per complessità approssimate come Õ per spazi sublineari negli algoritmi di streaming.

Componenti della complessità di spazio

La complessità di spazio ha molti contributori e punti di ottimizzazione nel design degli algoritmi. Vediamoli:

Requisiti di spazio dell'input

I dati di input occupano spazio proporzionale alla dimensione, ad esempio O(n) per un array o per l'analisi di un grande dataset come le sequenze genomiche.

Nelle interviste tecniche reali è comune escludere lo spazio di input quando si calcola lo spazio ausiliario e concentrarsi solo sulla memoria extra usata dall'algoritmo. Nel competitive programming, invece, lo spazio totale include di solito l'input.

Spazio ausiliario e memoria temporanea

Lo spazio ausiliario è la memoria extra di cui un algoritmo ha bisogno per eseguire le sue operazioni. Influisce direttamente su come l'algoritmo è progettato.

Perciò, puoi ad esempio avere O(n) per l'array temporaneo in un algoritmo di merge sort. Un altro esempio sono le tabelle hash per i duplicati (O(n)), gli stack di ricorsione per la corrispondenza di parentesi (O(n)) e molti altri.

Esempi classici di spazio ausiliario includono metodi a due puntatori (O(1)), algoritmi a finestra scorrevole con deque (O(k)) e BFS, che richiede O(V) spazio per l'insieme dei visitati e la coda.

Il seguente codice mostra un esempio di operazione di merge sort sull'array temporaneo durante il passo di unione:

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...Offerto da

Lo stack delle chiamate e lo spazio della ricorsione

Ogni chiamata ricorsiva aggiunge un frame di stack (indirizzo di ritorno + parametri + variabili locali).

La ricorsione lineare, come il fattoriale o il DFS su una lista collegata, ha uno stack O(n).

La ricorsione binaria, come il Fibonacci ingenuo o la ricorsione sugli alberi, ha O(n) nel caso peggiore.

L'ottimizzazione delle tail-call, supportata in Scheme, Rust e talvolta in Python con decorator, riduce a O(1). Tuttavia, il vero pericolo qui riguarda il limite di ricorsione predefinito di Python, intorno a 1000, che causerebbe uno stack overflow su alberi profondi.

Ecco un esempio di Fibonacci ricorsivo ingenuo che mostra la crescita dello stack:

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

Dai un'occhiata al nostro blog Analizzare la complessità del codice in Python per saperne di più sull'analisi della complessità in Python.

Overhead delle strutture dati

Il lato positivo dell'overhead delle strutture dati è la sua semplicità, perché tutte le strutture aggiungono costi fissi/per elemento: per esempio l'overhead minimo degli array, il doppio spazio dei puntatori nelle liste collegate, e molti altri esempi. 

Detto ciò, il linguaggio di programmazione ha un'enorme influenza. Le liste Python hanno overhead dinamico, a differenza degli array in C; per esempio, le hash map con fattore di carico al 75% sprecano spazio in bucket vuoti.

Tipi di complessità di spazio

Complessità costante: O(1)

La complessità di spazio costante è la soluzione fondamentale e ottimale, quando disponibile. Molti algoritmi noti hanno davvero complessità costante, come semplici scambi di variabili, ad esempio quello qui sotto, un semplice swap in-place usando l'unpacking di tuple in Python:

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

Altri algoritmi noti a complessità costante sono la partizione a bandiera olandese nel quicksort e la traversata di Morris per gli alberi. C'è però un limite pratico: puoi avere qualche dozzina di variabili prima che sia efficace; a seconda dell'hardware, nei casi peggiori, O(1) a volte non basta se la memoria richiesta supera le risorse del sistema.

Complessità lineare: O(n)

Una complessità di spazio lineare è semplicemente proporzionale all'input. Alcuni esempi: un array extra per la copia o un insieme hash per gli unici. L'uso più comune ricade nei pattern di elaborazione dati, come il filtraggio di liste.

Complessità logaritmica e sublineare

Una complessità logaritmica indica che la memoria usata da un algoritmo cresce molto lentamente all'aumentare dell'input. In particolare, è proporzionale al logaritmo della dimensione dell'input.

Per esempio, la ricorsione di ricerca binaria ha profondità di stack O(log(n)), così come i divide-et-impera con tail recursion o gli algoritmi di streaming, che approssimano risultati in spazio O(log(n)) o O(sqrt(n)).

Le complessità logaritmiche e sublineari sono rare, ma potentissime per dataset massivi. Un esempio di complessità logaritmica con la ricerca binaria iterativa (spazio costante) è mostrato nel codice seguente:

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

Complessità quadratica: O(n²)

Si ha complessità quadratica quando la memoria richiesta scala con il quadrato dell'input. Un esempio comune è la tabella di programmazione dinamica 2D, che ha complessità O(n²), o una matrice di adiacenza per grafi con complessità O(V²). È importante notare che questa complessità diventa poco pratica oltre migliaia di elementi di input.

Complessità esponenziale e fattoriale

La complessità esponenziale, come suggerisce il nome, fa crescere la memoria richiesta in modo proporzionale all'esponente della dimensione dell'input O(2^n), e si verifica, ad esempio, quando memorizzi tutti i sottoinsiemi o i percorsi di un albero decisionale.

Allo stesso modo, nella complessità fattoriale, la memoria richiesta è proporzionale al fattoriale della dimensione dell'input O(n!), e ciò avviene quando enumeri tutte le permutazioni dell'input. Tuttavia, queste complessità sono generalmente molto costose e quasi certamente impraticabili per n>20-30 nella maggior parte dei sistemi. Se lavori con questi casi, potresti aver davvero bisogno di potature, approssimazioni o di un approccio diverso.

Come calcolare la complessità di spazio

Un'analisi sistematica identifica tutte le allocazioni di memoria e i loro pattern di crescita:

Approccio di analisi riga per riga

Il primo passo è esaminare il tuo codice riga per riga e identificare ogni variabile, array e oggetto allocato. Il passo successivo è determinare se la dimensione di ciascuna allocazione dipende dai parametri di input. Poi, somma la memoria per le allocazioni indipendenti e prendi il massimo per i rami mutuamente esclusivi. Infine, traccia sia le allocazioni sullo stack per le variabili locali, sia quelle sull'heap per la memoria dinamica. Ecco un esempio:

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 spaceOfferto da

Analisi della complessità ricorsiva

La complessità di spazio per la ricorsione è pari alla massima profondità di ricorsione moltiplicata per lo spazio per frame di chiamata; poi aggiungi eventuali strutture dati ausiliarie allocate durante la ricorsione, identifica il caso base e analizza come la profondità di ricorsione si relaziona alla dimensione dell'input. Ad esempio, il Fibonacci ingenuo crea profondità O(n) con O(1) per frame, per un totale di spazio stack O(n). Ecco un esempio per il calcolo dello spazio del fattoriale:

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

Analisi della complessità nella programmazione dinamica

Le tabelle DP standard hanno dimensioni che corrispondono ai parametri dei sottoproblemi; quindi, un problema monodimensionale richiede spazio O(n), e problemi bidimensionali necessitano O(nxm). Tecniche di ottimizzazione come i rolling array riducono una dimensione trasformando, per esempio, O(n²) in O(n). La compressione degli stati sfrutta le dipendenze, quindi se la riga i ha bisogno solo di i-1, conserva solo due righe. Ecco un esempio di Fibonacci ottimizzato in spazio usando solo due variabili:

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

Se ti incuriosisce la dimensionalità e la sua riduzione, ti invito a consultare i nostri tutorial su Mastering Slowly Changing Dimensions (SCD) e Understanding Cardinality: Challenges and Solutions for Data-Heavy Workflows.

Passi per calcolare la complessità di spazio in pratica

Per calcolare la complessità di spazio in pratica, segui questi passaggi:

1. Chiarisci se lo spazio di input è incluso, in base al contesto
2. Conta variabili e costanti a dimensione fissa. Contribuiscono O(1)
3. Misura le strutture ausiliarie come array e hash map in funzione della dimensione dell'input
4. Calcola la massima profondità di ricorsione per il contributo di spazio dello stack
5. Combina tutti i componenti ed esprimi usando il limite asintotico più stretto.

La complessità di spazio degli algoritmi comuni

Requisiti di spazio degli algoritmi di ordinamento

L'algoritmo di merge sort richiede spazio ausiliario O(n) per gli array temporanei durante il merge. D'altra parte, Quicksort usa in media O(log n) di spazio per lo stack, ma O(n) nel caso peggiore senza ottimizzazioni. Heapsort, invece, ottiene O(1) di spazio ausiliario ordinando in-place, come mostra il codice seguente:

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 spaceOfferto da

Infine, il counting sort necessita di spazio O(k), dove k è l'intervallo di valori, ma è poco pratico quando k>>n.

Complessità di spazio degli algoritmi sui grafi

L'attraversamento dei grafi ha molti algoritmi. Per esempio, la breadth-first search (BFS) mantiene una coda che richiede O(V) spazio per i vertici, mentre la depth-first search (DFS) usa O(V) di spazio per lo stack nel caso peggiore alla massima profondità. L'algoritmo di Dijkstra, invece, necessita di O(V) per la coda di priorità e il tracciamento delle distanze per ciascun vertice. La rappresentazione del grafo conta: la matrice di adiacenza usa O(V²), mentre la lista di adiacenza usa O(V+E). 

Caratteristiche di spazio delle strutture dati

Esistono diverse strutture dati e ognuna richiede allocazioni di memoria differenti. Per esempio, Array e ArrayList memorizzano n elementi in memoria contigua O(n), le liste collegate richiedono spazio O(n) più l'overhead del puntatore per ogni nodo, gli alberi binari usano spazio O(n) con 2-3 puntatori per nodo che aggiungono un overhead significativo, le tabelle hash consumano spazio O(n) moltiplicato per il fattore di carico che tipicamente varia tra 1,5 e 3 volte, e le liste di adiacenza offrono efficienza di spazio O(V+E) per grafi sparsi.

Esempi di calcolo della complessità di spazio

Ecco alcuni esempi di calcolo della complessità di spazio

# 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] = 0Offerto da

Complessità di spazio vs. complessità temporale

Tempo e spazio rappresentano dimensioni di risorsa distinte che vanno bilanciate in base ai vincoli del sistema:

Differenze e somiglianze chiave

A prima vista, complessità di spazio e di tempo possono sembrare simili, ma sono anche diverse perché la complessità temporale misura le operazioni computazionali, mentre la complessità di spazio misura il consumo di memoria. Sebbene usino notazioni asintotiche e quadri di analisi matematica identici, devi sapere che gli algoritmi possono essere ottimali in una dimensione ma inefficienti nell'altra. L'ottimizzazione spesso comporta scambiare più spazio per meno tempo o viceversa.

Capire il trade-off fondamentale

Quando scambi spazio per tempo, memorizzi risultati precomputati che eliminano calcoli ridondanti. Al contrario, scambiare tempo per spazio richiede di ricalcolare i valori su richiesta invece di conservarli. Le tabelle di lookup scambiano un investimento una tantum di spazio per accessi ripetuti O(1). Possono esserci vincoli specifici come limiti di memoria e requisiti prestazionali che impongono quale risorsa privilegiare.

Memoization e ottimizzazione nella programmazione dinamica

La memoization funziona salvando i valori invece di ricalcolarli; è efficiente in tempo ma sfavorevole in spazio. Aggiunge, ad esempio, una cache O(n) al Fibonacci ricorsivo, ma riduce il tempo da O(2^n) a O(n), come nell'esempio qui sotto di Fibonacci memoizzato, evitando ricomputazioni:

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]Offerto da

La programmazione dinamica bottom-up, invece, calcola in modo iterativo per eliminare l'overhead dello stack di ricorsione. Per ottimizzare lo spazio, mantieni solo gli stati precedenti necessari al calcolo corrente; ad esempio, la distanza di edit può essere ridotta dalla tabella O(nxm) a O(min(n,m)) conservando una sola riga.

Tecniche di algoritmi in-place

Gli algoritmi in-place modificano direttamente l'input invece di allocare nuove strutture di memoria; iterati, aiutano significativamente con le allocazioni di memoria e quindi riducono la complessità di spazio, come nell'esempio seguente di rotazione di array in-place (algoritmo della reversa):

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)Offerto da

Altre tecniche in-place riducono drasticamente l'uso di memoria. Per esempio, la tecnica dei due puntatori manipola gli array con spazio ausiliario O(1), e il cyclic sort gestisce problemi di permutazioni in O(1) scambiando gli elementi nelle posizioni corrette. Tuttavia, vale la pena notare che la modifica in-place può distruggere i dati di input, influenzando la riusabilità e la chiarezza del codice.

Selezione delle strutture dati per l'efficienza di spazio

Esistono molte strutture dati, ciascuna con trade-off diversi; pertanto, ad esempio, preferisci gli array alle liste collegate quando la dimensione è nota, elimina l'overhead per elemento dei puntatori e usa i bit per memorizzare flag booleani con una compressione 8 volte superiore rispetto agli array di byte. I trie condividono prefissi comuni per offrire efficienza di spazio su grandi collezioni di stringhe. Per grafi sparsi, scegli liste di adiacenza invece di matrici per ottenere O(V+E) invece di O(V²) di spazio.

Considerazioni pratiche e realtà di implementazione

La complessità di spazio nel mondo reale dipende da linguaggi di programmazione, architettura hardware e ambienti di runtime.

Fattori di linguaggio e ambiente di runtime

I linguaggi di alto livello come Python e Java aggiungono metadati per oggetto e overhead, a differenza di C e C++, che offrono gestione manuale della memoria per un controllo preciso al costo della complessità. È probabilmente per questo che i framework di ottimizzazione per il machine learning come PyTorch usano C++ per il calcolo.

I limiti della dimensione dello stack variano tipicamente da 1 a 8MB, il che limita la profondità massima di ricorsione. Nota che i sistemi a 64 bit usano puntatori da 8 byte mentre quelli a 32 bit usano puntatori da 4 byte, raddoppiando le dimensioni delle strutture di puntatori. Per scoprire come i dati ad alta dimensionalità influenzano le prestazioni degli algoritmi, consulta il nostro tutorial: The Curse of Dimensionality in Machine Learning.

Gerarchia di memoria ed effetti della cache

L'uso di spazio e le prestazioni degli algoritmi dipendono fortemente dalla gerarchia di memoria. L'accesso alla RAM richiede circa 100 nanosecondi e l'accesso alla cache della CPU da 1 a 10 nanosecondi, che è 100 volte più veloce. Inoltre, l'accesso sequenziale alla memoria sfrutta le cache line, dove tipicamente 64 byte vengono caricati insieme.

Gli algoritmi con buona località spaziale ottengono prestazioni migliori grazie all'efficienza della cache. Quindi, quando si lavora su insiemi grandi che superano la capacità, si verifica thrashing, che degrada fortemente le prestazioni.

Garbage collection e gestione della memoria

Uno strumento utile per la gestione della memoria è la garbage collection, che consente di ripulire i dati non più utili. In altre parole, i garbage collector aggiungono overhead di memoria per il tracciamento degli oggetti e la gestione delle generazioni.

L'uso di memoria di picco supera la dimensione dei dati vivi a causa delle allocazioni fatte prima dei cicli di raccolta. Inoltre, la GC generazionale è ottimizzata per oggetti di breve vita mantenendo le generazioni giovani in spazi più piccoli. Tuttavia, se vuoi un controllo più deterministico dello spazio, puoi usare la gestione manuale della memoria, ma devi essere consapevole dei rischi, come i memory leak e la frammentazione.

Conclusioni e raccomandazioni

Grazie per aver letto il mio articolo sulla complessità di spazio. Ti lascio con alcuni consigli finali:

• Chiarisci sempre se l'analisi dello spazio include la dimensione dell'input per evitare fraintendimenti in interviste e code review.
• Dai priorità prima alla correttezza, poi ottimizza lo spazio solo quando il profiling rivela veri colli di bottiglia.
• Cerca di considerare vincoli hardware e di memoria già nelle fasi iniziali di progettazione del sistema per evitare refactoring costosi.
• Scegli sempre gli strumenti di profiling adatti al linguaggio per validare l'analisi teorica rispetto al comportamento reale e bilancia l'ottimizzazione dello spazio con la leggibilità del codice. Ottimizzazioni troppo sofisticate possono nuocere anche alla manutenibilità.