Complessità Computazionale

Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it

Antonio Brunetti antonio.brunetti@poliba.it

Pagina in lavorazione

Notazione O-grande

Codice di riferimento

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)