Costo computazionale e complessità asintotica
Come stimare il costo prima di misurarlo
Dato un problema computazionale, esistono quasi sempre molti algoritmi diversi che lo risolvono correttamente. Come stabiliamo quale algoritmo è più efficiente?
Misurare i secondi con un cronometro eseguendo il programma su un computer specifico è un metodo scientifico inadeguato, perché il tempo in secondi dipende dalla velocità della CPU, dalla quantità di RAM, dal sistema operativo e dalle ottimizzazioni del compilatore. L’analisi della complessità computazionale valuta invece l’efficienza intrinseca di un algoritmo in modo matematico e indipendente dall’hardware, contando come cresce il numero di operazioni elementari (e la memoria occupata) al crescere della dimensione dell’input .
Complessità in Tempo e in Spazio
Fissata la dimensione dell’input (es. il numero di elementi di un array, il numero di vertici di un grafo o il numero di bit di un intero), definiamo:
- Complessità Temporale : Il numero di operazioni elementari (assegnamenti, confronti, operazioni aritmetiche, accessi a
v[i], ciascuna assunta di costo costante nel modello RAM — Random Access Machine) eseguite dall’algoritmo su un input di taglia . - Complessità Spaziale : La quantità di celle di memoria aggiuntive (oltre all’input stesso) richieste dall’algoritmo in funzione di , comprendendo:
- variabili locali e strutture dati allocate dinamicamente nello Heap;
- i record di attivazione sullo Stack delle chiamate in caso di funzioni ricorsive (pari alla profondità massima dell’albero di ricorsione!).
Caso Migliore, Caso Peggiore e Caso Medio
A parità di dimensione , un algoritmo può compiere più o meno passi a seconda della configurazione dei dati (es. cercare un elemento x in un array v di elementi con la ricerca lineare):
- Caso Migliore : Il minimo numero di operazioni su tutti gli input di taglia (es. nella ricerca lineare,
xsi trova subito inv[0]solo confronto, ). - Caso Peggiore : Il massimo numero di operazioni su tutti gli input di taglia (es.
xè nell’ultima cellav[n-1]o non è presente confronti, ). È la misura più usata in informatica, perché fornisce una garanzia assoluta: l’algoritmo non impiegherà mai più di ! - Caso Medio : Il valore atteso del numero di operazioni mediato sulla distribuzione di probabilità di tutti gli input di taglia (es. se
xha uguale probabilità di trovarsi in ciascuna posizione, in media servono confronti).
Notazioni Asintotiche Formali: , ,
Quando diventa molto grande (), le costanti moltiplicative e i termini di grado inferiore diventano trascurabili: un algoritmo con costo batterà sempre, per sufficientemente grande, un algoritmo con costo .
L’analisi asintotica cattura l’ordine di grandezza del tasso di crescita di una funzione confrontandola con una funzione modello :
1. Notazione O-grande: — Limite Superiore Asintotico ()
Si dice che è di ordine O-grande di , e si scrive , se esistono una costante reale positiva e una soglia tali che:
- Significato intuitivo: A partire da in poi, non cresce più velocemente di (a meno di una costante moltiplicativa ). È un tetto superiore.
- Esempio: perché per ogni vale (basta scegliere ). (Nota: essendo un limite superiore, è formalmente vero anche che , ma si cerca sempre il limite superiore più stretto possibile!).
2. Notazione Omega-grande: — Limite Inferiore Asintotico ()
Si dice che è Omega-grande di , e si scrive , se esistono due costanti e tali che:
- Significato intuitivo: cresce almeno veloce quanto . È un pavimento inferiore.
3. Notazione Theta-grande: — Ordine di Grandezza Esatto ()
Si dice che è Theta-grande di , e si scrive , se è contemporaneamente e , ovvero esistono tre costanti e tali che:
- Significato intuitivo: e hanno esattamente lo stesso tasso di crescita asintotico (racchiudono “a sandwich” dall’alto e dal basso). Ogni polinomio di grado , con , appartiene a .
Gerarchia delle classi di complessità
Le principali classi di complessità, ordinate dalla più efficiente alla più lenta per , formano una gerarchia rigorosa:
flowchart LR C1["<b>O(1)</b><br/>Costante<br/>Accesso array <code>v[i]</code>"] CLOG["<b>O(log n)</b><br/>Logaritmica<br/>Ricerca Binaria"] CN["<b>O(n)</b><br/>Lineare<br/>Scansione array"] CNLOG["<b>O(n log n)</b><br/>Linearitmica<br/>MergeSort / QuickSort"] CN2["<b>O(n²)</b><br/>Quadratica<br/>Bubble / Insertion Sort"] C2N["<b>O(2ⁿ) / O(n!)</b><br/>Esponenziale / Fattoriale<br/>Fibonacci ingenuo / Hanoi"] C1 --> CLOG --> CN --> CNLOG --> CN2 --> C2N
Impatto pratico dei tempi di calcolo al crescere di
Supponendo un calcolatore capace di eseguire (un miliardo) di operazioni elementari al secondo ():
| Classe | Nome | (1 milione) | Algoritmo tipico | ||
|---|---|---|---|---|---|
| Costante | Accesso a v[i], push su Pila | ||||
| Logaritmica | Ricerca Binaria su array ordinato | ||||
| Lineare | Ricerca lineare, massimo di un array | ||||
| Linearitmica | Merge Sort, Heap Sort | ||||
| Quadratica | Bubble Sort, Selection Sort, Insertion Sort | ||||
| Cubica | Prodotto standard tra matrici | ||||
| Esponenziale | Incalcolabile | Sottoinsiemi di un insieme, Torri di Hanoi |
Cambiamento di base dei logaritmi
Nella notazione asintotica la base del logaritmo non conta (), perché per la formula del cambiamento di base , e il fattore è solo una costante moltiplicativa!
Regole pratiche per calcolare la complessità di codice C
-
Istruzioni elementari: assegnamenti, aritmetica, accesso a
v[i],returncostano . -
Sequenza di blocchi
A; B;: vale la regola della somma (massimo): -
Condizionale
if (cond) A else B: nel caso peggiore: -
Cicli con limiti indipendenti: si moltiplica il numero di iterazioni per il costo del corpo. Due cicli
forannidati da0ancostano . -
Cicli annidati con indice interno DIPENDENTE dall’esterno (Serie di Gauss):
for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { /* operazione O(1) */ } }Per il ciclo interno fa passo, per ne fa , …, per ne fa . Sommando tutti i passi otteniamo la Progressione Aritmetica di Gauss:
-
Cicli con raddoppio o dimezzamento dell’indice (
i = i * 2oppurei = i / 2):for (int i = 1; i < n; i = i * 2) { /* operazione O(1) */ }L’indice assume i valori . Il ciclo termina quando . Dunque il numero di iterazioni è !
Equazioni di ricorrenza fondamentali per funzioni ricorsive
Per una funzione ricorsiva, si esprime tramite un’equazione di ricorrenza:
| Schema della funzione ricorsiva | Equazione di ricorrenza | Soluzione asintotica | Esempio |
|---|---|---|---|
| Riduce con lavoro | Fattoriale, Somma ricorsiva | ||
| Riduce con lavoro | Selection Sort ricorsivo | ||
| Dimezza (1 chiamata) con lavoro | Ricerca Binaria, Potenza veloce | ||
| Dimezza (2 chiamate) con lavoro | Visita completa di un albero binario | ||
| Dimezza (2 chiamate) con lavoro | Merge Sort | ||
| Riduce (2 chiamate) con lavoro | Torri di Hanoi |
Profilazione, modello di costo e dimensione dell’input
La profilazione misura un programma concreto con dati, compilatore e macchina specifici. L’analisi sceglie una dimensione dell’ingresso e conta operazioni rappresentative. Per la ricerca lineare su elementi, contando le uguaglianze, troviamo un confronto se la chiave è in testa e confronti se è in fondo o assente. Se la chiave è presente una sola volta e ogni posizione ha probabilità , il valore atteso è . Questa conclusione cambia se modifichiamo la distribuzione delle posizioni o includiamo input in cui la chiave è assente.
Un esperimento può misurare il tempo per e mantenendo uguali distribuzione, compilatore e condizioni di prova. Il modello spiega la crescita attesa, mentre le misure includono costanti, effetti della cache e rumore. Specifichiamo anche se il costo in spazio include l’input o solo la memoria ausiliaria. Per gli ordinamenti concreti vedi ricerca e ordinamento.
Esempi guidati
Esempio 1: Analisi di cicli annidati misti (Lineare Logaritmico)
Problema: Determinare la complessità temporale in funzione di del seguente frammento:
int mistero(int n) {
int s = 0;
/* Blocco A */
for (int i = 0; i < n; i++) {
for (int j = n; j >= 1; j = j / 3) {
s += i + j;
}
}
/* Blocco B */
for (int k = 0; k < n; k++) {
s -= k;
}
return s;
}Analisi passo-passo:
-
Blocco A:
- Il ciclo esterno su
iesegue esattamente iterazioni. - Il ciclo interno su
jparte da e ad ogni passo dividejper (), quindi esegue iterazioni. - Poiché i limiti di
jnon dipendono dai, il costo del Blocco A è il prodotto: .
- Il ciclo esterno su
-
Blocco B: è un ciclo semplice da
0an - 1, quindi costa . -
Totale (Regola della somma):
Esempio 2: Risoluzione di una ricorrenza per srotolamento (Unrolling)
Problema: Scrivere e risolvere l’equazione di ricorrenza per il tempo e lo spazio sullo Stack della seguente funzione:
int elabora_ric(const int v[], int n) {
if (n <= 1) return 0;
int somma = 0;
for (int i = 0; i < n; i++) {
somma += v[i];
}
return somma + elabora_ric(v, n / 2);
}Analisi passo-passo:
-
Impostazione della ricorrenza:
-
Per , il caso base costa .
-
Per , la funzione esegue un ciclo
fordi passi () e poi effettua una sola chiamata ricorsiva su dimensione :
-
-
Srotolamento (Unrolling):
Poiché la serie geometrica converge a una costante, abbiamo , da cui:
-
Complessità Spaziale :
Ad ogni chiamata viene dimezzato (), quindi ci sono al massimo chiamate attive contemporaneamente sullo Stack: .
Esempio 3: La trappola di strlen(s) nella condizione del ciclo for
Problema: Confrontare la complessità di queste due versioni della scansione di una stringa di lunghezza :
/* Versione 1 (LENTA!) */
for (size_t i = 0; i < strlen(s); i++) {
putchar(s[i]);
}
/* Versione 2 (VELOCE!) */
size_t n = strlen(s);
for (size_t i = 0; i < n; i++) {
putchar(s[i]);
}Analisi:
La funzione strlen(s) non conosce a priori la lunghezza della stringa: deve scorrerla tutta dal primo carattere fino a '\0', impiegando tempo ad ogni singola chiamata!
- Nella Versione 1, la guardia
i < strlen(s)viene rivalutata ad ogni iterazione del ciclo ( volte), costando (quadratica)! - Nella Versione 2,
strlen(s)viene chiamata una sola volta prima del ciclo () e poi il ciclo fa passi da : costo totale (lineare)!
Errori frequenti
Errori da evitare
- Confondere con “Caso Peggiore” e con “Caso Migliore”:
È un equivoco diffuso! , e sono notazioni matematiche sulle funzioni, mentre Caso Peggiore () e Caso Migliore () sono proprietà dell’input. Possono essere combinate liberamente: ad esempio, nella ricerca lineare il caso migliore è e il caso peggiore è .- Assumere che ogni chiamata di funzione dentro un ciclo costi :
Se dentro un ciclofordi iterazioni invochiamoricerca_lineare(v, n, x)(che costa ), il ciclo non costa ma ! Bisogna sempre moltiplicare per la complessità della funzione chiamata.- Dimenticare lo spazio dello Stack nelle funzioni ricorsive:
Una funzione ricorsiva che non chiamamallocnon ha costo spaziale (a meno di Tail Call Optimization): ogni livello di ricorsione aperto occupa uno Stack Frame in memoria, quindi è almeno pari alla profondità massima di ricorsione.
Esercizi di prova
Esercizio 1. Confronto di ordini di grandezza asintotici (Base)
Ordina le seguenti funzioni di costo dalla asintoticamente più piccola (più veloce) alla più grande per , indicando se alcune appartengono alla stessa classe :
Soluzione
Trascurando le costanti moltiplicative e i termini di ordine inferiore:
- e anche (perché domina su ) e hanno lo stesso ordine di grandezza !
Ordine finale: .
Esercizio 2. Dimostrazione formale con la definizione di (Base)
Dimostra usando la definizione formale ( per ) che .
Soluzione
Dobbiamo trovare e tali che per ogni :
- Limite inferiore (): Poiché per il termine , vale sempre . Basta scegliere .
- Limite superiore (): Per ogni vale , dunque . Sommando otteniamo . Basta scegliere .
Con la doppia disuguaglianza è soddisfatta per ogni , quindi .
Esercizio 3. Analisi di un doppio ciclo con passo geometrico (Intermedio)
Determina la complessità temporale in funzione di del seguente frammento C:
int conta = 0;
for (int i = 1; i <= n; i = i * 2) {
for (int j = 0; j < n; j++) {
conta++;
}
}Soluzione
Il ciclo esterno parte da
i = 1e raddoppiaiad ogni passo (i = 1, 2, 4, 8, ..., 2^k <= n), quindi viene eseguito esattamente volte.Ad ogni iterazione del ciclo esterno, il ciclo interno su
jscorre da0an - 1, eseguendo esattamente passi.Poiché il numero di iterazioni del ciclo interno è indipendente da
i, il costo totale è il prodotto:
Esercizio 4. Analisi sottile: quando un ciclo interno da 1 a i con passo raddoppiato costa ! (Intermedio)
Determina la complessità temporale di questo frammento (attenzione a come varia il limite del ciclo interno!):
int s = 0;
for (int i = 1; i <= n; i = i * 2) {
for (int j = 0; j < i; j++) {
s++;
}
}Soluzione
Qui il limite superiore del ciclo interno è
i(nonn!), doveiassume solo le potenze di 2: con (cioè ).
Sommiamo il numero esatto di volte in cui viene eseguitos++al variare di :Poiché , abbiamo .
Sorpresa: la somma delle potenze di 2 fino a è inferiore a , quindi la complessità complessiva non è , bensì (lineare)!
Esercizio 5. Caso migliore e caso peggiore con uscita anticipata (Avanzato)
Determina la complessità nel caso migliore e nel caso peggiore della seguente funzione che verifica se un array contiene elementi duplicati:
int ha_duplicati(const int v[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (v[i] == v[j]) {
return 1; /* Uscita anticipata! */
}
}
}
return 0;
}Soluzione
Caso Migliore : Si verifica quando i primi due elementi dell’array sono già uguali (
v[0] == v[1]). Alla prima iterazione () il test dell’ifè subito vero e la funzione termina conreturn 1;dopo 1 solo confronto:Caso Peggiore : Si verifica quando tutti gli elementi dell’array sono distinti (oppure l’unico duplicato sono gli ultimi due elementi
v[n-2] == v[n-1]). La funzione deve confrontare tutte le coppie con :
Esercizio 6. Analisi di funzione ricorsiva con ramificazione binaria (Avanzato)
Determina la complessità temporale e la complessità spaziale sullo Stack della seguente funzione ricorsiva:
int f(int n) {
if (n <= 1) return 1;
return f(n / 2) + f(n / 2);
}Come cambierebbe la complessità temporale se sostituissimo l’ultima riga con int m = f(n / 2); return m + m;?
Soluzione
Versione originale
return f(n / 2) + f(n / 2);:
Tempo : Ad ogni livello la funzione effettua 2 chiamate ricorsive distinte di taglia più una somma , quindi:
L’albero di ricorsione ha altezza e ad ogni livello il numero di chiamate raddoppia (). Il numero totale di nodi dell’albero è .
Spazio sullo Stack : Poiché la seconda chiamata
f(n / 2)inizia solo dopo che la prima ha terminato e liberato i propri frame dallo Stack, il numero massimo di chiamate attive contemporaneamente è pari all’altezza dell’albero:Versione ottimizzata
int m = f(n / 2); return m + m;:
Ora viene effettuata una sola chiamata ricorsiva per livello: la ricorrenza diventa , abbattendo la complessità temporale da a !
Provenienza del materiale
- Dispensa ufficiale del corso:
C1PROG1U5L5_Costo_Computazionale.pdf(Unità 5, Lezione 5 — Costo computazionale). - Marco Anisetti, Astrazione,
Appunti_di_Fine_Unità_5.pdf, cap. 4.