[C] Complessità

[Fla@sh_b]

Ciao a tutti!
Qualcuno saprebbe dirmi che complessità asintotica ha questo codice?

int F(int N) 
{
    int i, j, a=0;
        
    for(i=0; i<N; i++) {

        j=1;

        while(j<N) {
            
            a++;
            j+=j;
        }

        i=i+1;
    }
    return a;
}

Per quanto mi riguarda ho fatto il seguente ragionamento:

1. il ciclo while viene eseguito N/2 volte quindi ha una complessità O(N/2);

2. anche il ciclo for viene eseguito N/2 volte quindi ha una complessità O(N/2);

3. complessita della funzione f(): O(N/2 * N/2) = O(N^2/4) ~ O(N^2)

E' giusto?

Help me!!!

[marco_c]

secondo me il while non lo esegue N/2 volte ma log_in_base_2_di_N volte.
visto che fai j+=j lo raddoppi di volta in volta, quindi tutte le potenze di 2...

[marco_c]

quindi la complessità è NlogN

[Fla@sh_b]

Ciao marco_c ! Ti ringrazio per la risposta...forse è la volta buona che capisco per bene come calcolare la complessità di una funzione!
Il procedimento che segue è valido?

Posto k il numero di iterazioni del quale voglio stabilire una stima della complessità in funzione di n 
potrei sfruttare qualcosa del genere:

::: CICLO WHILE :::
 
k=1 --- prima iterazione  --- j=2
k=2 --- sec. iterazione   --- j=4 
k=3 --- terza iterazione  --- j=8
k=4 --- quarta iterazione --- j=16
k   --- ultima iterazione --- j=2^k;

Alla k-esima iterazione j=2^k=n; -> 2^k=n -> k=log_base2_n!

::: CICLO FOR :::

k=1 --- prima iterazione  --- j=2
k=2 --- sec. iterazione   --- j=4 
k=3 --- terza iterazione  --- j=6
k=4 --- quarta iterazione --- j=8
k   --- ultima iterazione --- j=2*k;

Alla k-esima iterazione j=2*k=n; -> 2*k=n -> k=n/2!

::: COMPLESSITA DI F() :::

O(log_base2_n * n/2) = O(nlog_base2_n)

Che ne pensate? E' corretto?

[Ponza]

ma che caaavolo sono ste complessità? numeri complessi? stime asintotiche? io conosco queste ...ma all'informatica nn so cosa c'entrino

[marco_c]

Originariamente inviato da Fla@sh_b
Ciao marco_c ! Ti ringrazio per la risposta...forse è la volta buona che capisco per bene come calcolare la complessità di una funzione!
Il procedimento che segue è valido?

Posto k il numero di iterazioni del quale voglio stabilire una stima della complessità in funzione di n 
potrei sfruttare qualcosa del genere:

::: CICLO WHILE :::
 
k=1 --- prima iterazione  --- j=2
k=2 --- sec. iterazione   --- j=4 
k=3 --- terza iterazione  --- j=8
k=4 --- quarta iterazione --- j=16
k   --- ultima iterazione --- j=2^k;

Alla k-esima iterazione j=2^k=n; -> 2^k=n -> k=log_base2_n!

::: CICLO FOR :::

k=1 --- prima iterazione  --- j=2
k=2 --- sec. iterazione   --- j=4 
k=3 --- terza iterazione  --- j=6
k=4 --- quarta iterazione --- j=8
k   --- ultima iterazione --- j=2*k;

Alla k-esima iterazione j=2*k=n; -> 2*k=n -> k=n/2!

::: COMPLESSITA DI F() :::

O(log_base2_n * n/2) = O(nlog_base2_n)

Che ne pensate? E' corretto?

direi perfetto!
ciao

[Fla@sh_b]

Ciao marco_c...ti chiedo un'ultima cosa (PLZ) !

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...

::: 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?

[anx721]

il ciclo esterno viene eseguito n volte; per ogni valore di 'i', il ciclo interno è eseguito i volte, ed i varia tra 1 e n quindi il numero totale di volte che esegui il ciclo interno è pari alla somma:

1 + 2 + 3 + 4 +....+ n

ovvero è la sommatoria dei primi n numeri che vale O(n^2). Infatti puoi scrivere:

1 + 2 + 3 + ... + n =

(1 + 2 + 3 + ....+ n + 1 + 2 + 3 + ... + n) / 2 =

( (1 + n) + (2 + (n-1) + (3 + (n-2)) + ... + (n + 1)) / 2 =

n*(n+1)/2

[Fla@sh_b]

Ma...

Posto n=5 e k il numero di volte che viene eseguito il ciclo for interno...

i :  1  2  4 
k :  0  1  3

Quindi il ciclo interno viene in tutto eseguito 4 volte.
Non 1+2+...+n quindi (sbaglio ) ?

Inoltre dove ho trovato quest'esercizio si suggeriva di utilizzare una tabella con il passo di iterazione e il valore del contatore.
Tipo quella che ho postato poco più sopra...

::: 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;

...

Ed è proprio nel fare questa tabella che mi blocco (vedi mio precedente post)!

Help Me!!!

[anx721]

Scusa, non avevo visto che all'interno del secondo ciclo incrementi anchela variabile i; la complessita è allora lineare O(n) perchè comunque quando il ciclo interno è stato eseguito n volte i sarà maggiore di n per cui il ciclo esterno non è piu eseguito; se poi vuoi calcolcarti il numero preciso di iterazioni fatti lo schemino, ma comuqnue quello che importa nella complessità è calcolare la complessita asintotica piu che il numero preciso di iterazioni, e questa la puo spesso calcolare con osservazioni tipo quella che ho fatto in questo post.