Quale sarebbe il numero più piccolo e più grande di confronti in una matrice non ordinata che potrebbe avere anche elementi duplicati?Ricerca in una matrice non ordinata
Capisco che trovare qualcosa in un array non ordinato è un problema di O (n). Ma è vero se l'array contiene anche elementi duplicati?
Per elementi duplicati intendo, elementi che si verificano più di una volta nell'array specificato.
Come regola generale, quando parliamo di complessità asintotica che ignora costanti come O (n), non importa se si ha il doppio del lavoro, il triplo del lavoro ecc. Quindi il problema che è O (n) rimane O (n) in tale scenario.
In questo particolare problema, disporre di duplicati in un array non ordinato non velocizza il processo di ricerca di un elemento. Ovviamente, se l'elemento è 10 volte nell'array, probabilmente lo si troverà 10 volte più velocemente (in media), ma fintanto che questo non dipende da n, non cambia la complessità.
Quindi l'idea qui è che devi camminare l'array da un capo all'altro perché non è ordinato. Ciò significa che stai guardando O (n) - una traversata lineare degli elementi. Indipendentemente dal fatto che quello che stai cercando è in posizione 0, posizione 8 o posizione n-1, devi percorrere l'array per trovarlo.
Ora, se ci sono possibilmente duplicati nell'array, l'unica differenza è che è possibile trovare più di un'istanza del valore. Se stai cercando tutti loro o solo il primo, è ancora una situazione O (n). I duplicati non cambiano la complessità.
Caso migliore: lo trovate (supponendo che sia necessario trovarne uno solo) al primo confronto.
Caso peggiore: non ci sono duplicati per il valore dato ed è l'ultimo che si controlla - l'ennesimo confronto.
Se dovessi trovare TUTTI i duplicati, saranno sempre i confronti, perché devi visitare ogni elemento nella matrice non ordinata.
Il tempo O(n) è vero anche se sono presenti elementi duplicati. Dovresti familiarizzare con big-oh notation.
Nel peggiore dei casi, considerare questo array: 1, 1, 1, 1, ..., 1, 1, 2. La ricerca di 2 richiederà esattamente il confronto n se si parte dal primo elemento, quindi non è possibile avere duplicati. Se doveste cercare 1, lo troveremmo in un unico confronto, ma ci sono input di elementi distinti per i quali potete anche trovare un elemento in un singolo confronto se siete fortunati, quindi avere i duplicati in realtà non lo fa significa molto, tranne che è più probabile che tu abbia fortuna e trovi il tuo obiettivo in meno passaggi. Rimarrà comunque O(n).
Ci sono quasi sempre casi migliori e casi peggiori. Le prestazioni pratiche della maggior parte degli algoritmi dipendono sempre dall'input dato, big-oh notation ti dà solo una vaga idea di come l'algoritmo si esibirà. Questo non vuol dire che la notazione asintotica sia inutile, solo che non è sempre del tutto accurata perché ci sono costanti sottostanti coinvolte che fanno la differenza nella pratica.
In caso di dubbi sulle prestazioni, eseguire i propri punti di riferimento.
quello che sarebbe il più piccolo e il più grande numero di confronti in un array non ordinato che potrebbe avere elementi duplicati così?
Se si sta cercando un singolo valore specificato, il numero più piccolo e più grande di comparazioni sarà 1 e n, rispettivamente. Se il valore è noto nell'array e stai solo cercando la sua posizione, puoi fare a meno delle comparazioni n-1.
Capisco che trovare qualcosa in un array non ordinato è un problema O (n). Ma è vero se l'array contiene anche gli elementi duplicati?
Sì, è ancora O (n).
Supponiamo che la presenza di duplicati significhi che, in media, la ricerca del tempo viene dimezzata. Bene, questa è una grande riduzione, ma non influisce sul tempo O (n). Big-O non è un caso medio, è il caso peggiore, e il caso peggiore non cambia. E la divisione di n per un fattore costante non influisce comunque sul tempo di big-O.
Sei sicuro che "Big-O non è un caso medio, è il caso peggiore"? Da quello che so Big-O non è affatto un caso. – Lazer
@Lazer - Sì. Big-O è usato per indicare un limite superiore asintotico su una funzione (all'interno di un fattore costante). Se fosse un indicatore di caso medio o migliore, allora non potrebbe essere un limite superiore. –
Per come la vedo non ci dovrebbero essere paragoni 2n
for (int i=0; i<n; i++)
if (a[i]==ele)
break
else
continue;
Quindi ci sono due confronti (i<n) e (a[i]==ele) fatto N volte nel caso peggiore. Pertanto 2n confronti. Se esiste un modo per ridurre i<n, non so come.
Come tutti gli altri sono d'accordo per un array non ordinato che non contiene duplicati, la ricerca lineare esaustiva sarà O (n).
Se sono consentiti i duplicati, l'algoritmo rimane O (n) solo nel presupposto che la probabilità che ogni elemento sia duplicato è distribuita uniformemente.
Se esiste una funzione di densità di probabilità diversa che descrive la distribuzione di elementi duplicati, l'algoritmo di ricerca sarà probabilmente inferiore a O (n) a seconda della funzione di densità di probabilità.
Il numero di confronti dipende da ciò che stai cercando. È un elemento particolare? Il primo elemento che è un duplicato? La versione completa dell'array? – Pops
Benvenuti in SO! Consentitemi di darvi il primo upvote per usare l'etichetta dei compiti a casa e scrivere una domanda chiara e comprensibile (otteniamo una sfortunata quantità di _plzsendtehcodez_). – Pops