7 algoritmov, ki bi jih moral poznati vsak programer

Kot študent programiranja ste se v svoji karieri verjetno naučili veliko različnih algoritmov. Obvladanje različnih algoritmov je nujno za vsakega programerja.

S toliko algoritmi je lahko težko spremljati, kaj je bistveno. Če se pripravljate na razgovor ali preprosto nadgrajujete svoje sposobnosti, bo ta seznam razmeroma enostaven. Preberite, ko navajamo najpomembnejše algoritme za programerje.

1. Dijkstrin algoritem

Edsger Dijkstra je bil eden najvplivnejših računalniških znanstvenikov svojega časa in je prispeval k temu veliko različnih področij računalniške znanosti, vključno z operacijskimi sistemi, konstrukcijo prevajalnika in še veliko več več. Eden najpomembnejših prispevkov Dijkstre je iznajdljivost njegovega algoritma najkrajše poti za grafe, znanega tudi kot Dijkstrin najkrajši algoritem poti.

Dijkstrin algoritem najde eno najkrajšo pot v grafu od vira do vseh grafov. Na vsaki iteraciji algoritma se doda oglišče z najmanjšo razdaljo od vira in tisto, ki ne obstaja na trenutni najkrajši poti. To je pohlepna lastnost, ki jo uporablja Djikstrin algoritem.

Algoritem se običajno izvaja z uporabo niza. Dijkstrin algoritem je zelo učinkovit, če se izvaja z najmanjšo količino; najkrajšo pot lahko najdete samo v času O (V+ElogV) (V je število točk in E število robov v danem grafu).

Dijkstrin algoritem ima svoje omejitve; deluje le na usmerjenih in neusmerjenih grafih z robovi pozitivne teže. Za negativne uteži je običajno prednostni Bellman-Fordov algoritem.

Vprašanja za intervju običajno vključujejo Djikstrin algoritem, zato toplo priporočamo razumevanje njegovih zapletenih podrobnosti in aplikacij.

2. Združi razvrsti

Na tem seznamu imamo nekaj algoritmov za razvrščanje in združevanje je eden najpomembnejših algoritmov. To je učinkovit algoritem razvrščanja, ki temelji na tehniki programiranja Divide and Conquer. V najslabšem primeru lahko razvrščanje po združitvi razvrsti številke »n« samo v času O (nlogn). V primerjavi s primitivnimi tehnikami razvrščanja, kot so npr Razvrstitev mehurčkov (kar traja čas O (n^2)), je združevanje razvrščanja izjemno učinkovito.

Povezano: Uvod v algoritem razvrščanja za združevanje

Pri razvrščanju z združevanjem se matrika, ki jo je treba razvrstiti, večkrat razčleni v podmote, dokler ni vsaka podmaza sestavljena iz ene same številke. Rekurzivni algoritem nato večkrat združi podmaze in razvrsti matriko.

3. Quicksort

Quicksort je še en algoritem razvrščanja, ki temelji na tehniki programiranja Divide and Conquer. V tem algoritmu je za vrtilni element najprej izbran element, nato pa je celotna matrika razdeljena okoli tega vrtilnega elementa.

Kot ste verjetno uganili, je za učinkovito razvrščanje ključnega pomena dober zaokret. Vrtišče je lahko naključni element, medijski element, prvi element ali celo zadnji element.

Izvajanje hitrega razvrščanja se pogosto razlikuje po načinu izbire vrtilne točke. V povprečju bo quicksort razvrstil veliko matriko z dobro vrtilno le v času O (nlogn).

Splošna psevdokoda hitrega razvrščanja matriko na vrtišču večkrat razdeli in postavi v pravilen položaj podmota. Levo postavi tudi elemente, manjše od vrtilne točke, desno pa elemente, večje od vrtilne.

4. Globinsko prvo iskanje

Depth First Search (DFS) je eden prvih algoritmov grafov, ki so jih naučili študente. DFS je učinkovit algoritem, ki se uporablja za prečkanje ali iskanje grafa. Prav tako ga je mogoče spremeniti za uporabo pri prečkanju dreves.

Premik DFS se lahko začne iz katerega koli poljubnega vozlišča in se potopi v vsako sosednje oglišče. Algoritem se vrne, ko ni neobiskanega oglišča ali pa je slepa ulica. DFS se običajno izvaja z nizom in logično matriko za spremljanje obiskanih vozlišč. DFS je enostaven za izvedbo in izjemno učinkovit; deluje (V+E), kjer je V število točk in E število robov.

Tipične aplikacije prehoda DFS vključujejo topološko razvrščanje, zaznavanje ciklov v grafu, iskanje poti in iskanje močno povezanih komponent.

5. Iskanje po širini

Iskanje po širini (BFS) je znano tudi kot premik vrstnega reda dreves. BFS deluje v O (V+E) podobno kot algoritem DFS. Vendar BFS namesto sklada uporablja čakalno vrsto. DFS se potopi v graf, BFS pa po grafu po širini.

Algoritem BFS uporablja čakalno vrsto za spremljanje točk. Neobiskana sosednja oglišča so obiskana, označena in postavljena v čakalno vrsto. Če oglišče nima sosednje vertikalne točke, se iz vrstice odstrani in raziskuje.

BFS se običajno uporablja v peer-to-peer omrežjih, najkrajša pot netehtanega grafa in za iskanje najmanjšega obsega drevesa.

6. Binarno iskanje

Binarno iskanje je preprost algoritem za iskanje zahtevanega elementa v razvrščeni matriki. Deluje tako, da matriko večkrat razdeli na polovico. Če je zahtevani element manjši od skrajnega sredinskega elementa, se leva stran srednjega elementa dodatno obdela; v nasprotnem primeru se desna stran prepolovi in ​​znova poišče. Postopek se ponavlja, dokler ne najdete zahtevanega elementa.

Najhujša časovna zapletenost binarnega iskanja je O (logn), zaradi česar je zelo učinkovit pri iskanju linearnih nizov.

7. Najmanjši algoritmi raztezajočega drevesa

Najmanjše raztezajoče drevo (MST) grafa ima najnižje stroške med vsemi možnimi raztezajočimi drevesi. Stroški razteznega drevesa so odvisni od teže njegovih robov. Pomembno je omeniti, da je lahko več kot eno minimalno raztezajoče drevo. Obstajata dva glavna algoritma MST, in sicer Kruskalov in Primov.

Kruskalov algoritem ustvari MST tako, da naraščajočemu nizu doda rob z minimalnimi stroški. Algoritem najprej razvrsti robove po njihovi teži in nato doda robove v MST, začenši od najmanjšega.

Pomembno je omeniti, da algoritem ne dodaja robov, ki tvorijo cikel. Kruskalov algoritem je prednost za redke grafe.

Primov algoritem uporablja tudi pohlepno lastnost in je idealen za goste grafe. Osrednja ideja Primovega MST je imeti dva različna niza točk; en niz vsebuje naraščajoči MST, drugi pa neuporabljene točke. Na vsaki iteraciji je izbran rob najmanjše teže, ki bo povezal dva niza.

Algoritmi minimalnega obsega drevesa so bistveni za analizo grozdov, taksonomijo in oddajna omrežja.

Učinkovit programer dobro pozna algoritme

Programerji se nenehno učijo in razvijajo svoje veščine, pri čemer morajo biti vsi bistveni. Izkušen programer pozna različne algoritme, prednosti in slabosti vsakega od njih ter kateri algoritem bi bil za določen scenarij najbolj primeren.

Uvod v algoritem razvrščanja lupine

Medtem ko razvrščanje lupin ni najučinkovitejša metoda, lahko začetniki z vadbo veliko pridobijo.

Preberite Naprej

O avtorju