Simo F
25-06-2008, 17:03
Sto studiando per l'esame di Algoritmi e Strutture Dati..ma non riesco a capire come viene calcolata la complessità di un algoritmo.. il mio libro porta come esempio questo:
int calcola_fatt(int n)
{
int fat,i;
for(fat=1,i=2 ; i<=n ; i++)
fat *= i;
return fat;
}
che ha complessità:
T(n)=1+(n-1)*(1+1+1)+1=3n-1=O(n) ..
Non riesco a capire bene da dove viene il -1, cioè il for cicla n volte perciò mi verrebbe da pensare che O(n) sia 3n.. dove sbaglio??
int calcola_fatt(int n)
{
int fat,i;
for(fat=1,i=2 ; i<=n ; i++)
fat *= i;
return fat;
}
che ha complessità:
T(n)=1+(n-1)*(1+1+1)+1=3n-1=O(n) ..
Non riesco a capire bene da dove viene il -1, cioè il for cicla n volte perciò mi verrebbe da pensare che O(n) sia 3n.. dove sbaglio??