Teoria dell'Informazione: miglior algoritmo per max e min

[CUCU]

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.

[xxalenicxx]

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

[CUCU]

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

[xxalenicxx]

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.