Dalla complessità asintotica al comportamento reale delle strutture built-in: una guida ragionata per non memorizzare codice, ma scegliere la soluzione giusta.
Perché vale la pena studiare strutture dati (anche se fai frontend)
Quando un’app “va lenta”, raramente è colpa di un singolo if. Più spesso è una scelta strutturale: come rappresenti i dati e quali operazioni ripeti. Questo vale lato server, ma anche in frontend (pensiamo a rendering di liste, filtri, ricerche, deduplica, caching). Python è un ottimo linguaggio per imparare questi concetti perché la sintassi non ti distrae: puoi concentrarti sull’idea.
L’obiettivo qui non è collezionare snippet da ripetere a memoria, ma sviluppare una bussola: capire il costo delle operazioni, cosa succede in memoria e quando una struttura dati ti sta sabotando.
Big O: misurare la crescita, non i secondi
Se due programmi producono lo stesso risultato, “il migliore” non è quello più veloce sul tuo laptop oggi, ma quello che scala meglio quando l’input cresce.
Big O descrive proprio questo: la forma della crescita del lavoro al crescere dei dati. Non è un cronometro, è un linguaggio per ragionare.
Le tre complessità “buone” (quelle che vorresti vedere spesso)
-
O(1) – tempo costante
- Il numero di operazioni non dipende dalla dimensione dell’input.
- Esempio tipico: accesso per indice in una struttura contigua (come un array): prendi l’elemento
i“saltando” direttamente all’indirizzo giusto.
-
O(n) – tempo lineare
- Il lavoro cresce proporzionalmente ai dati.
- Esempio: cercare un valore in una lista non ordinata scorrendo elemento per elemento.
-
O(log n) – tempo logaritmico
- Ogni passo elimina metà del problema.
- Esempio: binary search, ma funziona solo su collezioni ordinate.
- Il punto chiave: anche con dataset enormi, i passi crescono lentamente (raddoppiare i dati aggiunge circa “un passo”).
Le complessità “pericolose” (quelle da riconoscere al volo)
-
O(n log n)
- Tipico di ordinamenti efficienti.
- È più di lineare ma molto meglio di quadratica.
-
O(n²) – quadratica
- Spesso nasce da un loop dentro un loop.
- Segnale d’allarme: “per ogni elemento, scorro tutti gli altri”.
-
O(2^n) – esponenziale
- Aumentare l’input di 1 raddoppia (o peggio) il lavoro.
- Ricorre in soluzioni ricorsive naive (es. Fibonacci senza memoization) o nel generare tutti i sottoinsiemi.
Le 3 regole pratiche di Big O
-
1) Ignora le costanti:
2nè comunque O(n). -
2) Tieni il termine dominante:
n² + ndiventa O(n²). - 3) Ragiona sul caso peggiore (worst case): utile perché ti dà una promessa affidabile.
Se ti porti a casa solo una cosa: ricordati l’ordine mentale
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)
Array e liste Python: contiguità, indici e costi nascosti
Un array (in senso classico) è una sequenza di elementi in memoria uno dopo l’altro, senza buchi. Questo abilita l’accesso per indice:
- se conosci l’indirizzo iniziale,
- e la dimensione di ogni cella,
puoi calcolare l’indirizzo di i con una formula. Risultato: accesso O(1).
La particolarità importante: la lista Python non contiene “valori”, ma riferimenti
In Python, una list è un array dinamico di puntatori (riferimenti) agli oggetti, non un blocco di valori omogenei.
Conseguenze:
- puoi mescolare tipi diversi (numeri, stringhe, altre liste) perché ogni cella contiene un riferimento di dimensione fissa;
- l’accesso per indice resta veloce (O(1)) perché stai sempre indicizzando un array di riferimenti.
Append: perché è “O(1) ammortizzato”
append() in fondo è in genere veloce. Ma ogni tanto la lista deve riallocare: chiede un blocco più grande, copia i riferimenti e continua.
Python gestisce questa crescita a scatti, mantenendo capacità extra. Quindi:
- molte append costano pochissimo,
- poche append costano tanto,
- mediamente, su molte operazioni, il costo è O(1) ammortizzato.
Insert all’inizio (o in mezzo): perché costa O(n)
Inserire in posizione 0 significa che tutti gli elementi esistenti devono scorrere di una cella per fare spazio.
-
insert(0, x)→ O(n) -
insert(i, x)→ O(n) nel worst case
Stesso discorso per rimuovere:
-
pop()in fondo → O(1) -
pop(0)→ O(n) (tutti gli elementi devono “chiudere il buco”)
Ricerca in lista non ordinata: O(n)
Operatori come in o metodi come .index() su liste non ordinate fanno una scansione lineare nel caso peggiore: O(n).
Due trappole che prima o poi colpiscono tutti
1) Slicing crea copie
x[2:5] costruisce una nuova lista copiando i riferimenti: costo proporzionale alla dimensione della slice.
2) Assegnazione non copia
y = x non duplica la lista: y e x puntano allo stesso oggetto. Mutare una cambia anche l’altra.
3) Griglie con moltiplicazione: righe “clonate”
Un classico:
grid = [[0]*3]*3
Non crea 3 righe indipendenti: duplica lo stesso riferimento 3 volte. Modificare una “riga” le modifica tutte.
Soluzione: creare una riga nuova ogni volta (es. list comprehension).
Liste concatenate: paghi l’accesso, guadagni inserimenti
Il limite strutturale dell’array è la contiguità: per inserire davanti devi spostare tutto.
La linked list cambia modello mentale:
- ogni elemento vive “dove capita” in memoria;
- ogni nodo contiene valore + puntatore al prossimo;
- hai un punto d’ingresso, la head.
Il prezzo: accesso per indice è O(n)
Non puoi saltare al nodo i con una formula: devi partire dalla head e seguire i puntatori uno a uno.
Il vantaggio: inserire/rimuovere senza spostare elementi
Per inserire un nodo in mezzo:
- crei il nuovo nodo,
- punti il nuovo nodo al “futuro” (il nodo successivo),
- poi punti il “passato” (il nodo precedente) al nuovo.
Non sposti blocchi di memoria: cambi solo puntatori.
Nota pratica importante: l’ordine delle assegnazioni conta. Se perdi il riferimento al pezzo di lista che segue, lo hai perso davvero.
Implicazioni pratiche: come scegliere velocemente
Ecco una sintesi operativa utile quando scrivi codice (Python o non solo):
-
Leggi spesso per indice?
listè perfetta → accesso O(1). -
Aggiungi spesso in fondo?
append()va benissimo → O(1) ammortizzato. -
Inserisci/rimuovi spesso all’inizio? una
listdiventa un costo nascosto → operazioni O(n); valuta strutture alternative. - Devi cercare spesso e velocemente? una lista non ordinata non scala → la ricerca è O(n); valuta strutture basate su hashing (quando ha senso) o mantieni i dati ordinati per fare binary search.
Conclusione
Imparare strutture dati e algoritmi significa imparare a leggere il costo del codice prima ancora di eseguirlo. Big O ti dà il vocabolario; capire come una list si comporta in memoria ti dà l’intuizione; conoscere modelli alternativi come le liste concatenate ti aiuta a scegliere la struttura giusta quando il profilo d’uso cambia.
La conseguenza più concreta è questa: quando un pezzo di codice rallenta con l’aumentare dei dati, spesso non serve “ottimizzare”, ma cambiare forma al problema—e quindi la struttura dati su cui lo stai appoggiando.
Articolo originale: https://frontendfacile.it/blog/strutture-dati-e-algoritmi-in-python-capire-davvero-big-o-liste-puntatori-e-pres
Top comments (0)