Ciao marco_c...ti chiedo un'ultima cosa (PLZ) !
codice:
int F(int n)
{
int b=0;
int i, j;
int a=0;
for(i=1; i<=n; i++) {
a=i;
for(j=1; j<a; j++) {
b++;
i++;
}
}
b=a*b;
return 2*b;
}
Per calcolarne la complessità faccio come al solito.
Posto k il numero di iterazioni del quale voglio stabilire una stima della complessità in funzione di n...
codice:
::: CICLO FOR ESTERNO - for(i=1; i<=n; i++) :::
k=1 --- prima iterazione --- i=2
k=2 --- sec. iterazione --- i=4
k=3 --- terza iterazione --- i=8
k=4 --- quarta iterazione --- i=16
k --- ultima iterazione --- i=2^k;
Alla k-esima iterazione i=2^k=n; -> 2^k=n -> k=log_base2_n!
::: CICLO FOR ANNIDATO - for(j=1; j<a; j++) :::
k=1 --- prima iterazione --- j=2
k=2 --- sec. iterazione --- j=3
k=3 --- terza iterazione --- j=4
k=4 --- quarta iterazione --- j=5
k --- ultima iterazione --- j=k+1;
Alla k-esima iterazione j=k+1=a; -> k+1=a -> k=a-1!
::: COMPLESSITA DI F() :::
O(log_base2_n * ?)
Come faccio a calcolare la complessità del ciclo for interno considerando che dipende dal for esterno a causa
dell'assegnazione a=i?
Ho googlato inutilmente cercando qualche esempio ma niente .
Qualche idea?