Video: L'algoritmo di Dijkstra - Logically Nerd 2024
Immagina di provare a trovare un elemento in una lista senza prima ordinarlo. Ogni ricerca diventa una ricerca sequenziale che richiede tempo. Ma, può essere fatto un caso per non ordinare i dati per gli algoritmi. Dopo tutto, i dati sono ancora accessibili, anche se non lo si ordina, e l'ordinamento richiede tempo.
Naturalmente, il problema con i dati non ordinati è lo stesso problema di quel cassetto spazzatura nella tua cucina (o ovunque tu abbia il tuo cassetto della spazzatura - assumendo che tu possa trovarlo del tutto). Cercare qualsiasi cosa nel cassetto della spazzatura richiede molto tempo, perché non puoi nemmeno iniziare a indovinare dove trovare qualcosa. Piuttosto che limitarti a prendere e prendere ciò che desideri, devi rimuovere una miriade di altri elementi che non vuoi nel tentativo di trovare l'elemento di cui hai bisogno. Sfortunatamente, l'articolo di cui hai bisogno potrebbe non essere nel cassetto della spazzatura in primo luogo, potresti averlo buttato via o averlo messo in un altro cassetto.
Il cassetto spazzatura nella tua casa è come i dati non ordinati sul tuo sistema. Quando i dati non sono ordinati, devi cercare un elemento alla volta e non sai nemmeno se troverai ciò di cui hai bisogno senza prima cercare tutti gli elementi nel set di dati. È un modo frustrante per lavorare con i dati.
Naturalmente, semplicemente l'ordinamento dei dati non è sufficiente. Se si dispone di un database dipendente ordinato per cognome, ma è necessario cercare un dipendente per data di nascita, l'ordinamento non è utile. (Dire che si desidera trovare tutti i dipendenti che hanno un compleanno in un determinato giorno.) Per trovare la data di nascita che è necessario, è comunque necessario cercare l'intero set di dati un elemento alla volta. Di conseguenza, l'ordinamento deve concentrarsi su un particolare bisogno. Sì, era necessario il database dei dipendenti ordinato per dipartimento a un certo punto e per cognome in un altro momento, ma ora è necessario ordinarlo per data di nascita in modo da utilizzare il set di dati in modo efficace.
La necessità di mantenere diversi ordini ordinati per gli stessi dati è la ragione per cui gli sviluppatori hanno creato degli indici. L'ordinamento di un indice piccolo è più rapido rispetto all'ordinamento dell'intero set di dati. L'indice mantiene un ordine di dati specifico e punta al set di dati completo in modo da poter trovare ciò di cui hai bisogno in modo estremamente rapido. Mantenendo un indice per ciascun requisito di ordinamento, è possibile ridurre efficacemente i tempi di accesso ai dati e consentire a più persone di accedere ai dati contemporaneamente nell'ordine in cui devono accedervi.
Sono disponibili molti modi per categorizzare gli algoritmi di ordinamento. Uno di questi modi è la velocità del genere. Quando si considera l'efficacia di un particolare algoritmo di ordinamento nell'ordinare i dati, i benchmark di temporizzazione in genere prendono in considerazione due fattori:
- Confronti: Per spostare i dati da una posizione in un set di dati a un altro, è necessario sapere dove spostarli, che significa confrontare i dati di destinazione con altri dati nel set di dati.Avere meno confronti significa prestazioni migliori.
- Scambi: A seconda di come si scrive un algoritmo, i dati potrebbero non arrivare alla sua posizione finale nel set di dati al primo tentativo. I dati potrebbero effettivamente spostarsi più volte. Il numero di scambi influisce notevolmente sulla velocità perché ora stai spostando i dati da una posizione a un'altra nella memoria. Scambi minori e minori (come quando si usano gli indici) significa prestazioni migliori.
