PDA

View Full Version : Calcolo complessità algoritmi:Helllllllp

Xoom83
10-02-2007, 16:06
Qualcuno è in grado di spiegarmi in maniera semplice il calcolo della complessità di un algoritmo in presenza di cicli??!?!

vi prego aiutatemi........
dvd100
10-02-2007, 22:04
(complessità del codice all'interno del ciclo)*(numero di cicli eseguiti)
:D
Xoom83
11-02-2007, 08:37
(complessità del codice all'interno del ciclo)*(numero di cicli eseguiti)
:D

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? :help:
yorkeiser
12-02-2007, 15:26
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)