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; ... ... } }

Mi sa che senza nessun contesto e` difficile rispondere alla tua domanda. Percio` diamo il contesto ;) Vogliamo un'analisi come quella che e` stata fatta qui su un algoritmo simile: http://www.inf.unibz.it/dis/teaching/DSA/dsa02.pdf

i cicli for innestati hanno un tempo di n*n ? anche i cicli che dipendono dal ciclio precedente?

beh, si`! In questo contesto viene richiesto il numero di passaggi cumulativi dall'inizio del pseudocodice.

Ti faccio un esempio:

for i = 1 ... n do (n + 1) volte a = x n volte for j = 1 ... k do n * (k + 1) volte b = y n * k volte done done

Con "cumulativo" intendo dire che il "n per" raffigura per ogni istruzione all'interno del ciclo su i.

Qui, un ciclo 1 ... n viene visto come una cosa che esegui n + 1 volte, perche` ci sono n + 1 confronti da fare, ma il body del ciclo viene eseguito n volte. Questo ovviamente e` un po` una convenzione. Che sia n o n+1 non ti cambia il resultato dell'analisi di complessita`, ovviamente.

Bye, Chris.