1. Il Dualismo delle Risorse Informatiche
Quando si progetta un algoritmo, l'ottimizzazione non riguarda un unico fattore. La valutazione delle prestazioni si divide in due metriche principali che spesso entrano in conflitto tra loro:
- Complessità Temporale ($Time Complexity$): Misura il numero di operazioni elementari eseguite dall'algoritmo al variare della dimensione $n$ dei dati di input.
- Complessità Spaziale ($Space Complexity$): Misura la quantità di memoria RAM aggiuntiva richiesta dall'algoritmo durante la sua esecuzione (oltre allo spazio occupato dai dati di input originari).
2. Il Principio del Trade-off (Spazio vs Tempo)
In molti contesti informatici avanzati, esiste un compromesso inevitabile noto come Time-Space Trade-off: è possibile velocizzare l'esecuzione di un programma sacrificando memoria (ad esempio memorizzando in cache risultati pregressi, come nella programmazione dinamica o nella memoization), oppure si può risparmiare memoria eseguendo calcoli ripetuti ogni volta che servono, allungando però i tempi d'attesa.
| Strategia Algoritmica | Complessità Temporale | Complessità Spaziale | Note di Efficienza |
|---|---|---|---|
| Ricerca Lineare Base | $O(n)$ | $O(1)$ | Minimo consumo di memoria, ma lenta su dataset enormi. |
| Ricerca Binaria (Vettore Ordinato) | $O(\log n)$ | $O(1)$ | Molto rapida, richiede che i dati siano preventivamente ordinati. |
| Memoizzazione (Fibonacci) | $O(n)$ | $O(n)$ | Riduce drasticamente il tempo rispetto a $O(2^n)$ usando memoria extra per salvare gli stati. |
- Spazio Fisso: Variabili globali, costanti e codice macchina compilato (indipendenti da $n$).
- Spazio Variabile: Strutture dati dinamiche (vettori, matrici), oggetti allocati e profondità dello stack di chiamata nei cicli ricorsivi ($O(\log n)$ o $O(n)$).
3. Simulatore Interattivo: Valutatore di Bilanciamento Risorse
Confronta l'impatto combinato di tempo e spazio stimato per differenti classi di algoritmi in base alla dimensione dell'input.