Complessità Computazionale
Da Bioingegneria Elettronica e Informatica.
Versione del 20 mag 2018 alle 17:44 di Profbevilacqua (Discussione | contributi)
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)
