In breve: La complessità misura quante risorse usa un algoritmo. Serve a capire se un programma è veloce o lento.
Cos'è la complessità
Un algoritmo è una serie di passi per risolvere un problema. Lo stesso problema può avere algoritmi diversi.
Alcuni algoritmi sono veloci, altri lenti. La complessità ci dice quanto tempo o memoria servono per finire il lavoro.
Studiamo la complessità per scegliere la soluzione migliore. Non basta che il programma funzioni: deve funzionare bene anche con tanti dati.
Come si misura
La complessità si misura contando le operazioni che l'algoritmo esegue. Conta soprattutto come crescono queste operazioni quando aumentano i dati in ingresso.
Usiamo la notazione O grande per descrivere questa crescita. Per esempio, scriviamo O(n), O(n²) oppure O(log n).
La lettera n indica la quantità di dati. Se n raddoppia, vogliamo sapere se il tempo raddoppia, quadruplica o cresce ancora di più.
Esistono due tipi di complessità importanti. La complessità temporale riguarda il tempo di esecuzione. La complessità spaziale riguarda la memoria usata.
Esempi pratici
Immagina di cercare un nome in una rubrica disordinata. Devi leggere ogni pagina, una per una. Questo è un algoritmo con complessità O(n): più nomi ci sono, più tempo serve.
Ora pensa a una rubrica ordinata in ordine alfabetico. Puoi aprire a metà e capire da che parte cercare. Questa ricerca ha complessità O(log n), molto più veloce.
Un esempio di O(n²) è confrontare ogni studente di una classe con tutti gli altri. Se la classe ha 20 alunni, fai 400 confronti. Se ne ha 100, fai 10.000 confronti.
Si parla anche di caso peggiore, caso medio e caso migliore. Di solito il caso peggiore è quello più importante da studiare.
Parole difficili
- Algoritmo: sequenza ordinata di passi che risolve un problema in modo preciso.
- Notazione O grande: simbolo che descrive come crescono le operazioni al crescere dei dati.
- Complessità temporale: misura del tempo che un algoritmo impiega per finire.
- Complessità spaziale: misura della memoria che un algoritmo occupa durante l'esecuzione.
- Caso peggiore: situazione in cui l'algoritmo impiega il numero massimo di operazioni.
- Logaritmo: operazione matematica che cresce molto lentamente al crescere del numero.
Riferimenti
- Norma: Riordino degli istituti tecnici
- Obiettivo formativo coperto: ob.tecnico-informatica-telecomunicazioni.informatica.cl3.complessita-algoritmica.01