Complessità Computazionale

Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it

Antonio Brunetti antonio.brunetti@poliba.it

Esempio pratico di Valutazione della Complessità O (detta o-grande)

Notazione O-grande

public static int avobeMeanCount(double[] a, double mean)
{
    int n = a.lenght, 
        count = 0;
    for(int i = 0; i < n; i++)
        if (a[i] > mean)
            count++;
 
    return count;
} // metodo abouveMeanCount

Soluzione

Costo unitario per ogni dichiarazione (locale o formale) e/o assegnazione, valore restituito:

• double [] a; -> 1
• double mean; -> 2
• int n = a.lenght; -> 3
• int count = 0; -> 4
• int i=0; -> 5
• return count; -> 6
• n incrementi di i nel ciclo for (da i = 1 a i = n)
• n-1 incrementi (worst case)

6 + n + n -1

Costo unitario per ogni confronto:

• n+1 confronti (fra i e n) nel ciclo for
• n confronti if (a[i]<n)

n + 1 + n

TOT f(n) = 4n+6

4n <= 4n per n >=0

6 <= 6n per n >=1

per ogni n>=1 f(n) = 4n+6 <= 10n

ovvero per C = 10 e K = 1 f(n) <= Cn per ogni n>=K

quindi f(n) è O(n)