7 algoritmi che ogni programmatore dovrebbe conoscere

Come studente di programmazione, probabilmente hai imparato molti algoritmi diversi nel corso della tua carriera. Diventare abile in diversi algoritmi è assolutamente essenziale per qualsiasi programmatore.

Con così tanti algoritmi, può essere difficile tenere traccia di ciò che è essenziale. Se ti stai preparando per un colloquio o semplicemente rispolverando le tue abilità, questo elenco lo renderà relativamente facile. Continua a leggere mentre elenchiamo gli algoritmi più essenziali per i programmatori.

1. Algoritmo di Dijkstra

Edsger Dijkstra è stato uno degli scienziati informatici più influenti del suo tempo e ha contribuito a molte diverse aree dell'informatica, inclusi i sistemi operativi, la costruzione di compilatori e molto altro di più. Uno dei contributi più importanti di Dijkstra è l'ingegnosità del suo algoritmo del percorso più breve per i grafici, noto anche come Algoritmo del percorso più breve di Dijkstra.

L'algoritmo di Dijkstra trova il singolo percorso più breve in un grafo da una sorgente a tutti i vertici del grafo. Ad ogni iterazione dell'algoritmo viene aggiunto un vertice con la distanza minima dalla sorgente e uno che non esiste nel percorso minimo corrente. Questa è la proprietà greedy utilizzata dall'algoritmo di Djikstra.

L'algoritmo viene in genere implementato utilizzando un set. L'algoritmo di Dijkstra è molto efficiente se implementato con un Min Heap; puoi trovare il percorso più breve in appena O(V+ElogV) tempo (V è il numero di vertici ed E è il numero di bordi in un dato grafico).

L'algoritmo di Dijkstra ha i suoi limiti; funziona solo su grafi diretti e non orientati con archi di peso positivo. Per i pesi negativi, in genere è preferibile l'algoritmo Bellman-Ford.

Le domande dell'intervista includono comunemente l'algoritmo di Djikstra, quindi consigliamo vivamente di comprenderne i dettagli e le applicazioni intricate.

2. Unisci ordinamento

Abbiamo un paio di algoritmi di ordinamento in questo elenco e il merge sort è uno degli algoritmi più importanti. È un efficiente algoritmo di ordinamento basato sulla tecnica di programmazione Divide and Conquer. Nel peggiore dei casi, il merge sort può ordinare "n" numeri in appena O(nlogn). Rispetto alle tecniche di smistamento primitive come Ordinamento a bolle (che richiede tempo O(n^2)), il merge sort è estremamente efficiente.

Imparentato: Introduzione all'algoritmo di ordinamento di unione

Nel merge sort, l'array da ordinare viene ripetutamente suddiviso in sottoarray finché ogni sottoarray è costituito da un singolo numero. L'algoritmo ricorsivo quindi unisce ripetutamente i sottoarray e ordina l'array.

3. Quicksort

Quicksort è un altro algoritmo di ordinamento basato sulla tecnica di programmazione Divide and Conquer. In questo algoritmo, un elemento viene prima scelto come pivot e l'intero array viene quindi partizionato attorno a questo pivot.

Come probabilmente avrai intuito, un buon perno è cruciale per un ordinamento efficiente. Il pivot può essere un elemento casuale, l'elemento media, il primo elemento o anche l'ultimo elemento.

Le implementazioni di Quicksort spesso differiscono nel modo in cui scelgono un pivot. Nel caso medio, Quicksort ordinerà un array di grandi dimensioni con un buon pivot in appena O(nlogn) tempo.

Lo pseudocodice generale di Quicksort partiziona ripetutamente l'array sul pivot e lo posiziona nella posizione corretta del sottoarray. Posiziona anche gli elementi più piccoli del perno alla sua sinistra e gli elementi più grandi del perno alla sua destra.

4. Profondità prima ricerca

Depth First Search (DFS) è uno dei primi algoritmi di grafi insegnati agli studenti. DFS è un algoritmo efficiente utilizzato per attraversare o cercare un grafico. Può anche essere modificato per essere utilizzato nell'attraversamento degli alberi.

L'attraversamento DFS può iniziare da qualsiasi nodo arbitrario e si tuffa in ogni vertice adiacente. L'algoritmo torna indietro quando non ci sono vertici non visitati o c'è un vicolo cieco. DFS è in genere implementato con uno stack e un array booleano per tenere traccia dei nodi visitati. DFS è semplice da implementare ed eccezionalmente efficiente; funziona (V+E), dove V è il numero di vertici ed E è il numero di spigoli.

Le applicazioni tipiche dell'attraversamento DFS includono l'ordinamento topologico, il rilevamento di cicli in un grafico, l'individuazione di percorsi e la ricerca di componenti fortemente connessi.

5. Ricerca in ampiezza

La ricerca in ampiezza (BFS) è anche nota come attraversamento dell'ordine di livello per gli alberi. BFS funziona in O(V+E) in modo simile a un algoritmo DFS. Tuttavia, BFS utilizza una coda invece dello stack. DFS si tuffa nel grafico, mentre BFS attraversa il grafico in larghezza.

L'algoritmo BFS utilizza una coda per tenere traccia dei vertici. I vertici adiacenti non visitati vengono visitati, contrassegnati e messi in coda. Se il vertice non ha vertici adiacenti, un vertice viene rimosso dalla coda ed esplorato.

BFS è comunemente usato nelle reti peer-to-peer, nel percorso più breve di un grafo non pesato e per trovare lo spanning tree minimo.

6. Ricerca binaria

Ricerca binaria è un semplice algoritmo per trovare l'elemento richiesto in un array ordinato. Funziona dividendo ripetutamente l'array a metà. Se l'elemento richiesto è più piccolo dell'elemento più centrale, il lato sinistro dell'elemento centrale viene ulteriormente elaborato; in caso contrario, il lato destro viene dimezzato e ricercato di nuovo. Il processo viene ripetuto finché non viene trovato l'elemento richiesto.

La complessità temporale della ricerca binaria nel caso peggiore è O(logn) che la rende molto efficiente nella ricerca di array lineari.

7. Algoritmi di albero di copertura minimo

Un albero di copertura minimo (MST) di un grafo ha il costo minimo tra tutti i possibili alberi di copertura. Il costo di un albero ricoprente dipende dal peso dei suoi bordi. È importante notare che può esserci più di un albero ricoprente minimo. Esistono due principali algoritmi MST, ovvero Kruskal e Prim.

L'algoritmo di Kruskal crea l'MST aggiungendo il margine con il costo minimo a un insieme in crescita. L'algoritmo prima ordina gli archi in base al loro peso e poi aggiunge gli archi all'MST partendo dal minimo.

È importante notare che l'algoritmo non aggiunge bordi che formano un ciclo. L'algoritmo di Kruskal è preferito per i grafici sparsi.

L'algoritmo di Prim utilizza anche una proprietà greedy ed è ideale per grafici densi. L'idea centrale nell'MST di Prim è di avere due distinti insiemi di vertici; un insieme contiene l'MST in crescita, mentre l'altro contiene vertici inutilizzati. Ad ogni iterazione, viene selezionato il limite di peso minimo che collegherà i due set.

Gli algoritmi di albero di copertura minimo sono essenziali per l'analisi dei cluster, la tassonomia e le reti di trasmissione.

Un programmatore efficiente è abile con gli algoritmi

I programmatori imparano e sviluppano costantemente le proprie capacità e ci sono alcuni elementi essenziali di cui tutti devono essere abili. Un programmatore esperto conosce i diversi algoritmi, i vantaggi e gli svantaggi di ciascuno e quale algoritmo sarebbe più appropriato per un determinato scenario.

Introduzione all'algoritmo di ordinamento della shell

Sebbene lo shell sort non sia il metodo più efficiente, i principianti hanno molto da guadagnare dalla pratica.

Leggi Avanti

Circa l'autore