Spiegazione della complessità temporale e spaziale di un algoritmo.
Immaginate due programmi che svolgono esattamente lo stesso lavoro. Fornite a ciascuno mille record e non riuscirete a distinguerli. Fornitene invece un miliardo, e uno terminerà prima ancora che abbiate rilasciato il tasto Invio, mentre l'altro sarà ancora in esecuzione martedì prossimo.
Stesso portatile. Stessi dati. Ciò che li distingue è la complessità temporale, che non è altro che un modo per definire la velocità con cui il carico di lavoro di un algoritmo aumenta man mano che gli si fornisce più input.
Analizzeremo il significato effettivo del termine, come viene rappresentato nella notazione Big O, come ricavarlo da un codice reale e dove entra in gioco la complessità spaziale. Infine, parleremo di un ambito in cui tutto questo smette di essere un compito scolastico e inizia a costare denaro reale: gli smart contract.
Che cos'è la complessità temporale di un algoritmo?
Dimentichiamoci per un attimo dei secondi. La complessità temporale conta i passaggi. Confronti, assegnazioni, qualche calcolo qua e là, e il totale viene espresso in funzione di n, che rappresenta la dimensione dell'input.
Ecco la funzione più noiosa che si possa immaginare:
python def print_all(items): for item in items: print(item)
Dieci articoli? Dieci giri del circuito. Diecimila? Diecimila giri.
Il lavoro aumenta in linea retta rispetto all'input, quindi lo definiamo O(n).
Ora, forse ogni viaggio costa davvero tre piccole operazioni invece di una. Va bene, allora è 3n. Onestamente, a nessuno importa, perché raddoppiare la lista significa comunque raddoppiare il lavoro, e quella curva di crescita è proprio ciò che ci interessa. Il numero esatto viene scartato di proposito.
Ecco perché ogni corso di strutture dati e algoritmi e metà dei colloqui di lavoro per programmatori insistono sulla complessità temporale. Se riesci a dedurre la complessità di un algoritmo semplicemente guardandolo, puoi intuire come si comporterà con dati di input che non hai mai avuto modo di testare. Che, in produzione, costituiscono la maggior parte dei dati.
Perché il tempo di esecuzione è una misura inadeguata di un algoritmo
Allora perché non eseguire semplicemente il tutto con un timer? Molti lo fanno, e lo capisco. Il problema è che il tempo di esecuzione include una serie di elementi che non c'entrano nulla con il tuo algoritmo:
- Hardware. Il mio portatile di cinque anni e un nuovissimo server cloud vi daranno risultati completamente diversi per lo stesso script.
- Linguaggio di programmazione. Scrivi lo stesso ciclo in C e in Python e potresti notare una differenza di 10 volte, o anche di più.
- Caricamento del sistema. Si avvia un aggiornamento in background, il garbage collector si attiva, la cache è vuota. Il risultato si sposta.
- Qualunque sia l'input che ti è capitato di raccogliere. Un algoritmo di ordinamento che funziona velocemente su dati quasi ordinati può risultare estremamente lento su dati mescolati.
Un cronometro ti fornisce una singola misurazione su una singola scatola con un singolo input. Chiedigli di misurare 100 volte i dati e non saprà dirti nulla.
Il numero di passaggi non varia. Stesso algoritmo, stesso input, e si ottiene lo stesso numero di passaggi sia che si tratti di Rust su un server rack o di JavaScript su un telefono. Ecco perché la complessità temporale è un parametro di confronto equo tra due soluzioni prima ancora di averle confrontate. Io, comunque, le confronterei comunque in seguito, per quel che vale. È solo una questione diversa.
Spiegazione della notazione Big O e di altre notazioni asintotiche.
I libri di testo la chiamano notazione asintotica, che suona peggio di quanto non sia in realtà. Si lascia che n diventi enorme e si smette di preoccuparsi dei dettagli, quindi i moltiplicatori costanti e gli input piccoli vengono eliminati e sopravvive solo la curva di crescita. Ce ne sono tre che vale la pena conoscere:
| Notazione | Ciò che descrive | Significato semplice | Esempio |
|---|---|---|---|
| Grande O, O(f(n)) | limite superiore | L'algoritmo cresce non più velocemente di f(n) | La ricerca lineare è O(n) |
| Grande Omega, Ω(f(n)) | Limite inferiore | L'algoritmo necessita di almeno f(n) lavoro | Qualsiasi ordinamento per confronto è Ω(n log n) |
| Big-Theta, Θ(f(n)) | rilegatura stretta | I limiti superiore e inferiore corrispondono | L'algoritmo di merge sort è Θ(n log n) |
In pratica, sentirete parlare di notazione Big O circa il 95% delle volte. Essa definisce un limite superiore, il che significa che il tempo di esecuzione non crescerà più velocemente del valore indicato tra parentesi. Durante la mia prima revisione del codice in un vero lavoro, uno sviluppatore senior scrisse "O(n²), per favore correggi" accanto a un ciclo annidato, e ciò che intendeva dire era che la complessità temporale nel caso peggiore era quadratica e che la lista stava per diventare molto più lunga.
Omega e Theta sono usati principalmente nei corsi universitari di analisi degli algoritmi, e non credo di averli usati al lavoro da anni. La notazione O grande (Big O) è preferibile perché risponde alle domande che le persone pongono realmente durante una riunione, ovvero "quanto peggiorerebbe la situazione se il traffico triplicasse?".
C'è un dettaglio tecnico che mi ha confuso per un po'. Dato che la notazione O grande rappresenta solo un limite superiore, una funzione O(n) è anche O(n²), a rigor di termini, allo stesso modo in cui una persona alta 5 piedi è "sotto i 7 piedi". Vero, ma inutile. Ognuno cita il limite più stretto che riesce a giustificare e farò lo stesso.
Classi di complessità temporale comune con esempi
Non ci sono poi così tante classi che vedrai nel codice reale, forse sette se conti quelle più complesse. Ecco all'incirca quanto costa ciascuna con n = 1.000:
| Classe | Nome | Esempio tipico | Operazioni con n = 1.000 |
|---|---|---|---|
| O(1) | Costante | Indice dell'array, ricerca nella tabella hash | 1 |
| O(log n) | Logaritmo | Ricerca binaria | ~10 |
| SU) | Lineare | Scansione di un elenco | 1.000 |
| O(n log n) | Linearitmico | Merge sort, quicksort (media) | ~10.000 |
| O(n²) | Quadratica | Cicli annidati, ordinamento a bolle | 1.000.000 |
| O(2ⁿ) | Esponenziale | Fibonacci ricorsivo ingenuo | Più degli atomi nell'universo |
| SU!) | Fattoriale | Venditore ambulante con metodi brutali | Ancora più grande |
O(1): Tempo costante
Che il tuo dizionario Python abbia dieci chiavi o dieci milioni, estrarne una tramite chiave ha un costo pressoché identico, così come leggere gli elementi[5] da una lista. Questa piattezza è proprio il punto cruciale del tempo costante.
O(log n): Tempo logaritmico
Li considero come algoritmi del tipo "indovina il numero tra 1 e 100", dove ogni tentativo esclude metà delle possibilità rimanenti. La ricerca binaria fa esattamente questo su un elenco ordinato:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Con un miliardo di elementi ordinati, sono necessari circa 30 confronti, mentre esaminarli uno per uno potrebbe richiederne l'intero miliardo, e non ho mai smesso di trovare la cosa divertente.
O(n) e O(n log n)
Un algoritmo lineare visita ogni elemento un numero fisso di volte, proprio come faresti se cercassi a occhio il numero più grande in una colonna di un foglio di calcolo. O(n log n) è il livello ideale per un ordinamento efficiente. L'algoritmo di ordinamento per fusione (merge sort) suddivide l'elenco in singoli elementi (log n livelli di suddivisione) ed esegue un passaggio lineare per ogni livello durante la fusione, quindi il suo tempo di esecuzione rimane invariato sia che i dati arrivino ordinati o disordinati.
O(n²) e peggio
Il codice quadratico ha quasi sempre un ciclo annidato all'interno di un altro ciclo, come questo controllo di duplicati che confronta ogni coppia:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
La crescita esponenziale e fattoriale sono di gran lunga peggiori. La sequenza ricorsiva di Fibonacci, tipica dei manuali, continua a risolvere gli stessi sottoproblemi più e più volte, quindi ogni +1 su n raddoppia approssimativamente il lavoro. Con n = 20 non te ne accorgerai; con n = 60 puoi andare a cucinare la cena, mangiarla, lavare i piatti e il lavoro non sarà ancora finito.
Come calcolare la complessità temporale passo dopo passo
Non è quasi mai necessaria una dimostrazione formale per calcolare la complessità temporale. Ripasso mentalmente questo elenco e copre la maggior parte del codice che vedo:
- Definisci n. Decidi qual è la dimensione dell'input: la lunghezza di una lista, il numero di nodi in un grafo, il numero di cifre in un numero.
- Conta il lavoro in ogni riga. Le istruzioni semplici (assegnazioni, confronti, aritmetica) hanno un costo O(1).
- Aggiungi blocchi sequenziali. Due cicli uno dopo l'altro, ciascuno su n, danno n + n = 2n.
- Moltiplica i blocchi annidati. Un ciclo su n all'interno di un altro ciclo su n dà n × n = n².
- Eliminiamo le costanti. 2n diventa n e 500 diventa 1.
- Si consideri solo il termine dominante. In n² + n, la parte n² diventa di gran lunga più importante del resto al crescere di n.
Un calcolo rapido. Il tuo conteggio risulta essere T(n) = 3n² + 5n + 2. Aggiungi un milione: 3n² sono tre trilioni, 5n sono cinque milioni. Errore di arrotondamento. Chiamiamolo O(n²), fatto.
I circuiti che saltano da un punto all'altro invece di procedere uno alla volta sono più insidiosi:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Ogni passaggio dimezza n, quindi questo ciclo while si interrompe dopo circa log₂(n) iterazioni. Che è sostanzialmente la risposta completa alla domanda "quando la complessità temporale è O(log n)?". Se ciò che rimane si riduce di un fattore costante ad ogni passaggio, ci siamo.
La ricorsione richiede un altro strumento, una ricorrenza. L'algoritmo di ordinamento per fusione esegue due operazioni di dimensioni dimezzate e poi una fusione, quindi T(n) = 2T(n/2) + n. Il teorema principale è una sorta di promemoria per le ricorrenze di questa forma, e per questa in particolare restituisce O(n log n).
E una regola empirica che uso spesso nella programmazione competitiva: una macchina normale esegue circa 10⁸ operazioni semplici al secondo. È un valore molto approssimativo, ma è sufficiente per verificare la complessità temporale di una soluzione prima di inviarla. Con n pari a 10⁵, O(n²) corrisponde a circa 10¹⁰ operazioni, quindi si verifica un timeout. O(n log n) è inferiore a 2 milioni. Funziona perfettamente.
Analisi del caso peggiore, del caso migliore e del caso medio
Applicando input diversi allo stesso algoritmo, la quantità di lavoro può variare notevolmente. La ricerca lineare lo dimostra chiaramente:
- Nella migliore delle ipotesi, quello che cerchi è proprio lì, in prima fila. Un solo confronto e sei fuori.
- Nel peggiore dei casi: si trova proprio alla fine, oppure non c'è affatto. Questo significa n confronti.
- Caso medio: se potesse trovarsi ovunque con uguale probabilità, in media controllerai circa n/2 volte. Rimane comunque O(n), sia chiaro.
Chiedete a uno sviluppatore qual è la "complessità" di qualcosa e quasi sempre vi fornirà la complessità temporale nel caso peggiore, perché quel numero è una garanzia su cui basare la pianificazione.
Supponiamo che la tua API gestisca una richiesta in O(n) nel peggiore dei casi. Ottimo, ora sai come si comporta la richiesta più lenta e sei anche al sicuro nel caso in cui qualcuno ti invii dati spazzatura di proposito. C'è chi lo fa davvero: se un attaccante scopre quali chiavi causano una collisione nella tua tabella hash, per un po' vedrai solo quelle chiavi.
Vale la pena esaminare il caso medio, dato che lo scenario peggiore si verifica raramente. Quicksort ne è l'esempio perfetto, con una complessità media di O(n log n), che però scende a O(n²) se si scelgono ingenuamente i pivot su dati già ordinati. Le librerie standard aggirano questo problema utilizzando pivot casuali o passando a un algoritmo di ordinamento diverso quando la ricorsione diventa eccessivamente profonda.
Che cos'è la complessità dello spazio e lo spazio ausiliario?
La memoria è l'altra voce di spesa di un algoritmo. La complessità spaziale tiene traccia della quantità di memoria necessaria al crescere della dimensione dell'input e viene espressa con la stessa notazione Big O del tempo.
Una parte di quella memoria è costituita dall'input stesso, che si paga indipendentemente da ciò che si fa con esso. La parte che si controlla effettivamente si chiama spazio ausiliario, ovvero lo spazio extra che il codice alloca durante l'esecuzione, come variabili temporanee e nuovi array, oltre allo stack delle chiamate che nessuno ricorda finché non si verificano problemi.
Alcuni casi rapidi:
- Lo scambio di due variabili richiede un paio di slot a prescindere da qualsiasi altra cosa, quindi lo spazio ausiliario è O(1).
- Copiare un elenco di n elementi in un nuovo elenco comporta un costo di memoria aggiuntiva pari a O(n).
- La ricorsione a n livelli lascia n frame nello stack, che ha una complessità spaziale O(n) anche se non è mai stato creato un array.
Ho visto uno sviluppatore junior perdere un pomeriggio a causa di quell'ultimo problema. La sua funzione ricorsiva sembrava non utilizzare alcuna memoria, ma ogni chiamata incompiuta veniva bloccata sullo stack in attesa del ritorno di quelle più profonde, e con un input di grandi dimensioni l'intero programma si bloccava con un overflow dello stack.
Molte ottimizzazioni consistono semplicemente nello scambiare memoria con tempo, o viceversa. La memoizzazione memorizza nella cache i risultati già calcolati, riducendo la complessità temporale dell'algoritmo di Fibonacci da O(2ⁿ) a O(n) in cambio di O(n) memoria. Le tabelle hash consentono di ottenere un numero medio di ricerche pari a O(1) utilizzando spazio per i bucket. Su un server con 64 GB di RAM, questo scambio è solitamente scontato, ma su un microcontrollore o all'interno di uno smart contract ci pensereste due volte.
Complessità temporale e spaziale delle strutture dati comuni
Scegliere la struttura dati giusta è generalmente più efficace che ottimizzare nei minimi dettagli i dettagli del ciclo. Di seguito i costi medi per le strutture dati che utilizzerete più spesso:
| Struttura dei dati | Accesso | Ricerca | Inserire | Eliminare | Spazio |
|---|---|---|---|---|---|
| Vettore | O(1) | SU) | SU) | SU) | SU) |
| lista concatenata | SU) | SU) | O(1) | O(1) | SU) |
| Tabella hash | n / a | O(1) | O(1) | O(1) | SU) |
| Albero di ricerca binario bilanciato | O(log n) | O(log n) | O(log n) | O(log n) | SU) |
| Heap binario | O(1) per min/max | SU) | O(log n) | O(log n) | SU) |
Due note a piè di pagina. Le operazioni di inserimento e cancellazione nelle liste concatenate hanno complessità O(1) solo se si possiede già il nodo. Una tabella hash, invece, può arrivare a O(n) quando molte chiavi entrano in conflitto.
Anche gli algoritmi di ordinamento variano notevolmente:
| Algoritmo di ordinamento | Migliore | Media | Peggio | Spazio ausiliario |
|---|---|---|---|---|
| Ordinamento delle bolle | SU) | O(n²) | O(n²) | O(1) |
| Unione ordinamento | O(n log n) | O(n log n) | O(n log n) | SU) |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Ordinamento a heap | O(n log n) | O(n log n) | O(n log n) | O(1) |
L'algoritmo di ordinamento per fusione (merge sort) è prevedibile ma richiede memoria aggiuntiva. L'algoritmo di ordinamento heap (heap sort) ordina i risultati direttamente sul posto e mantiene lo stesso risultato nel caso peggiore. L'algoritmo di ordinamento rapido (quicksort), nonostante il risultato finale meno elegante, tende a essere più efficace nella pratica.
Complessità temporale nella blockchain e nei contratti intelligenti
Ecco dove la cosa si fa interessante. Sul tuo server, un algoritmo approssimativo spreca CPU e magari infastidisce un utente. Su Ethereum o su qualsiasi blockchain basata su EVM, spreca denaro. Ogni operazione eseguita da uno smart contract ha un costo in gas, pagato nella criptovaluta nativa della blockchain, quindi il conteggio delle operazioni si traduce in una voce sul conto di qualcuno. In altre parole, una cattiva complessità temporale ha un prezzo.
Supponiamo di avere un contratto che itera su ogni detentore di token per pagare le ricompense. O(n), e il gas aumenta con ogni nuovo detentore. Il giorno del lancio nessuno se ne accorge.
Poi l'elenco dei detentori continua a crescere. Un giorno il pagamento richiede più gas del limite di gas del blocco, ovvero il limite massimo di gas che un singolo blocco può contenere. Dopodiché la transazione non può essere completata. Non è "lenta". Semplicemente non va a buon fine e i fondi in attesa dietro a quella funzione rimangono bloccati. I revisori dei conti segnalano cicli illimitati come questo come attacchi denial-of-service, ed è giusto così.
La soluzione consiste nel pensare alla complessità, pura e semplice:
- Suddividi il lavoro in lotti di dimensioni fisse distribuiti su più transazioni.
- Capovolgilo in modo che ogni utente richieda la propria ricompensa. Ogni chiamata è O(1).
- Sostituisci l'anello con una prova Merkle.
Trovo molto utili le prove di Merkle come esempio del perché log n sia così importante sulla blockchain. Un albero di Merkle esegue l'hashing di una grande quantità di dati in un unico hash radice.
Per dimostrare che una voce appartiene a un insieme di n, sono necessari circa log₂(n) hash. Per un milione di voci, ciò significa circa 20. Non un milione. Gli airdrop si basano su questo principio e i wallet Bitcoin leggeri utilizzano lo stesso trucco per confermare una transazione senza scaricare l'intero blocco.
Anche off-chain la stessa cosa. Immaginate un sistema di pagamento che abbina ogni transazione blockchain in entrata a una fattura, scansionando tutte quelle aperte. O(n) per pagamento, e diventa più lento man mano che il negozio cresce. Inserite le fatture in una mappa hash con chiave per indirizzo o ID e ogni corrispondenza sarà O(1). E se preferite non costruire e gestire voi stessi questa infrastruttura, un gateway di pagamento in criptovalute come Plisio lo fa per voi.
