[Algoritmi] Calcolo del numero di operazioni
Inviato: 03/05/2019, 15:18
Parto subito con un esempio.
Sono informazioni tratte dal libro Algoritmi e strutture dati, ed. 2, di Bertossi e Montresor.
C'è un algoritmo molto semplice, il seguente:
"il minimo di un insieme A è l'elemento di A che è minore o uguale ad ogni elemento di A".
Questa ricerca richiede che ogni valore sia confrontato con tutti gli altri, per un totale di n(n-1) confronti, dove n è la dimensione di A.
Viene abbozzato un algoritmo descritto così: si sceglie il primo elemento di A come minimo parziale, copiandolo in una variabile min. Si confronta min con gli elementi compresi fra le posizioni 2 e n; ogni volta che si incontra un elemento minore, si aggiorna il minimo parziale. Al termine, min contiene il minimo dell'insieme.
Più avanti si dice che questo algoritmo richiede n(n-1)/2 confronti.
Ma non è uguale al precedente (descritto solo in linguaggio naturale)?
La domanda che mi pongo è sostanzialmente come fare a capire quanti passaggi fa un algoritmo per arrivare alla soluzione, cioè da dove si ricava quel n(n-1).
Grazie.
Sono informazioni tratte dal libro Algoritmi e strutture dati, ed. 2, di Bertossi e Montresor.
C'è un algoritmo molto semplice, il seguente:
"il minimo di un insieme A è l'elemento di A che è minore o uguale ad ogni elemento di A".
Questa ricerca richiede che ogni valore sia confrontato con tutti gli altri, per un totale di n(n-1) confronti, dove n è la dimensione di A.
Viene abbozzato un algoritmo descritto così: si sceglie il primo elemento di A come minimo parziale, copiandolo in una variabile min. Si confronta min con gli elementi compresi fra le posizioni 2 e n; ogni volta che si incontra un elemento minore, si aggiorna il minimo parziale. Al termine, min contiene il minimo dell'insieme.
Più avanti si dice che questo algoritmo richiede n(n-1)/2 confronti.
Ma non è uguale al precedente (descritto solo in linguaggio naturale)?
La domanda che mi pongo è sostanzialmente come fare a capire quanti passaggi fa un algoritmo per arrivare alla soluzione, cioè da dove si ricava quel n(n-1).
Grazie.