In breve: Per uno stesso problema esistono più algoritmi. Impariamo a confrontarli per scegliere il migliore.
Cosa significa confrontare algoritmi
Un algoritmo è una sequenza di passi che risolve un problema. Per lo stesso problema possiamo scrivere algoritmi diversi.
Pensa a come raggiungere la scuola. Puoi andare a piedi, in bici o in autobus. Ogni scelta porta allo stesso risultato.
Cambia però il tempo impiegato. Cambia anche la fatica richiesta. Con gli algoritmi succede la stessa cosa.
Come si confrontano gli algoritmi
Confrontiamo gli algoritmi guardando alcune caratteristiche misurabili. La prima è il tempo di esecuzione, cioè quanti passi servono per finire.
La seconda è lo spazio in memoria usato durante il calcolo. La terza è la leggibilità del codice scritto.
Un buon algoritmo usa poche risorse e resta chiaro. Spesso bisogna trovare un equilibrio tra queste qualità.
Per misurare il tempo si conta il numero di operazioni. Si osserva poi come cresce questo numero al crescere dei dati.
Esempi pratici
Vediamo il problema di cercare un nome in un elenco. Il primo algoritmo è la ricerca sequenziale, che controlla un elemento alla volta.
Il secondo è la ricerca binaria, che funziona solo su elenchi ordinati. Divide a metà l'elenco a ogni passo.
Su mille nomi la ricerca sequenziale può fare mille controlli. La ricerca binaria ne fa circa dieci. Il risultato è lo stesso, ma il lavoro è molto diverso.
Un altro esempio è ordinare una lista di numeri. Possiamo usare algoritmi come Bubble Sort o Insertion Sort. Producono lo stesso elenco ordinato, ma con velocità diverse.
Per confrontare in pratica scriviamo entrambi gli algoritmi. Poi li proviamo sugli stessi dati di ingresso. Infine confrontiamo i tempi e i passi eseguiti.
Parole difficili
- Algoritmo: sequenza ordinata di passi che risolve un problema.
- Ricerca sequenziale: metodo che controlla gli elementi uno dopo l'altro.
- Ricerca binaria: metodo che dimezza ogni volta l'insieme da esaminare.
- Tempo di esecuzione: numero di passi che un algoritmo compie per finire.
- Memoria: spazio usato dal programma per conservare i dati.
- Dati di ingresso: valori che diamo all'algoritmo per farlo lavorare.
Riferimenti
- Norma: Riordino degli istituti tecnici
- Obiettivo formativo coperto: ob.tecnico-informatica-telecomunicazioni.informatica.cl3.analisi-algoritmi.01