DEV Community

frontendfacile.it
frontendfacile.it

Posted on Originally published at frontendfacile.it

Strutture dati e algoritmi in Python: capire davvero Big O, liste, puntatori e prestazioni

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)

  1. 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.
  2. O(n) – tempo lineare

    • Il lavoro cresce proporzionalmente ai dati.
    • Esempio: cercare un valore in una lista non ordinata scorrendo elemento per elemento.
  3. 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)

  1. O(n log n)

    • Tipico di ordinamenti efficienti.
    • È più di lineare ma molto meglio di quadratica.
  2. O(n²) – quadratica

    • Spesso nasce da un loop dentro un loop.
    • Segnale d’allarme: “per ogni elemento, scorro tutti gli altri”.
  3. 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² + n diventa 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
Enter fullscreen mode Exit fullscreen mode

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 list diventa 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)