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:

  1. 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 .
  2. 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, x si trova subito in v[0] solo confronto, ).
  • Caso Peggiore : Il massimo numero di operazioni su tutti gli input di taglia (es. x è nell’ultima cella v[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 x ha 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
CostanteAccesso a v[i], push su Pila
LogaritmicaRicerca Binaria su array ordinato
LineareRicerca lineare, massimo di un array
LinearitmicaMerge Sort, Heap Sort
QuadraticaBubble Sort, Selection Sort, Insertion Sort
CubicaProdotto standard tra matrici
EsponenzialeIncalcolabileSottoinsiemi 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

  1. Istruzioni elementari: assegnamenti, aritmetica, accesso a v[i], return costano .

  2. Sequenza di blocchi A; B;: vale la regola della somma (massimo):

  3. Condizionale if (cond) A else B: nel caso peggiore:

  4. Cicli con limiti indipendenti: si moltiplica il numero di iterazioni per il costo del corpo. Due cicli for annidati da 0 a n costano .

  5. 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:

  6. Cicli con raddoppio o dimezzamento dell’indice (i = i * 2 oppure i = 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 ricorsivaEquazione di ricorrenzaSoluzione asintoticaEsempio
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:

  1. Blocco A:

    • Il ciclo esterno su i esegue esattamente iterazioni.
    • Il ciclo interno su j parte da e ad ogni passo divide j per (), quindi esegue iterazioni.
    • Poiché i limiti di j non dipendono da i, il costo del Blocco A è il prodotto: .
  2. Blocco B: è un ciclo semplice da 0 a n - 1, quindi costa .

  3. 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:

  1. Impostazione della ricorrenza:

    • Per , il caso base costa .

    • Per , la funzione esegue un ciclo for di passi () e poi effettua una sola chiamata ricorsiva su dimensione :

  2. Srotolamento (Unrolling):

    Poiché la serie geometrica converge a una costante, abbiamo , da cui:

  3. 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

  1. 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 è .
  2. Assumere che ogni chiamata di funzione dentro un ciclo costi :
    Se dentro un ciclo for di iterazioni invochiamo ricerca_lineare(v, n, x) (che costa ), il ciclo non costa ma ! Bisogna sempre moltiplicare per la complessità della funzione chiamata.
  3. Dimenticare lo spazio dello Stack nelle funzioni ricorsive:
    Una funzione ricorsiva che non chiama malloc non 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 :

Esercizio 2. Dimostrazione formale con la definizione di (Base)

Dimostra usando la definizione formale ( per ) che .

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++;
    }
}

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++;
    }
}

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;
}

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;?


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.