Ricerca nella struttura dei dati: spiegazione di diversi metodi di ricerca
Pubblicato: 2021-05-03La rete di comunicazione si sta espandendo e quindi le persone usano Internet! Le aziende stanno passando al digitale per una gestione efficiente. I dati generati su Internet sono in aumento e quindi i set di dati stanno diventando complessi. È essenziale organizzare, gestire, accedere e analizzare i dati in modo accurato ed efficiente, una struttura dati è la tecnica più utile e l'articolo si concentra sullo stesso!
Sommario
Struttura dati
In informatica, le strutture di dati sono la base per i tipi di dati astratti (ADT), dove ADT sono la forma logica del tipo di dati. Il layout fisico del tipo di dati viene implementato utilizzando la struttura dei dati. Diversi tipi di struttura dati vengono utilizzati per diversi tipi di applicazioni; alcuni sono specializzati in compiti particolari.
La struttura dei dati è una raccolta di valori di dati e relazioni tra loro, operazioni e funzioni applicabili ai dati. Aiuta a organizzare, gestire e archiviare i dati in un formato particolare. Pertanto, gli utenti possono avere un facile accesso e modificare i dati in modo efficiente.
Le strutture dati aiutano a gestire grandi quantità di dati, come enormi database. Algoritmi efficienti sono costruiti sulla base di strutture dati efficienti. Oltre all'archiviazione efficiente, le strutture dati sono anche responsabili del recupero efficiente delle informazioni dalla memoria archiviata. Include un array, un elenco collegato, un puntatore, una ricerca, uno stack, un grafico, una coda, una struttura, programmi, ordinamento e così via.
L'articolo copre il concetto di ricerca nella struttura dei dati e i suoi metodi. Due esempi di algoritmi sono spiegati in dettaglio per comprendere chiaramente il concetto. Per acquisire ulteriori conoscenze, abilità e competenze, sono disponibili corsi online sulla struttura dei dati, citati a fine articolo.
Che cos'è la ricerca nella struttura dei dati?
Il processo di ricerca delle informazioni desiderate dall'insieme di elementi archiviati sotto forma di elementi nella memoria del computer è denominato "ricerca nella struttura dei dati". Questi insiemi di elementi sono in varie forme, come un array, un albero, un grafico o un elenco collegato. Un altro modo per definire la ricerca nella struttura dei dati è individuare l'elemento desiderato di caratteristiche specifiche in una raccolta di elementi.
Metodi di ricerca
La ricerca nella struttura dati può essere eseguita implementando algoritmi di ricerca per verificare o recuperare un elemento da qualsiasi forma di struttura dati archiviata. Questi algoritmi sono classificati in base al tipo di operazione di ricerca, ad esempio:
- Ricerca sequenziale
L'array o l'elenco di elementi viene attraversato in sequenza controllando ogni componente dell'insieme.
Ad esempio, Ricerca lineare.
- Ricerca a intervalli
Gli algoritmi progettati in modo esplicito per la ricerca in strutture di dati ordinate sono inclusi nella ricerca a intervalli. L'efficienza di questi algoritmi è di gran lunga migliore degli algoritmi di ricerca lineare.
Ad esempio, Ricerca binaria, Ricerca logaritmica.
Questi metodi vengono esaminati in base al tempo impiegato da un algoritmo per cercare un elemento corrispondente all'elemento di ricerca nelle raccolte dati e sono dati da,
- Il miglior tempo possibile
- Il tempo medio
- Il momento peggiore
Le preoccupazioni principali riguardano i tempi peggiori che portano a previsioni garantite delle prestazioni dell'algoritmo e sono anche facili da calcolare rispetto ai tempi medi.
Per illustrare esempi e concetti in questo articolo, vengono considerati "n" elementi nella raccolta dati in qualsiasi formato di dati. Le operazioni dominanti vengono utilizzate per semplificare l'analisi e il confronto degli algoritmi. Per la ricerca in una struttura di dati, un confronto è un'operazione dominante, che è indicata da O() e pronunciata come "big-Oh" o "Oh".
Esistono numerosi algoritmi di ricerca in una struttura di dati come ricerca lineare, ricerca binaria, ricerca per interpolazione, ricerca per salto, ricerca esponenziale, ricerca Fibonacci, ricerca per sottoliste, ricerca binaria onnipresente, ricerca binaria illimitata, funzione ricorsiva per ricerca per sottostringa e programma ricorsivo per cercare un elemento in modo lineare nella matrice data. L'articolo è limitato agli algoritmi di ricerca lineare e binaria e ai loro principi di funzionamento.
Diamo un'occhiata dettagliata alla ricerca lineare e alla ricerca binaria nella struttura dei dati.
Ricerca lineare
L'algoritmo di ricerca lineare ricerca tutti gli elementi nell'array in sequenza. Il suo miglior tempo di esecuzione è uno, mentre il peggior tempo di esecuzione è n, dove n è il numero totale di elementi nell'array di ricerca.
È l'algoritmo di ricerca più semplice nella struttura dei dati e controlla ogni elemento nell'insieme di elementi finché non corrisponde all'elemento di ricerca fino alla fine della raccolta dei dati. Quando i dati non sono ordinati, è preferibile un algoritmo di ricerca lineare.
La ricerca lineare presenta alcune complessità come indicato di seguito:
- Complessità spaziale
La complessità dello spazio per la ricerca lineare è O(n) in quanto non utilizza spazio aggiuntivo dove n è il numero di elementi in un array.
- Complessità temporale
*Complessità del caso migliore = O(1) si verifica quando l'elemento di ricerca è presente nel primo elemento nell'array di ricerca.
*La complessità del caso peggiore = O(n) si verifica quando l'elemento di ricerca non è presente nell'insieme di elementi o nell'array.
*Complessità media = O(n) si riferisce a quando l'elemento è presente da qualche parte nell'array di ricerca.
Esempio,
Prendiamo una matrice di elementi come indicato di seguito:
45, 78, 12, 67, 08, 51, 39, 26
Per trovare '51' in una matrice di 8 elementi sopra indicati, un algoritmo di ricerca lineare controllerà ogni elemento in sequenza fino a quando il suo puntatore punta a 51 nello spazio di memoria. Ci vuole tempo O(6) per trovare 51 in un array. Per trovare 12, nell'array sopra, ci vuole O(3), mentre, per 26, richiede O(8) tempo.
Ricerca binaria
Questo algoritmo trova elementi specifici confrontando gli elementi più centrali nella raccolta dati. Quando si verifica una corrispondenza, restituisce l'indice dell'elemento. Quando l'elemento centrale è maggiore dell'elemento, cerca un elemento centrale del sottoarray sinistro. Al contrario, se l'elemento centrale è più piccolo dell'elemento di ricerca, esplora il centro dell'elemento nel sottoarray destro. Continua a cercare un elemento finché non lo trova o finché la dimensione dei sottoarray non diventa zero.
La ricerca binaria richiede un ordine ordinato degli elementi. È più veloce di un algoritmo di ricerca lineare. Funziona secondo il principio del divide et impera.
Complessità runtime = O(log n)
L'algoritmo di ricerca binaria presenta complessità come indicato di seguito:
- Complessità nel caso peggiore = O (n log n)
- Complessità media = O (n log n)
- Complessità del caso migliore = O (1)
Esempio,
Prendiamo un algoritmo ordinato di 08 elementi:
08, 12, 26, 39, 45, 51, 67, 78
Per trovare 51 in una matrice degli elementi di cui sopra,
L'algoritmo dividerà un array in due array, 08, 12, 26, 39 e 45, 51, 67, 78
Poiché 51 è maggiore di 39, inizierà a cercare gli elementi sul lato destro dell'array.
Dividerà ulteriormente il in due come 45, 51 e 67, 78
Poiché 51 è minore di 67, inizierà la ricerca a sinistra di quel sottoarray.
Quel sottoarray è nuovamente diviso in due come 45 e 51.
Poiché 51 è il numero corrispondente all'elemento di ricerca, restituirà il numero di indice di quell'elemento nell'array.
Si concluderà che l'elemento di ricerca 51 si trova nella sesta posizione in una matrice.
La ricerca binaria riduce il tempo della metà poiché il conteggio del confronto viene ridotto in modo significativo rispetto all'algoritmo di ricerca lineare.
Leggi: Tipi di strutture di dati in Python
Ricerca per interpolazione
È una variante migliorata dell'algoritmo di ricerca binaria e funziona sulla posizione di rilevamento dell'elemento di ricerca. Simile agli algoritmi di ricerca binaria, funziona in modo efficiente solo su una raccolta di dati ordinata.
Tempo di esecuzione peggiore = O(n)
Quando la posizione dell'elemento di destinazione è nota nella raccolta dei dati, viene utilizzata una ricerca di interpolazione. Per trovare un numero nell'elenco telefonico, se si vuole cercare il numero di telefono di Monica, invece di usare la ricerca lineare o binaria, si può cercare direttamente nello spazio di memoria dove i nomi iniziano con 'M'.
Conclusione
La ricerca nelle strutture dati si riferisce alla ricerca di un dato elemento nell'array di 'n' elementi. Ci sono due categorie, vale a dire. Ricerca sequenziale e ricerca a intervalli nella ricerca. Quasi tutti gli algoritmi di ricerca si basano su una di queste due categorie. Le ricerche lineari e binarie sono i due algoritmi semplici e facili da implementare in cui il binario funziona più velocemente degli algoritmi lineari.
Sebbene la ricerca lineare sia più semplice, controlla ogni elemento finché non trova una corrispondenza con l'elemento di ricerca, quindi efficiente quando la raccolta dei dati non è ordinata correttamente. Ma se la raccolta dei dati è ordinata e la lunghezza di un array è considerevole, la ricerca binaria è più veloce.
La struttura dei dati è una parte essenziale della programmazione del computer durante la gestione dei set di dati. I programmatori e gli sviluppatori devono continuare ad aggiornarsi e perfezionarsi con nozioni di base e aggiornamenti nelle tecniche di programmazione del computer. I programmatori che si occupano della struttura dei dati dovrebbero optare spesso per i corsi.
Se sei curioso di saperne di più sulla scienza dei dati, dai un'occhiata all'Executive PG Program in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore, 1 contro 1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.
