1. Definizione Formale della Notazione O-Grande
La notazione O-grande ($O$) è uno strumento matematico utilizzato nell'analisi degli algoritmi per descrivere il limite asintotico superiore di una funzione. Siano $f(n)$ e $g(n)$ due funzioni non negative definite sui numeri interi positivi. Si dice che $f(n) = O(g(n))$ se esistono due costanti positive $c > 0$ e $n_0 > 0$ tali che:
In parole semplici, la notazione indica che, al di là di una certa soglia iniziale $n_0$, la crescita del tempo (o dello spazio) richiesto dall'algoritmo è dominata da un multiplo costante di $g(n)$, ignorando i fattori moltiplicativi costanti e i termini di ordine inferiore.
2. Regole Pratiche di Semplificazione
Quando si analizza il codice sorgente di un algoritmo per determinarne la complessità in O-grande, si applicano alcune regole algebriche fondamentali:
- Eliminazione delle Costanti: Se un blocco richiede $3n^2 + 5$ operazioni, la complessità è $O(n^2)$ (le costanti $3$ e $5$ vengono scartate).
- Dominanza dei Termini: In una somma di funzioni (es. $n^2 + n \log n + 100n$), prevale il termine con crescita maggiore, determinando $O(n^2)$.
- Indipendenza dalla Base dei Logaritmi: Poiché $\log_a n = \frac{\log_b n}{\log_b a}$ e $\frac{1}{\log_b a}$ è una costante, tutte le complessità logaritmiche sono equivalenti e indicate semplicemente come $O(\log n)$.
| Ordine di Crescita | Nome Comune | Valutazione di Efficienza |
|---|---|---|
| $O(1)$ | Costante | Ottimale (indipendente dalla mole di dati). |
| $O(\log n)$ | Logaritmica | Eccellente (es. dimezzamento continuo dei dati). |
| $O(n)$ | Lineare | Buona (tempo proporzionale agli elementi). |
| $O(n \log n)$ | Linearitmica | Standard efficiente per ordinamenti basati su confronti. |
| $O(n^2)$ | Quadratica | Accettabile solo per input ridotti ($n$ piccoli). |
| $O(2^n)$ | Esponenziale | Inattuabile per input di grandi dimensioni. |
3. Simulatore Interattivo: Analizzatore di Crescita Asintotica
Seleziona un'espressione di costo algebrico per calcolare la sua forma semplificata in O-grande e stimare i valori numerici al crescere di $n$.