Pagina 207 del libro di testo
Dato un problema P si possono individuare diversi algoritmi risolutivi A1, A2, … ciascuno con la sua complessità in tempo T1, T2, …
Sia A* l’algoritmo con la complessità minima T*.
A* è un algoritmo ottimo per il problema P.
Se si dimostra che per il problema P non può esistere un algoritmo con complessità in tempo minore di T* allora il problema P ha complessità T*.
La complessità di un problema P è quella del suo algoritmo ottimo…
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.
Esempio
Calcolare il seno di un certo angolo
- Per ogni angolo il codice calcola il valore della funzione seno con un metodo di approssimazione.
- Codice lungo e lento.
- Poco spazio per i dati in memoria.
- Una tabella contiene un certo numero di valori già calcolati della funzione seno, il codice consulta semplicemente la tabella.
- Codice corto e veloce.
- Tanto spazio per i dati in memoria.
Analogamente per elaborare
- numeri irrazionali, trascendenti (processore matematico)
- note, suoni degli strumenti (scheda audio)
- geometrie (scheda video)