[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