Mi piacerebbe avere un senso per la gamma di complessità in cui cadono gli algoritmi. Penso che sarebbe interessante e utile per chi, come me, sta cercando di capire meglio come vengono formulati gli algoritmi e come decostruirli.
Puoi offrire un algoritmo di base con spiegazione, un algoritmo intermedio con spiegazione e forse un livello esperto (con o senza) una spiegazione?
Dalla Matrice competenza del programmatore:
principianti
Di base ordinamento , ricerca e attraversamento della struttura dati e algoritmi di recupero
Intermedio
Albero e Grafico strutture dati, semplice goloso e divide and conquer .
Avanzate
algoritmi del grafico , algoritmi di calcolo numerici , ecc.
principianti
Ricerca binaria : individua la posizione di un elemento in una matrice ordinata.
Inserimento albero AVL : inserisci un elemento in un albero AVL mantenendo la proprietà di bilanciamento dei sottostrutture.
Ricerca approfondita , Ricerca per ampiezza : cammina sui nodi di un grafico in ordine DFS o BFS.
Intermedio
Algoritmo di Dijkstra : algoritmo di ricerca del grafico che risolve il problema del percorso più breve a sorgente singola per un grafico con bordo non negativo costo del percorso, producendo un albero del percorso più breve.
Long Success Common Successive : Trova la sottosequenza più lunga comune a tutte le sequenze in un insieme di sequenze (spesso solo due).
Scafo convesso (Graham Scan) : Dato un insieme di punti, trova il sottoinsieme minimo di quei punti da coprire con un poligono convesso.
Ordinamento di conteggio : algoritmo di ordinamento di interi consecutivi in O (n).
Avanzate
Intervallo Minimu Query : Dato un array A [1, n] di n oggetti ordinati (come i numeri), una Range Minimum Query (o RMQ) da i a j richiede la posizione di un elemento minimo nel sub-array A [i, j]. Gli RMQ possono essere utilizzati per risolvere il problema il più basso antenato comune .
Altri esempi
Principiante: Inversione della lista collegata , Mergesort , Setaccio di Eratostene , Algoritmi albero nero- nero (inserimento e rimozione)
Intermedio: Simplex , Test di primalità di Miller-Rabin , codifica di Huffman , Algoritmo di Kruskal
Avanzate: Algoritmo di Viterbi , FFT di Cooley-Tukey , Ricottura simulata , Inferenza di tipo Hindley-Milner
Ho cercato di trovare collegamenti che avevano almeno qualche pseudocodice e / o una buona spiegazione. Ma la cosa sugli algoritmi avanzati è che hanno molte varianti. Quindi, puoi spiegare lo schema di base di un "algoritmo genetico", ma in realtà ci sono molti algoritmi che seguono quel nome. (Lo stesso per la FFT, ho collegato una variante denominata di esso)
Questo testo sull'integrazione numerica , per un pubblico di gioco, descrive due algoritmi per l'integrazione numerica: una più semplice , algoritmo semplice (l'integratore di Eulero) e uno più avanzato (l'integratore di ordine 4 di Runge-Kutta). Potrebbe essere un bene vedere "base vs. avanzato". È possibile utilizzare gli integratori per simulare la fisica e l'integratore di Eulero porta a errori enormi, quindi raccomanda RK4. Ma sono probabilmente varianti dello "stesso" algoritmo: Eulero è RK di primo ordine.
Leggi altre domande sui tag algorithms