Pagina 194 e successive del libro di testo
Vogliamo individuare dei criteri oggettivi da usare per scegliere l’algoritmo con prestazioni migliori tra tutti quelli che risolvono lo stesso problema
- complessità in tempo
- complessità in spazio
- complessità dell’input
- complessità dell’output
- complessità di trasmissione.
Nell’ipotesi che i criteri già discussi (piuttosto soggettivi) siano sempre applicati, se ritenuti utili, passiamo al consumo di risorse hardware.
Ci occupiamo del consumo atteso di risorse hardware generiche ma sempre presenti: CPU, RAM, memoria di massa.
Velocità e dimensione
La velocità di esecuzione di un programma è condizionata dalle diverse velocità di accesso e diverse capacità dei dispositivi di memorizzazione
| Velocità effettive | Capacità | |
|---|---|---|
| CPU | ~ 2 GHz | ~ KB |
| Cache | ~ 1 GHz (GB/s) | ~ MB |
| RAM | ~ 0.5 GHz (GB/s) | ~ GB |
| HD | ~ 0,25 GHz (GB/s) | ~ TB |
A dimensioni inferiori del codice e dei dati corrispondono
- minor tempo di accesso
- minor tempo d’esecuzione.
Il consumo di memoria (codice e dati) durante l’esecuzione porta a definire il criterio di complessità in spazio mentre quello di occupazione della CPU viene definito come complessità in tempo.
Ulteriori criteri che prendono in considerazione le risorse necessarie sono
- complessità dell’input (se la dimensione dell’input è dominante…)
- complessità dell’output (se la dimensione dell’output è dominante…)
- complessità di trasmissione (se il tempo di trasmissione dei dati e/o del codice diventa dominante…)
Tra le risorse hardware ci occupiamo principalmente della CPU e quindi della complessità in tempo.
Pagina 195 del libro di testo
Per ogni problema la complessità in tempo e la complessità in spazio sono collegate tra loro
In pratica, per un certo problema posso scegliere un algoritmo/programma che utilizza
- codice molto lungo
- piccole quantità di dati
- codice molto corto
- grandi quantità di dati.
Arrivati a un certo punto… una riduzione della complessità in tempo porta a un aumento della complessità in spazio e viceversa.
Esiste una complessità del problema sotto la quale non si può scendere.
Esempi
Calcolare il seno di un certo angolo
- Il codice calcola il valore della funzione seno, con un metodo di approssimazione, a seconda del valore dell’angolo.
- Codice lungo e lento.
- Il consumo di spazio per i dati è basso.
- Il codice consulta una tabella che contiene i valori già calcolati, della funzione seno,.
- Codice corto e veloce.
- Il consumo di spazio per i dati è alto.
Analogamente per elaborare
- numeri irrazionali, trascendenti (coprocessore matematico)
- note, suoni degli strumenti (scheda audio)
- geometrie (scheda video)
Per valutare la complessità in tempo è necessario analizzare le singole istruzioni del programma (dell’algoritmo…).