Complessità Computazionale: differenze tra le versioni
Da Bioingegneria Elettronica e Informatica.
(Creata pagina con "'''Vitoantonio Bevilacqua''' [mailto:vitoantonio.bevilacqua@poliba.it vitoantonio.bevilacqua@poliba.it] '''Antonio Brunetti''' [mailto:antonio.brunetti@poliba.it antonio.bru...") |
|||
| Riga 19: | Riga 19: | ||
* n-1 incrementi (worst case) | * n-1 incrementi (worst case) | ||
| − | 6 + n + n -1 | + | '''6 + n + n -1''' |
| − | + | Costo unitario per ogni confronto: | |
| − | n+1 confronti (fra i e n) nel ciclo for | + | * n+1 confronti (fra i e n) nel ciclo for |
| − | n confronti if (a[i]<n) | + | * n confronti if (a[i]<n) |
| − | n+ 1 + n | + | '''n + 1 + n''' |
| + | <br /><br /> | ||
| − | TOT f(n) = 4n+6 | + | '''TOT f(n) = 4n+6''' |
4n <= 4n per n >=0 | 4n <= 4n per n >=0 | ||
| + | |||
6 <= 6n per n >=1 | 6 <= 6n per n >=1 | ||
| + | <br /> | ||
| + | <br /> | ||
per ogni n>=1 f(n) = 4n+6 <= 10n | per ogni n>=1 f(n) = 4n+6 <= 10n | ||
| + | |||
ovvero per C = 10 e K = 1 f(n) <= Cn per ogni n>=K | ovvero per C = 10 e K = 1 f(n) <= Cn per ogni n>=K | ||
quindi f(n) è O(n) | quindi f(n) è O(n) | ||
Versione delle 18:47, 20 mag 2018
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)
