[VARI] complessità di tempo

[otrebor86]

Ciao ragazzi
vi posto questo codice che il prof ha spiegato

sum=0;         //1
for i=1 to N   //3(N+1)
     for j=i to N   // ....
          sum=sum+1  //...
return sum   //....

Ora ragionando sulla seconda riga di codice
3 = (assegnazione,verfica,incremento)
N = il numero delle iterazioni
+1 = da dove cavolo esce?????????????????????

grazie mille per l'aiuto
ciaoo

[robs05]

Il ciclo for esegue n iterazioni più +1 che sarebbe il confronto della variabile i nel test del for che ovviamente risulterà falso e si esce dal for..

se provi ad eseguire un for con un debugger

es for (int i = 0; i < 3; i++)

i = 0 test ok incrementa entra ne for
i = 1 test ok incrementa entra ne for
i = 2 test ok incrementa entra ne for
i = 3 test no incrementa ma esci

quindi N+1 --> 3+1 operazioni