Caso Migliore, Peggiore & Medio
Tre Modi per Misurare un Algoritmo
Il costo di ogni algoritmo dipende dal suo input. Due input della stessa dimensione possono produrre tempi di esecuzione molto diversi. L'analisi della complessità formalizza tre prospettive su questa variazione.
Caso migliore — Ω (Omega): l'input che fa finire l'algoritmo più velocemente. Per la ricerca lineare su un elenco di N elementi: Ω(1) — il bersaglio occupa la prima posizione. Un confronto, fatto.
Caso peggiore — O (Big O): l'input che fa finire l'algoritmo più lentamente. Per la ricerca lineare: O(N) — il bersaglio si trova ultimo nell'elenco, oppure non appare affatto. Ogni elemento richiede un'ispezione.
Caso medio — Θ (Theta): costo previsto su tutti i possibili input, supponendo una distribuzione uniforme. Per la ricerca lineare con il bersaglio ugualmente probabile di occupare una qualsiasi delle N posizioni: Θ(N/2) = Θ(N). La costante 1/2 cade perché Theta esprime una crescita asintotica stretta, non coefficienti esatti.
Perché il Caso Peggiore Predomina
I sistemi devono gestire il caso peggiore. Una query di database che in media richiede 10 ms ma occasionalmente impiega 60 secondi produce un errore visibile all'utente. Gli ingegneri progettano per limiti nel caso peggiore in modo che le prestazioni rimangono prevedibili indipendentemente dall'input. L'analisi del caso medio ha valore in contesti probabilistici, ma l'analisi del caso peggiore fornisce garanzie.
Analisi dei Casi di Ricerca Binaria
La ricerca binaria funziona solo su array ordinati. Ad ogni passo: confronta il bersaglio con l'elemento al punto medio. Se il bersaglio è uguale al punto medio, lo restituisce. Se il bersaglio è più piccolo, ricorre sulla metà sinistra. Se più grande, ricorre sulla metà destra.
Ogni confronto elimina metà dei candidati rimanenti.
Crescita della Memoria & Trade-off Tempo-Spazio
Contare la Memoria, Non le Operazioni
La complessità del tempo misura il numero di operazioni che un algoritmo esegue. La complessità dello spazio misura la memoria aggiuntiva che alloca oltre il suo input. Entrambi sono importanti nei sistemi di produzione: un algoritmo veloce che alloca O(N²) di memoria esaurirà un server.
O(1) spazio: memoria aggiuntiva costante indipendentemente da N. Un ordinamento in-place (ad es. insertion sort) scambia elementi all'interno dell'array originale. Utilizza una manciata di variabili temporanee — O(1) non importa quanto grande sia l'array.
O(N) spazio: memoria proporzionale alla dimensione dell'input. La creazione di una copia di un array di N elementi richiede N slot. La costruzione di un set hash da un elenco di N stringhe memorizza fino a N voci.
O(N²) spazio: memoria proporzionale a N². La costruzione di una matrice di adiacenza N×N per un grafo con N vertici richiede N² celle. Con N = 10.000 vertici, sono 10^8 voci — centinaia di megabyte per una semplice griglia booleana.
Trade-off Tempo-Spazio
Una delle mosse fondamentali nella progettazione di algoritmi: scambia spazio per tempo, o tempo per spazio.
Le tabelle hash utilizzano O(N) spazio aggiuntivo per ottenere la ricerca O(1). Senza la tabella hash, una scansione su un elenco ottiene la ricerca O(N) con O(1) spazio aggiuntivo. La tabella hash paga memoria per acquistare velocità.
La memoizzazione memorizza i risultati calcolati in precedenza (O(N) o più spazio) per evitare di ricalcolarli. Fibonacci ricorsivo senza memoizzazione viene eseguito in tempo O(2^N). Con memoizzazione: O(N) tempo e O(N) spazio. L'investimento di spazio riduce il tempo in modo esponenziale.
Dizionario Hash vs Elenco Ordinato
Confronta due strategie per contare le occorrenze di parole in un documento di N parole:
Strategia A: un dizionario (hash map). Inserisci ogni parola; incrementa il suo conteggio.
Strategia B: mantieni un elenco ordinato di parole viste; usa la ricerca binaria per controllare l'appartenenza prima di inserire.
Analisi Ammortizzata: Distribuire il Costo
Quando la Spesa Occasionale Non Rovina le Prestazioni Medie
Alcune operazioni sono occasionalmente costose ma economiche in media su una sequenza. L'analisi ammortizzata calcola il costo medio per operazione su l'intera sequenza — non il costo nel caso peggiore di una singola operazione.
Array dinamico (lista Python, ArrayList Java): inizia con capacità 1. Quando pieno, raddoppia la capacità. Il raddoppio copia tutti gli elementi esistenti: lavoro O(N) per un append. Ma i raddoppi sono rari. Dopo N append totali, quante operazioni di copia totali si sono verificate?
I raddoppi si verificano alle dimensioni 1, 2, 4, 8, ..., N/2. Conteggi di copia: 1 + 2 + 4 + ... + N/2. Questa è una serie geometrica che somma a N − 1 copie totali su tutti gli N append. Medie di copia per append: (N − 1) / N < 1, quindi O(1) ammortizzato per append nonostante il costo nel caso peggiore O(N) per raddoppio.
Perché l'Analisi Ammortizzata Importa
Un sistema che occasionalmente fa una pausa per ridimensionare, ribilanciare o compattare una struttura può sembrare avere operazioni individuali allarmanti nel caso peggiore. L'analisi ammortizzata rivela che l'allarme è falso: gli eventi costosi rari vengono pagati da quelli economici. Comprendere il costo ammortizzato previene l'over-engineering: aggiungere complessità per evitare una rara operazione O(N) che contribuisce solo O(1) ammortizzato è lavoro sprecato.
Approfondimento: il corso unhamming applica l'analisi di complessità ai difetti del mondo reale nel software di produzione. Vedi Il Capitolo Mancante: Complessità Algoritmica & MOAD-0001: Il Difetto Sedimentario.
Inserimento Ammortizzato di Tabella Hash
Una tabella hash inizia vuota e raddoppia la capacità ogni volta che il fattore di carico supera 0,75. Inserire 1.000 elementi attiva esattamente 10 raddoppi alle capacità 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.