Calcolo complessità algoritmi:Helllllllp

[Xoom83]

Qualcuno è in grado di spiegarmi in maniera semplice il calcolo della complessità di un algoritmo in presenza di cicli??!?!

vi prego aiutatemi........

[dvd100]

(complessità del codice all'interno del ciclo)*(numero di cicli eseguiti)

[Xoom83]

Originariamente inviato da dvd100

(complessità del codice all'interno del ciclo)*(numero di cicli eseguiti)

uhm fino a questo calcolo ci ero arrivato.

ma se avessi un frammento di codice di questo tipo:

w=1
for(i=1; i<n; i*=3){
for (j=1; j<w; j++)
count++;
w*=2;
}

il ciclo esterno viene eseguito log(n) volte,ma quello interno?

[yorkeiser]

La formula corretta è quella scritta da dvd100.

Nel tuo caso, si tratta di un algoritmo un po' strano: nel caso in cui inizializzi w=1, la complessità è 1, dal momento che esegui il ciclo un'unica volta. Se inizializzi w=2 o a un numero maggiore, hai evidentemente un ciclo infinito, quindi di complessità infinita. La complessità del ciclo esterno è invece log3(n), come effettivamente hai scritto. Nel caso di cicli innestati, la complessità totale è data dal prodotto delle due complessità. Indi per cui, nel tuo caso hai un algoritmo di complessità:

log3(n)*1=log3(n)