Prestazioni e complessità

Efficienza di un algoritmo e prestazioni

Il problema del migliorare le prestazioni di un sistema è un problema centrale per l’informatica, ed è l’ambito nel quale si concentra la maggior parte degli sforzi e degli investimenti dell’industria dei computer. La capacità di costruire macchine dalle prestazioni sempre migliori non solo ha costituito e costituisce il grosso dell’attività industriale in questo senso, con l’introduzione di nuove tecnologie e tecniche di produzione, ma il suo scopo non è solamente avere programmi più veloci ma quello di attivare funzioni che sono possibili solo grazie al miglioramento delle prestazioni. Mano a mano che nella storia dell’informatica sono migliorate le prestazioni si sono rese possibili attività altrimenti prima impossibili:

• manipolare enormi quantità di dati oltre le capacità umane;
• svolgere più operazioni in contemporanea;
• manipolare sorgenti dati multimediali;
• una sola rete globale in grado di gestire miliardi di pacchetti dati al secondo;
• Robotica e computer vision;
• videogiochi e realtà virtuale;
• dispositivi mobili ed insossabili;
• intelligenza artificiale.

sono solo alcune delle applicazioni più evidenti rese possibili, oggi parte della nostra quotidianità e che sono rese possibili non solo da algoritmi sofisticati (che magari esistevano anche prima molto prima delle applicazioni pratiche) ma soprattutto da macchine in grado di eseguirli. Anzi la stessa potenza di calcolo ha reso possibile la realizzazione di linguaggi e sistemi di automazione più semplici da programmare ed utilizzare.

Prestazioni ed efficienza

Ottenere migliori prestazioni significa sicuramente puntare ad un miglioramento dell’hardware, come testimonia la legge di Moore che ha visto per 40 anni il raddoppio delle prestazioni dei sistemi con puntualità matematica ogni 18 mesi e poi ancora successivamente con l’introduzione del calcolo parallelo prima e delle GPU fino alle moderne architetture ARM. Un computer odierno è milioni di volte più potente di una macchina di 50 anni fa, col risultato pratico che uno smartwatch ha più potenza di calcolo del computer che ha portato l’uomo sulla Luna.

Tuttavia il miglioramento hardware è solo una parte del problema, come vedremo in questa lezione il miglioramento delle prestazioni è in realtà prima di tutto un problema di efficienza degli algoritmi. La capacità di risolvere col minor numero di risorse (istruzioni e memoria) un determinato problema ha infatti un peso assai maggiore rispetto alle pur fondamentali migliorie dell’hardware.

Ci sono due modi per misurare l’efficienza di un algoritmo e quindi di confrontare due algoritmi per capire quale è il più efficiente. Uno è mediante una misurazione sintetica, ovvero cronometrando il tempo di esecuzione su un set di dati. Tuttavia questo tipo di misurazione presenta due diversi problemi:

• dipende dall’hardware utilizzato, dal sistema operativo, dal linguaggio e dal compilatore;
• può non essere fattibile per grandi set di dati, richiedendo tempo e risorse per la sola misura.

L’altro metodo è tramite misurazione analitica, quindi mediante strumenti matematici, per individuare non il tempo di esecuzione effettivo, ma la capacità di dare una classificazione prestazionale ad un algoritmo al variare dei dati a disposizione, ed in modo indipendente dalla macchina su cui verrà eseguito. In altre parole possiamo dare una misura del tempo di esecuzione di un algoritmo con la seguente formula:

Dove k è una costante che rappresenta la macchina di esecuzione, mentre C è la misura analitica della complessità. In altre parole lo stesso programma eseguito su due computer diversi darà prestazioni differenti, ma non per la natura dell’algoritmo, ma solo per le caratteristiche del computer. Per questa ragione analizzeremo le prestazioni tramite misura analitica, senza dipendere da una macchina specifica, senza cronometro, ma solo facendo riferimento all’analisi del codice.

Analisi della complessità di un algoritmo

Ma da cosa dipende C? La complessità è sempre una misura del numero di istruzioni da eseguire per risolvere un determinato problema. Vediamo perché:

• tutte le istruzioni hanno lo stesso tempo di esecuzione (che siano assegnazioni, espressioni, condizioni o salti); questo è in generale sempre vero per le macchine di Von Neumann;
• due algoritmi che eseguono un diverso numero di istruzioni ma una volta soltanto hanno una differenza di complessità trascurabile. In altri termini due programmi, uno di 100 righe ed uno di 1000 righe hanno la stessa complessità, in quanto la velocità del computer è tale da rendere trascurabile la loro differenza di tempo di esecuzione.
• è la quantità di dati trattati che invece aumenta la complessità. Se un programma richiede N dati bisogna eseguire un numero costante di istruzioni N volte, allora la complessità dipenderà esclusivamente da N.

Ad esempio:

for (int i=0; i<N; i++) {
  cout << i << endl;
}

E’ evidente che il numero di istruzioni eseguite sarà proporzionale al numero di cicli, cioè da N. Questa grandezza viene chiamata complessità computazionale, e viene utilizzata per misurarla la notazione O grande.

Notazione O grande

La notazione O-grande (O(f(n))) descrive il comportamento dell’algoritmo nel peggiore dei casi (“worst-case”), dove

• n = dimensione dell’input.
• f(n) = funzione che rappresenta il costo in funzione di n.

Qui di eseguito le principali classi di complessità:

Vediamole singolarmente.

O(1) — Tempo Costante

Significa: il tempo di esecuzione non dipende dalla dimensione dell’input.

#include <iostream>
using namespace std;

int getFirstElement(int arr[]) {
    return arr[0]; // Sempre un solo accesso, indipendentemente da n
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50};
    cout << getFirstElement(numbers) << endl;
    return 0;
}

O(log n) — Tempo Logaritmico

Esempio: Ricerca Binaria su un array ordinato.

int ricercaBinaria(int arr[], int dimensione, int valoreDaTrovare) {
    int inizio = 0;
    int fine = dimensione - 1;

    while (inizio <= fine) {
        int medio = (inizio + fine) / 2;

        if (arr[medio] == valoreDaTrovare)
            return medio; // Trovato

        if (arr[medio] < valoreDaTrovare)
            inizio = medio + 1; // Cerca a destra
        else
            fine = medio - 1; // Cerca a sinistra
    }

    return -1; // Non trovato
}

O(n) — Tempo Lineare

Esempio: ricerca sequenziale.

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

O(n log n) — Tempo Lineare-Logaritmico

Esempio: Merge Sort (algoritmo di ordinamento).

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

O(n²) — Tempo Quadratico

Esempio: Bubble Sort (algoritmo di ordinamento lento).

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
        }
    }
}

O(2ⁿ) — Tempo Esponenziale

Esempio: Decifrazione di una password (attacco BruteForce)

#include <stdio.h>
#include <string.h>

#define MAX_LUNGHEZZA 4
#define CHAR_SET "abcdefghijklmnopqrstuvwxyz"
#define LUNGHEZZA_CHAR_SET 26

// Funzione ricorsiva per generare tutte le combinazioni
int forzaBruta(char* tentativo, const char* password, int posizione, int lunghezzaMassima) {
    if (posizione == lunghezzaMassima) {
        tentativo[posizione] = '\0'; // termina la stringa
        if (strcmp(tentativo, password) == 0) {
            cout << "Password trovata: " << tentativo << endl;
            return 1;
        }
        return 0;
    }

    for (int i = 0; i < LUNGHEZZA_CHAR_SET; i++) {
        tentativo[posizione] = CHAR_SET[i];
        if (forzaBruta(tentativo, password, posizione + 1, lunghezzaMassima)) {
            return 1;
        }
    }

    return 0;
}

Si tratta di un tempo esponenziale perché per ogni lettera della password dobbiamo tentare tutte le possibili combinazioni, che crescono esponenzialmente al valore di N (la lunghezza della password).

Qui un confronto.

Esercizio:

• confrontare mergeSort e Bubble Sort con lo stesso set di dati (generare un array di 10000 elementi) e confrontare col cronometro i tempi di esecuzione.
• spiegare perché il calcolo della serie di n numeri di Fibonacci in modo ricorsivo è esponenziale. Provare a proporre una soluzione ricorsiva non esponenziale.