Skip to main content

Complessità degli algoritmi

Come possiamo confrontare gli algoritmi in base al tempo che impiegano ?​

Contiamo il numero di istruzioni eseguite.

Questo comporta che la complessità dipende da quanto è grande il problema.

Esempio: Se stiamo ordinando un array da 100 elementi, è chiaro che ci vorrà meno tempo rispetto ad un array di 1 milione di elementi.

E' quindi necessario definire la dimensione di un problema.

Cos'è quindi la complessità ?​

E' una funzione che va dai numeri naturali ai numeri reali negativi.

Vediamo un esempio di codice​

SEARCH(A, x)
    FOR(i = 0; i <= LENGTH(A); i++)
        IF(A[i] == x)
            RETURN TRUE;
    RETURN FALSE;

Come possiamo contare il numero di istruzioni ?​

Ad esempio, quante volte viene eseguito il return true ?

Minimo zero, al massimo una volta.

Possiamo quindi dire che il caso migliore è "minimo zero", mentre il caso pessimo è "massimo 1 volta".

E' difficile definire in tempo, quanto questo algoritmo può impiegare, perchè l'algoritmo potrebbe trovare un elemento immediatamente, o alla fine, o a metà, avere dei ritardi hardware ecc.

Possiamo quindi dire che la complessità non dipende solamente dalla dimensione, ma anche da come è composto il problema.

Il caso pessimo è il limite massimo in termini di tempo, ovvero il numero massimo di istruzioni che l'algoritmo può eseguire a prescindere dall'input.

Quali sono quindi i casi peggiori e migliori ?​

Nel caso migliore, il numero di istruzioni eseguite è costante, ovvero che non dipende dalla dimensione del problema.

Nel caso peggiore, il numero di istruzioni eseguite è <=c∗n<= c * n dove cc è una costante e nn è il numero degli elementi nell'array.

Ma ha senso tenere in considerazione la costante moltiplicativa a fronte di un numero n ?​

Nel caso di dimostrazioni si, ma alla finalità di calcolare la complessità di un problema, no.

Vediamo un secondo esempio, con il prodotto tra 2 matrici​

Sia X il numero di iterazioni da fare all'interno di K

MULT(A, B)
    FOR i <- 1 TO ROWS(A)
        FOR j <- 1 TO COLS(B)
            C_ij <- 0
            FOR k <- 1 TO COLS(A) (COSTO 2)
                C_ij <- C_ij + a_ik * b_kj (COSTO 3)
    RET C

All'interno del ciclo di K, eseguo (3 + 2)x + 3 in maniera indicativa.