Problema nel confronto di numeri
Buongiorno a tutti
Sul mio libro di analisi c'è scritto che se ho in insieme finito $A={x_1, x_2, ... x_n}$ il numero di confronti che devo fare tra i sui elementi per determinare il minimo ed il massimo di tale insieme è 2(n-1). Però mi sembra strano perchè se ho un insieme A con 2 soli elementi allora dovrei fare 2(2-1)=2 confronti ma mi sembra che basti un confronto solo per detrminare quale sia il minimo e il massimo. E per tre elementi dovrei fare 4 confronti, ma non so come a questo punto contarli. E' forse sbagliata sul libro la formula 2(n-1) ?
Grazie anticipatamente a tutti.
Sul mio libro di analisi c'è scritto che se ho in insieme finito $A={x_1, x_2, ... x_n}$ il numero di confronti che devo fare tra i sui elementi per determinare il minimo ed il massimo di tale insieme è 2(n-1). Però mi sembra strano perchè se ho un insieme A con 2 soli elementi allora dovrei fare 2(2-1)=2 confronti ma mi sembra che basti un confronto solo per detrminare quale sia il minimo e il massimo. E per tre elementi dovrei fare 4 confronti, ma non so come a questo punto contarli. E' forse sbagliata sul libro la formula 2(n-1) ?
Grazie anticipatamente a tutti.
Risposte
Ti dico la prima cosa che mi viene in mente. La formula è corretta perchè per trovare il minimo fai così (il massimo è analogo):
parti dal primo elemento e lo confronti con il secondo. Dei due prendi il più piccolo e lo confronti con il terzo. Dei due prendi il più piccolo e lo confronti con il quarto e così via. Non torni mai indietro quindi consideri ogni elemento 1 sola volta andando sempre in avanti. Quindi è evidente che hai fatto n-1 confronti.
Se fai la stessa cosa per il massimo ottieni 2(n-1) confronti. Non possono essere di meno perchè hai bisogno di considerare almeno una volta ognuno degli n elementi cioè appunto di n-1 confronti.
Nel caso di 2 elementi in realtà basta un confronto solo per il semplice motivo che serve un confronto per il massimo ed uno per il minimo, ma uno implica l'altro.
Cioè se trovi che x1 è il minimo di {x1,x2} è evidente che sai già che x2 è il massimo.
Quindi a voler essere pignoli quella formula vale per insiemi con almeno 3 elementi mentre per 2 elementi basta un confronto solo.
Spero di essere stato chiaro.
parti dal primo elemento e lo confronti con il secondo. Dei due prendi il più piccolo e lo confronti con il terzo. Dei due prendi il più piccolo e lo confronti con il quarto e così via. Non torni mai indietro quindi consideri ogni elemento 1 sola volta andando sempre in avanti. Quindi è evidente che hai fatto n-1 confronti.
Se fai la stessa cosa per il massimo ottieni 2(n-1) confronti. Non possono essere di meno perchè hai bisogno di considerare almeno una volta ognuno degli n elementi cioè appunto di n-1 confronti.
Nel caso di 2 elementi in realtà basta un confronto solo per il semplice motivo che serve un confronto per il massimo ed uno per il minimo, ma uno implica l'altro.
Cioè se trovi che x1 è il minimo di {x1,x2} è evidente che sai già che x2 è il massimo.
Quindi a voler essere pignoli quella formula vale per insiemi con almeno 3 elementi mentre per 2 elementi basta un confronto solo.
Spero di essere stato chiaro.
"terubozu":
E' forse sbagliata sul libro la formula 2(n-1) ?
Dimostriamola per induzione a partire da $n=3$. Se $n=3$ allora servono due confronti per il minimo e due per il massimo e $4=2(3-1)$.
Supponiamo la tesi vera per $n >= 3$ e dimostriamola per $n+1$. Sia $A$ insieme con $n+1$ elementi. Scegliamone $n$ e determiniamo massimo e minimo tra questi in $2(n-1)$ mosse. Ci occorrono altre due mosse per confrontare i valori trovati con l'unico elemento escluso. Ora $2(n-1)+2=2n$, finito.
Dimenticavo! Assumo $A subset RR$ finito, dove $A$ è l'insieme del primo topic.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo