[Algoritmi] Calcolo del numero di operazioni

Messaggioda EveyH » 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.
EveyH
Junior Member
Junior Member
 
Messaggio: 150 di 313
Iscritto il: 18/01/2015, 15:18

Re: [Algoritmi] Calcolo del numero di operazioni

Messaggioda vict85 » 03/05/2019, 15:42

La proprietà di essere minimo è transitiva, quindi se un elemento è maggiore di almeno un altro non può essere il minimo. Questo vuol dire che l'algoritmo seguente
Codice:
m = A[1]
for i in 2:n {
   m = min( m, A[i] )
}

calcola il minimo in \(\displaystyle (n-1) \) confronti. Nota che la funzione min fa un solo confronto. Non so dove tu ci veda un fattore n/2.
vict85
Moderatore
Moderatore
 
Messaggio: 9640 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Calcolo del numero di operazioni

Messaggioda apatriarca » 03/05/2019, 17:50

Dato un insieme di \(n\) elementi, quante sono le coppie di elementi di tale insieme? Possiamo pensare di scegliere un elemento a caso per il primo elemento della coppia e poi scegliere tra gli \(n-1\) rimanenti per il secondo. Abbiamo così ottenuto le coppie ordinate. Se non ci interessa l'ordine dovremo dividere tale numero per metà.

Ma il secondo algoritmo è lineare e molto diverso dal primo. Se ti dice che il numero di confronti è \(n\,(n-1)/2\) c'è un errore nel tuo libro di testo.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5216 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Calcolo del numero di operazioni

Messaggioda EveyH » 04/05/2019, 10:47

vict85 ha scritto:La proprietà di essere minimo è transitiva, quindi se un elemento è maggiore di almeno un altro non può essere il minimo. Questo vuol dire che l'algoritmo seguente
Codice:
m = A[1]
for i in 2:n {
   m = min( m, A[i] )
}

calcola il minimo in \(\displaystyle (n-1) \) confronti. Nota che la funzione min fa un solo confronto. Non so dove tu ci veda un fattore n/2.


Non sono io che ci vedo un fattore n/2, ho riportato quanto scritto nel libro, che appunto mi confondeva. Se c'è un errore però, non è stato segnalato perché non c'è nemmeno nell'errata corrige uscita successivamente. In ogni caso, a parte questo, mi interessava sapere come arrivare a trovare questo numero di confronti.
Secondo voi cosa bisogna padroneggiare della matematica per superare un esame di algoritmi e strutture dati?
Grazie.
EveyH
Junior Member
Junior Member
 
Messaggio: 151 di 313
Iscritto il: 18/01/2015, 15:18

Re: [Algoritmi] Calcolo del numero di operazioni

Messaggioda EveyH » 04/05/2019, 11:03

apatriarca ha scritto:Dato un insieme di \(n\) elementi, quante sono le coppie di elementi di tale insieme? Possiamo pensare di scegliere un elemento a caso per il primo elemento della coppia e poi scegliere tra gli \(n-1\) rimanenti per il secondo. Abbiamo così ottenuto le coppie ordinate. Se non ci interessa l'ordine dovremo dividere tale numero per metà.

Ma il secondo algoritmo è lineare e molto diverso dal primo. Se ti dice che il numero di confronti è \(n\,(n-1)/2\) c'è un errore nel tuo libro di testo.


A quale secondo algoritmo ti riferisci?
EveyH
Junior Member
Junior Member
 
Messaggio: 152 di 313
Iscritto il: 18/01/2015, 15:18

Re: [Algoritmi] Calcolo del numero di operazioni

Messaggioda vict85 » 04/05/2019, 15:25

L'errore nel libro c'è, quel \(n(n-1)/2\) è al più un limite teorico dell'algoritmo, ovvero qualsiasi algoritmo che faccia più confronti fa sicuramente lo stesso confronto \(2\) o più volte.

Riguardo a numero dei confronti nel mio algoritmo, quante volte viene ripetuto il ciclo? Quanti confronti ci sono per ripetizione del ciclo. Calcolati questi due valori li moltiplichi tra di loro.
vict85
Moderatore
Moderatore
 
Messaggio: 9641 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite