Ciao a tutti, c'è qualcuno che sa spiegarmi il tempo di esecuzione del seguente pseudocodice?
Si tratta di un array A. k è la posizione nell'array!
for i = 1 to k do { mini = i; for j = i+1 to lenght[A] do { if A[j] < A [min] then mini = j; ... ... } }
i cicli for innestati hanno un tempo di n*n ? anche i cicli che dipendono dal ciclio precedente?
Grazie,
Enrico
Ciao Enrico.
On 2007-02-28 17:10, Enrico Zanardo wrote:
for i = 1 to k do
Passerai questo ciclo k volte.
for j = i+1 to lenght[A] do
E questo ciclo al massimo length[A] volte. Il numero esatto dipende dal ciclo esterno, ma di solito interessa solo l'ordine di tempo( e/o memoria) e non il valore esatto (cioé, per essere esatto OMEGA(length[A]) per questo ciclo).
Tutto sommato, si arriva a OMEGA( k * length[A] ).
i cicli for innestati hanno un tempo di n*n ?
n? Cos'è n?
Saluti, Benjamin
Ciao Enrico,
On 2/28/07, Enrico Zanardo info@etaweb.it wrote:
Ciao a tutti, c'è qualcuno che sa spiegarmi il tempo di esecuzione del seguente pseudocodice?
Andando a memoria, sul "Rivest-Leiserson-Cormen" si trova l'analisi di complessità di questo tipo di pseudo codice e/o come ricavarlo, anche se devo dire che i suggerimenti di Chris e Benjamin sono altrettanto esplicativi.
Stefano PS Chris, scusa se ho "riaperto" il thread! :-)
-
Benjamin Gufler -
Enrico Zanardo -
Steevie