Tanti algoritmi per un solo problema
Un algoritmo è una serie di passi precisi per risolvere un problema. La maggior parte dei problemi si può risolvere con più di un algoritmo. Per esempio, per trovare un nome in una lista puoi controllare ogni nome, oppure (se la lista è ordinata) puoi continuare a dimezzarla.
Entrambi danno la risposta giusta. La differenza è l'efficienza: quanto lavoro e quanta memoria servono. Un buon programmatore sceglie l'algoritmo che resta veloce anche quando i dati diventano tanti.
Confrontare gli algoritmi in base al tempo
Misurare con il cronometro non è giusto: un computer veloce fa sembrare buono un algoritmo lento. Perciò contiamo i passi di base (confronti, scambi, somme) in funzione della dimensione dell'input n.
Caso migliore, medio e peggiore
Il caso migliore è l'input più fortunato (il 13 è nella prima scatola: 1 passo). Il caso peggiore è il più sfortunato (il 13 non c'è: n passi). Di solito si indica il caso peggiore, perché è una garanzia: l'algoritmo non sarà mai più lento di così.
Complessità temporale e complessità spaziale
La complessità temporale dice come cresce il numero di passi con n. La complessità spaziale dice come cresce la memoria aggiuntiva con n. Il merge sort è veloce ma richiede memoria in più; il bubble sort quasi non ne richiede ma è lento.
La notazione Big O
La Big O descrive la velocità di crescita, ignorando i dettagli piccoli. Teniamo solo il termine più grande e togliamo i numeri costanti: 3n² + 5n + 2 diventa O(n²), perché per n grande la parte n² è quasi tutto.
| Big O | Nome | n = 16 | n = 1000 | Esempio |
|---|---|---|---|---|
| O(1) | costante | 1 | 1 | leggere l'elemento 5 di un array |
| O(log n) | logaritmica | 4 | circa 10 | ricerca binaria |
| O(n) | lineare | 16 | 1000 | ricerca lineare, trovare il massimo |
| O(n log n) | n log n | 64 | circa 10.000 | merge sort |
| O(n²) | quadratica | 256 | 1.000.000 | bubble sort, cicli annidati |
Regola rapida per il codice: un ciclo su n elementi è O(n); un ciclo dentro un ciclo è O(n²); dimezzare il problema a ogni passo è O(log n).
Efficienza della ricerca lineare e binaria
La ricerca lineare controlla gli elementi uno per uno. Caso peggiore: n confronti, quindi O(n). Funziona su qualsiasi lista, ordinata o no.
La ricerca binaria richiede una lista ordinata. Guardi l'elemento di mezzo; se è troppo grande, scarti la metà destra, altrimenti la sinistra. Ogni passo dimezza la lista, quindi il caso peggiore è circa log₂ n + 1 confronti: O(log n). Per 1.000.000 di elementi sono circa 20 passi invece di 1.000.000.
Efficienza degli algoritmi di ordinamento
Bubble sort, insertion sort e selection sort usano un ciclo dentro un ciclo, quindi fanno circa n²/2 confronti: O(n²). L'insertion sort è O(n) nel caso migliore (una lista già ordinata).
Il merge sort dimezza la lista circa log₂ n volte e a ogni livello fa circa n lavoro: O(n log n). Richiede O(n) di memoria aggiuntiva.
La ricerca binaria richiede una lista ordinata. Se cerchi una sola volta, ordinare prima (n log n) costa più di una ricerca lineare (n). Se cerchi molte volte, ordinare una volta sola conviene.
Precondizioni, postcondizioni e trappole della ricorsione
Una precondizione è ciò che deve essere vero prima che l'algoritmo parta (ricerca binaria: la lista è ordinata). Una postcondizione è ciò che è garantito alla fine (ordinamento: ogni elemento è minore o uguale al successivo). Scriverle aiuta a testare e a dimostrare un algoritmo.
La ricorsione significa che una funzione richiama se stessa su un problema più piccolo. Errori comuni:
- Nessun caso base, o un caso base che non viene mai raggiunto: le chiamate non si fermano mai (stack overflow).
- Il problema non diventa più piccolo a ogni chiamata.
- Ripetere lo stesso lavoro: un semplice Fibonacci ricorsivo richiama fib(3) più e più volte, quindi cresce come O(2ⁿ). Memorizzare le risposte (memoizzazione) lo rende O(n).
- Una ricorsione molto profonda usa molta memoria, un frame dello stack per ogni chiamata.
Provalo: gara tra due ricerche
Scrivi i numeri da 1 a 32 su foglietti di carta e mettili in ordine a faccia in giù. Chiedi a un amico di scegliere un numero segreto. Prima cerca uno per uno e conta i foglietti che giri. Poi cerca girando sempre il foglietto di mezzo. Ripeti 5 volte. Quale metodo non ha mai richiesto più di 6 mosse? Controlla con il cursore nell'ultimo passo 3D (n = 32: log₂ 32 = 5).
Formule e definizioni chiave
- Ricerca lineare: caso peggiore n confronti → O(n)
- Ricerca binaria: caso peggiore circa log₂ n + 1 confronti → O(log n)
- Bubble / insertion / selection sort: circa n(n − 1)/2 confronti → O(n²)
- Merge sort: circa n log₂ n confronti → O(n log n)
- Regola della Big O: tieni il termine più grande, togli le costanti (5n² + 3n → O(n²))
- Raddoppiando n: O(1) uguale, O(log n) +1, O(n) ×2, O(n²) ×4
Esempi svolti
1. Una lista ha 50 nomi. Quanti confronti servono alla ricerca lineare nel caso migliore e nel peggiore?
Caso migliore: il nome è il primo → 1 confronto. Caso peggiore: il nome è l'ultimo o manca → 50 confronti. La ricerca lineare è O(n).
2. Qual è il massimo numero di confronti della ricerca binaria su una lista ordinata di 1024 elementi?
Ogni passo dimezza la lista: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Sono 10 dimezzamenti, più l'ultimo controllo: al massimo 11 confronti (log₂ 1024 = 10).
3. Trova la Big O di f(n) = 4n² + 10n + 7.
Tieni il termine più grande (4n²) e togli la costante 4: O(n²).
4. Un ciclo fa variare i da 1 a n, e dentro di esso un altro ciclo fa variare j da 1 a n. Quante volte viene eseguita l'istruzione interna?
n volte per ciascuno degli n valori di i: n × n = n². Complessità temporale O(n²).
5. Un programma O(n²) ordina 1000 elementi in 2 secondi. Circa quanto tempo serve per 3000 elementi?
n diventa 3 volte più grande, quindi n² diventa 3² = 9 volte più grande: circa 2 × 9 = 18 secondi.
6. Confronta bubble sort e merge sort per n = 1000 elementi.
Bubble sort: circa n²/2 = 500.000 confronti. Merge sort: circa n log₂ n = 1000 × 10 = 10.000. Il merge sort fa circa 50 volte meno lavoro, ma richiede memoria in più.
Errori comuni
- Misurare la velocità solo con il cronometro su un computer. Conta invece i passi in funzione di n.
- Usare la ricerca binaria su una lista non ordinata. La sua precondizione è una lista ordinata.
- Tenere le costanti nella Big O, come scrivere O(2n). È semplicemente O(n).
- Scrivere una funzione ricorsiva senza caso base, o che non rende il problema più piccolo.