[Algoritmi] Calcolo del numero di operazioni

[EveyH]

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.

[vict85]

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

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.

[apatriarca]

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.

[EveyH]

"vict85":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

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]

"apatriarca":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?

[vict85]

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.