OliForum Matematico

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.

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

Hai mostrato un algoritmo che soddisfa quella proprietà ma non è affatto una dimostrazione che ogni algoritmo per quel problema deve avere quella proprietà.
Ad ogni modo si scrive "qual è", non "qual'è" (è un errore grave).

Saluti

Ok, scusa tanto, penserò allora alla dimostrazione. E scusate anche per il "qual'è", ogni tanto scrivendo veloce si può anche sbagliare, la prossima volta sarò più preciso nelle mie risposte.