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...") |
|||
| (3 versioni intermedie di uno stesso utente non sono mostrate ) | |||
| Riga 3: | Riga 3: | ||
'''Antonio Brunetti''' [mailto:antonio.brunetti@poliba.it antonio.brunetti@poliba.it] | '''Antonio Brunetti''' [mailto:antonio.brunetti@poliba.it antonio.brunetti@poliba.it] | ||
| − | <span style="color:red;font-weight:bold"> | + | <span style="color:red;font-weight:bold">Esempio pratico di Valutazione della Complessità O (detta o-grande) |
| + | </span> | ||
== Notazione O-grande == | == Notazione O-grande == | ||
| − | + | <syntaxhighlight lang="java"> | |
| + | 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 | ||
| + | </syntaxhighlight> | ||
| + | === Soluzione === | ||
Costo unitario per ogni dichiarazione (locale o formale) e/o assegnazione, valore restituito: | Costo unitario per ogni dichiarazione (locale o formale) e/o assegnazione, valore restituito: | ||
| Riga 19: | Riga 32: | ||
* 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 attuale delle 15:19, 29 mag 2019
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)
