Elenet.net
+2 voti
Qual'è il numero minimo e il numero massimo di passi di questo algoritmo?
correlata alla risposta per: Ordinamento di un vettore
quesito posto 9 Marzo 2013 in Classe terza da Emanuele Rizzo Esperto (238 punti)
modificato 12 Marzo 2013 da Gianni Messina
  

1 Risposta

+1 voto

Il numero di passi minimo è N-1, il numero di passi massimo è N fattoriale.

risposta inviata 9 Marzo 2013 da Salvatore Firriolo Corsista (131 punti)
Sono d'accordo sul numero minimo.
Sul numero massimo invece considerando che ad ogni visita dell'array si decrementa di un elemento (caso peggiore) ma tale numero va sommato al numero delle visite fatte nel passaggio precedente allora in totale avrei:

(n-1)+(n-2)+(n-3) + .. + 1  

che non corrisponde a n!  

Che ne dite?
778 domande
1,565 risposte
639 commenti
1,445 utenti