1. Che cos'è la Complessità Computazionale?
La complessità computazionale è la branca dell'informatica teorica che studia la quantità di risorse (in termini di tempo di calcolo e di memoria RAM) necessarie per l'esecuzione di un algoritmo. Poiché la velocità di esecuzione dipende dall'hardware della macchina su cui il programma viene eseguito, l'analisi teorica prescinde dai secondi fisici e misura le prestazioni in funzione della dimensione $n$ dei dati in ingresso (input size).
2. La Notazione Asintotica: O-Grande ($O$)
Per descrivere come cresce il costo computazionale al crescere di $n$ (specialmente per valori molto grandi), si utilizza la notazione O-grande ($O$). Essa descrive il limite superiore del comportamento asintotico dell'algoritmo, trascurando le costanti moltiplicatrici e i termini di ordine inferiore.
| Notazione | Nome della Complessità | Esempio Tipico |
|---|---|---|
| $O(1)$ | Costante | Accesso diretto a un elemento di un array tramite indice. |
| $O(\log n)$ | Logaritmica | Ricerca binaria (Binary Search) in un vettore ordinato. |
| $O(n)$ | Lineare | Scansione sequenziale (ricerca lineare) di una lista non ordinata. |
| $O(n \log n)$ | Linearitmica | Algoritmi di ordinamento efficienti (es. Merge Sort, Quick Sort). |
| $O(n^2)$ | Quadratica | Doppi cicli annidati (es. Bubble Sort, Selection Sort). |
| $O(2^n)$ | Esponenziale | Soluzioni ricorsive ingenue (es. calcolo naif della sequenza di Fibonacci). |
- Complessità Temporale ($Time$): Numero di operazioni elementari eseguite in funzione di $n$.
- Complessità Spaziale ($Space$): Quantità di memoria di supporto aggiuntiva richiesta dall'algoritmo durante il calcolo.
3. Simulatore Interattivo: Comparatore di Complessità
Seleziona un ordine di complessità e imposta una dimensione d'input $n$ per stimare il numero teorico di operazioni eseguite dall'algoritmo.