Algoritmi e complessità: domande di esercitazione con spiegazioni

1Che cosa misura la complessità

Un algoritmo è un elenco finito di passi precisi che risolve un problema, come ordinare una lista o trovare un nome in un elenco telefonico.

Due algoritmi possono risolvere lo stesso problema ma impiegare tempi molto diversi. La complessità descrive come il lavoro cresce al crescere dell’input.

La dimensione dell’input si chiama n: il numero di elementi da ordinare, la lunghezza di una lista, il numero di nodi di un grafo.

Pensa di cercare un nome in un elenco telefonico di 1000 pagine. Leggere ogni pagina richiede fino a 1000 passi. Aprirlo a metà e dimezzare ogni volta richiede circa 10 passi.

La complessità temporale conta i passi. La complessità spaziale conta la memoria aggiuntiva. Entrambe si scrivono come funzione di n.

Di solito si considera il caso peggiore: il lavoro massimo su tutti gli input di dimensione n. A volte si chiede invece il caso medio o il caso migliore.

2Notazione O grande e classi di crescita

La notazione O grande (Big O) conserva solo ciò che conta per n grande. Si eliminano i fattori costanti e si tiene solo il termine che cresce più in fretta.

Per n = 1000 il termine n² vale 3 000 000, mentre 5n è solo 5000. I termini più piccoli cambiano appena il totale.

Queste classi compaiono continuamente, dalla crescita più lenta alla più veloce:

• O(1), costante: leggere un elemento di un array tramite il suo indice.
• O(log n), logaritmica: la ricerca binaria, che dimezza il problema a ogni passo.
• O(n), lineare: un solo passaggio su tutti gli elementi, come trovare il valore massimo.
• O(n log n): buoni algoritmi di ordinamento come il merge sort.
• O(n²), quadratica: due cicli annidati sugli elementi, come il bubble sort.
• O(2ⁿ), esponenziale: provare ogni sottoinsieme. Diventa rapidamente inutilizzabile.

O grande è un limite superiore: il lavoro cresce al più così in fretta. Ω (Omega grande) è un limite inferiore, e Θ (Theta) è un limite stretto, sia superiore sia inferiore.

La base di un logaritmo non conta nella notazione O grande, perché i logaritmi con basi diverse differiscono solo per un fattore costante.

3Ricerca, ordinamento e ricorsione

Alcuni algoritmi ricorrono in quasi ogni corso. Impara le loro complessità come dati di fatto.

• La ricerca lineare controlla gli elementi uno a uno: O(n). La ricerca binaria richiede un array ordinato e dimezza l’intervallo a ogni passo: O(log n).
• Il bubble sort, l’insertion sort e il selection sort confrontano e scambiano elementi in cicli annidati: O(n²). L’insertion sort è O(n) su un array già ordinato.
• Il merge sort divide l’array in metà, le ordina e le fonde: O(n log n) in ogni caso, con O(n) di memoria aggiuntiva.
• Il quicksort divide attorno a un pivot: O(n log n) in media, ma O(n²) nel caso peggiore, per esempio un array ordinato con il primo elemento come pivot.
• Nessun ordinamento basato solo su confronti può fare meglio di Ω(n log n) nel caso peggiore. Il counting sort è più veloce perché non confronta.

Una funzione ricorsiva richiama se stessa su un input più piccolo finché raggiunge un caso base a cui risponde direttamente. Il suo tempo di esecuzione si scrive come una relazione di ricorrenza:

• T(n) = T(n/2) + O(1) dà O(log n), come la ricerca binaria.
• T(n) = 2T(n/2) + O(n) dà O(n log n), come il merge sort.
• T(n) = T(n − 1) + O(n) dà O(n²).
• T(n) = 2T(n − 1) + O(1) dà O(2ⁿ).

Vale la pena conoscere tre idee di progettazione. Divide et impera divide, risolve e combina. Il metodo greedy (goloso) sceglie a ogni passo l’opzione localmente migliore. La programmazione dinamica memorizza le risposte ai sottoproblemi sovrapposti così che vengano calcolate una sola volta.

4Il metodo passo dopo passo

Per trovare la complessità temporale di un frammento di codice:

1. Decidi che cos’è n: la dimensione dell’input.
2. Conta quante volte viene eseguito ogni ciclo. Un ciclo che somma 1 a ogni passo viene eseguito circa n volte. Un ciclo che raddoppia o dimezza viene eseguito circa log₂ n volte.
3. I cicli uno dentro l’altro si moltiplicano. I cicli uno dopo l’altro si sommano.
4. Per una funzione ricorsiva, scrivi la ricorrenza: quante chiamate, su quale dimensione, più il lavoro per chiamata.
5. Tieni il termine che cresce più in fretta ed elimina le costanti.
6. Controlla con un numero piccolo, per esempio n = 8 o n = 1024.

Per una domanda teorica, nomina prima l’algoritmo o l’idea che descrive, poi richiama la sua complessità e le sue condizioni (input ordinato, pesi non negativi, sottoproblemi sovrapposti).

5Un esempio svolto

Segui ogni passaggio. Prova a prevedere il successivo prima di aprirlo.

6Errori comuni

• Moltiplicare cicli che vengono eseguiti uno dopo l’altro. n + n = 2n è ancora O(n).
• Tenere le costanti, come in O(2n) o O(n/2). Entrambe sono O(n).
• Contare un ciclo che raddoppia come n giri. Viene eseguito circa log₂ n volte.
• Usare la ricerca binaria su dati non ordinati, o su una lista concatenata dove il punto centrale non si raggiunge in un solo passo.
• Dare il caso medio del quicksort quando viene chiesto il caso peggiore.
• Pensare che O grande significhi “esattamente”. O(n²) è un limite superiore; Θ(n²) è la crescita esatta.

7Come sono fatte le domande d’esame

• Facile: termini e fatti chiave. La complessità della ricerca binaria, del merge sort o dell’accesso a un array, il significato di O, Ω e Θ, che cos’è la ricorsione.
• Medio: applicare i concetti. La complessità di un frammento di codice, una ricorrenza da risolvere, come cambia il tempo quando n raddoppia, quale algoritmo si adatta a un compito.
• Difficile: casi e analisi. Il teorema master, i casi peggiori del quicksort, greedy contro programmazione dinamica, e le classi P, NP e NP-completo.

P contiene i problemi risolvibili in tempo polinomiale. NP contiene i problemi le cui soluzioni possono essere verificate in tempo polinomiale. Ogni problema in P è in NP; se P = NP è ancora sconosciuto.