Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

[Algoritmi] Calcolo del numero di operazioni

03/05/2019, 16: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.

Re: [Algoritmi] Calcolo del numero di operazioni

03/05/2019, 16: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.

Re: [Algoritmi] Calcolo del numero di operazioni

03/05/2019, 18: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.

Re: [Algoritmi] Calcolo del numero di operazioni

04/05/2019, 11: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.

Re: [Algoritmi] Calcolo del numero di operazioni

04/05/2019, 12: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?

Re: [Algoritmi] Calcolo del numero di operazioni

04/05/2019, 16: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.
Rispondi al messaggio