tempi esucuzione codice

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 :wink:
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.

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
  

Ho provato e il mio problema è che un ciclo dipende dall'altro, quindi
secondo me è dovrebbe essere così ma non ne sono sicuro

for i = 1 to k do (k + 1) volte
   a = x k volte
   for j = i+1 to length[A] do sommatoria da (j=2) a (k+1) di (lenght[A]-j+1)volte
      b = y sommatoria da (j=2) a (k+1) di (lenght[A]-j+1)volte
   done
done

Giusto?

enrico