Dimostrare che nel caso peggiore il numero minimo di confronti per trovare il massimo ed il minimo di un insieme di n elementi è tetto(3n/2)-2.
Non lasciatevi ingannare dal titolo. Per la dimostrazione non dovrebbero essere necessarie particolari conoscenze di informatica né di teoria dell'informazione.
Teoria dell'Informazione: miglior algoritmo per max e min
- xxalenicxx
- Messaggi: 13
- Iscritto il: 21 ott 2005, 16:31
- Località: Roma
Si può dimostrare così:
Ho una array di n elementi, supponiamo n sia pari:
n = 6:
a1 a2 a3 a4 a5 a6
faccio un confronto a 2 a due tra i termini dell'array, cioè confronto i termini:
[a1,a2] [a3,a4] [a5,a6]
Dopo il confronto so qual'è il più grande o il più piccolo, quindi confronto il più grande dei due con la variabile Max (se è più piccola la aggiorno con il valore più grande), e poi il più piccolo con la variabile Min (se è più grande la aggiorno con il valore più piccolo), quindi in totale ho fatto 3 confronti per n/2 coppie, quindi (3/2)*n confronti. Si può evitare il confronto della prima coppia, facendone solo uno, inizializzando il la variabile Max con il più grande e la Min con il più piccolo, quindi in totale:
(3/2)*n - 3 +1 = (3/2)*n - 2
Se n è dispari inizializzo Max = Min con il primo elemento dell'array, poi inizio a confrontare le coppie però iniziando da secondo elemento, quindi se n = 7:
Max = Min = a1
[a2,a3] [a4,a5] [a6,a7]
e da qui in generale:
tetto((3/2)*n) - 2
Ho una array di n elementi, supponiamo n sia pari:
n = 6:
a1 a2 a3 a4 a5 a6
faccio un confronto a 2 a due tra i termini dell'array, cioè confronto i termini:
[a1,a2] [a3,a4] [a5,a6]
Dopo il confronto so qual'è il più grande o il più piccolo, quindi confronto il più grande dei due con la variabile Max (se è più piccola la aggiorno con il valore più grande), e poi il più piccolo con la variabile Min (se è più grande la aggiorno con il valore più piccolo), quindi in totale ho fatto 3 confronti per n/2 coppie, quindi (3/2)*n confronti. Si può evitare il confronto della prima coppia, facendone solo uno, inizializzando il la variabile Max con il più grande e la Min con il più piccolo, quindi in totale:
(3/2)*n - 3 +1 = (3/2)*n - 2
Se n è dispari inizializzo Max = Min con il primo elemento dell'array, poi inizio a confrontare le coppie però iniziando da secondo elemento, quindi se n = 7:
Max = Min = a1
[a2,a3] [a4,a5] [a6,a7]
e da qui in generale:
tetto((3/2)*n) - 2
- xxalenicxx
- Messaggi: 13
- Iscritto il: 21 ott 2005, 16:31
- Località: Roma