PDA

Visualizza la versione completa : [C] ComplessitÓ


Fla@sh_b
02-02-2005, 17:15
Ciao a tutti! :fighet:
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? :confused:

Help me!!! :dh˛:

marco_c
02-02-2005, 17:19
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
02-02-2005, 17:20
quindi la complessitÓ Ŕ NlogN

Fla@sh_b
02-02-2005, 18:54
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? :confused:

Ponza
02-02-2005, 22:11
ma che caaavolo sono ste complessitÓ? numeri complessi? stime asintotiche? io conosco queste ...ma all'informatica nn so cosa c'entrino :)

marco_c
03-02-2005, 09:02
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? :confused:



direi perfetto!
ciao

Fla@sh_b
03-02-2005, 20:21
Ciao marco_c...ti chiedo un'ultima cosa (PLZ) :D !




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

anx721
03-02-2005, 20:35
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
03-02-2005, 21:33
:ciauz:

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

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!!! :dh˛:

anx721
03-02-2005, 21:43
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.

Loading