EFFICIENZA ALGORITMI

[nepero87]

Salve!

Ho iniziato questo mese il corso di strutture dati, e da subito ci è stato insegnato a ottimizzare ogni programma in C che svolgiamo, minimizzando prima di tutto il tempo di esecuzione, poi lo spazio occupato in memoria.

Bene, in una slide in cui si calcola i passi di un algoritmo c'è scritto:

sum=0; [1 passo]
for (i=1;i for (j=i;j sum=sum+1; [$sum_{i=1}^N (N+1-i)$ passi]
return sum; [$1$ passo]

Si calcolano i passi (unità di tempo necessari alla compilazione di un algoritmo. Ma ci sono diversi punti oscuri.. Perchè mai il primo for ha $2*N$ passi, perchè il secondo for ne ha $2*sum_{i=1}^N (N+1-i) $, perchè l'argomento della for ha $sum_{i=1}^N (N+1-i)$ istruzioni?
Non riesco a capire come si contano questi passi...

E' un argomento che mi mette un po' in difficoltà...

[nepero87]

Nobody can help me?

[lorven]

Il calcolo dei passi è semplice, se si ha presente come viene eseguito un ciclo enumerativo di tipo FOR, il quale comporta, ad ogni "giro", la verifica della condizione di uscita e l'incremento dell'ìndice associato.
Pertanto, il FOR esterno esegue N volte il controllo su $i Il ciclo nidificato esegue il controllo $j Considerando che questi $2*(N-i+1)$ passi vanno eseguiti per ogni i compreso tra 1 ed N, si ottiene la sommatoria indicata $sum_{i=1}^N2*(N+i-1)$.
Analogamente per l'istruzione sum=sum+1, che è compresa nel ciclo nidificato: è eseguita $N-i+1$ volte nel ciclo su J, per ogni i compreso tra 1 e N.
Ciao

[nepero87]

Ah ok ti ringrazio...