7 algoritama koje bi trebao znati svaki programer

Kao student programiranja vjerojatno ste tijekom svoje karijere naučili mnogo različitih algoritama. Poznavanje različitih algoritama apsolutno je bitno za svakog programera.

S toliko algoritama može biti izazov pratiti ono što je bitno. Ako se pripremate za intervju ili jednostavno nadopunite svoje vještine, ovaj će vam popis učiniti relativno lakim. Čitajte dalje dok navodimo najvažnije algoritme za programere.

1. Dijkstrin algoritam

Edsger Dijkstra bio je jedan od najutjecajnijih informatičara svog vremena, a on je dao svoj doprinos mnogo različitih područja računalne znanosti, uključujući operacijske sustave, konstrukciju prevoditelja i još mnogo toga više. Jedan od najznačajnijih doprinosa Dijkstre je domišljatost njegovog algoritma za najkraći put za grafikone, poznatog i kao Dijkstrin najkraći algoritam puta.

Dijkstrin algoritam pronalazi jedan najkraći put u grafu od izvora do svih vrhova grafa. Na svakoj iteraciji algoritma dodaje se vrh s minimalnom udaljenošću od izvora i onim koji ne postoji na trenutnoj najkraćoj putanji. Ovo je pohlepno svojstvo koje koristi Djikstrin algoritam.

Algoritam se obično provodi pomoću skupa. Dijkstrin algoritam vrlo je učinkovit kada se implementira s minimalnom hrpom; možete pronaći najkraći put u samo O (V+ElogV) vremenu (V je broj vrhova, a E broj rubova u datom grafu).

Dijkstrin algoritam ima svoja ograničenja; radi samo na usmjerenim i neusmjerenim grafovima s rubovima pozitivne težine. Za negativne težine tipično je poželjan Bellman-Fordov algoritam.

Pitanja za intervju obično uključuju Djikstrin algoritam, pa toplo preporučujemo razumijevanje njegovih zamršenih detalja i aplikacija.

2. Spoji sortiranje

Na ovom popisu imamo nekoliko algoritama za sortiranje, a sortiranje stapanjem je jedan od najvažnijih algoritama. To je učinkovit algoritam sortiranja temeljen na programskoj tehnici Divide and Conquer. U najgorem slučaju, sortiranje spajanjem može sortirati “n” brojeve u samo O (nlogn) vremenu. U usporedbi s primitivnim tehnikama sortiranja poput Sortiranje mjehurićima (za to je potrebno O (n^2) vrijeme), sortiranje stapanjem izvrsno je učinkovito.

Povezano: Uvod u algoritam sortiranja spoja

U sortiranju spajanjem, niz koji se sortira opetovano se razbija u podmase sve dok se svaki podrazred ne sastoji od jednog broja. Rekurzivni algoritam tada opetovano spaja pod nizove i sortira niz.

3. Quicksort

Quicksort je još jedan algoritam sortiranja koji se temelji na tehnici programiranja Divide and Conquer. U ovom algoritmu, element se prvo bira kao zaokret, a cijeli niz se zatim particionira oko tog zaokreta.

Kao što ste vjerojatno pretpostavili, dobar zaokret ključan je za učinkovito sortiranje. Okretni element može biti ili slučajni element, medijski element, prvi element ili čak zadnji element.

Implementacije brzog sortiranja često se razlikuju u načinu na koji biraju zaokret. U prosječnom slučaju, brzo sortiranje će sortirati veliki niz s dobrim zaokretom za samo O (nlogn) vrijeme.

Opći pseudokod brzog razvrstavanja opetovano particionira niz na zaokretu i postavlja ga u ispravan položaj podmaze. Također lijevo postavlja elemente manje od zaokreta, a desno više od zaokreta.

4. Dubinsko prvo pretraživanje

Depth First Search (DFS) jedan je od prvih algoritama grafikona koji se uči studentima. DFS je učinkovit algoritam koji se koristi za kretanje ili pretraživanje grafikona. Također se može izmijeniti za upotrebu pri prelasku stabala.

DFS -ov prelazak može započeti sa bilo kojeg proizvoljnog čvora i roni u svaki susjedni vrh. Algoritam se vraća unatrag kada nema neposjećenog vrha ili postoji slijepa ulica. DFS se obično implementira sa hrpom i logičkim nizom za praćenje posjećenih čvorova. DFS je jednostavan za implementaciju i iznimno učinkovit; radi (V+E), gdje je V broj vrhova, a E broj bridova.

Tipične primjene DFS prelaska uključuju topološko sortiranje, otkrivanje ciklusa u grafikonu, pronalaženje puta i pronalaženje jako povezanih komponenti.

5. Pretraživanje po širini

Breadth-First Search (BFS) također je poznat kao prelaz po stablima po razini. BFS radi u O (V+E) slično DFS algoritmu. Međutim, BFS koristi red umjesto hrpe. DFS ponire u grafikon, dok BFS prelazi graf po širini.

BFS algoritam koristi red za praćenje vrhova. Neposjećeni susjedni vrhovi se posjećuju, označavaju i stavljaju u red. Ako vrh nema susjednih vrhova, tada se vrh uklanja iz reda i istražuje.

BFS se obično koristi u peer-to-peer mrežama, najkraćoj putanji neponderiranog grafa i za pronalaženje minimalnog raspona stabla.

6. Binarno pretraživanje

Binarno pretraživanje je jednostavan algoritam za pronalaženje traženog elementa u sortiranom nizu. Djeluje tako da se niz više puta dijeli na pola. Ako je traženi element manji od krajnjeg elementa, tada se lijeva strana srednjeg elementa dalje obrađuje; u protivnom se desna strana prepolovi i ponovno pretražuje. Postupak se ponavlja sve dok se ne pronađe traženi element.

Složenost binarnog pretraživanja u najgorem slučaju je O (logn) što ga čini vrlo učinkovitim pri pretraživanju linearnih nizova.

7. Algoritmi minimalnog raspon stabla

Minimalno rasponsko stablo (MST) grafikona ima minimalne troškove među svim mogućim rasponskim stablima. Cijena raspornog stabla ovisi o težini njegovih rubova. Važno je napomenuti da može postojati više od jednog minimalnog raspona stabla. Postoje dva glavna MST algoritma, naime Kruskalov i Primov.

Kruskalov algoritam stvara MST dodavanjem ruba uz minimalne troškove rastućem skupu. Algoritam najprije sortira rubove prema njihovoj težini, a zatim dodaje rubove u MST počevši od minimalnog.

Važno je napomenuti da algoritam ne dodaje rubove koji tvore ciklus. Kruškalov algoritam preferira se za rijetke grafove.

Primov algoritam također koristi pohlepno svojstvo i idealan je za guste grafikone. Središnja ideja Prim -ovog MST -a je imati dva različita skupa vrhova; jedan skup sadrži rastući MST, dok drugi sadrži neiskorištene vrhove. Na svakoj iteraciji odabire se rub minimalne težine koji će spojiti dva skupa.

Algoritmi minimalnog raspona stabla bitni su za analizu klastera, taksonomiju i mreže emitiranja.

Učinkovit programer poznaje algoritme

Programeri neprestano uče i razvijaju svoje vještine, a postoje neke bitne stvari u kojima svi moraju biti vješti. Vješt programer zna različite algoritme, prednosti i nedostatke svakog od njih te koji bi algoritam bio najprikladniji za dati scenarij.

Uvod u algoritam sortiranja ljuske

Iako sortiranje ljuski nije najučinkovitija metoda, početnici imaju mnogo koristi od vježbanja.

Pročitajte Dalje

O autoru