7 algoritmus, amelyet minden programozónak tudnia kell

A programozás hallgatójaként valószínűleg rengeteg különböző algoritmust tanult meg pályafutása során. Minden programozó számára elengedhetetlen a különböző algoritmusokban való jártasság.

Ennyi algoritmus mellett nehéz lehet nyomon követni a lényeges dolgokat. Ha egy interjúra készül, vagy egyszerűen csak fejleszti készségeit, akkor ez a lista viszonylag egyszerűvé teszi. Olvassa el, miközben felsoroljuk a programozók számára legfontosabb algoritmusokat.

1. Dijkstra algoritmusa

Edsger Dijkstra korának egyik legbefolyásosabb informatikusa volt, és ebben közreműködött a számítástechnika számos különböző területe, beleértve az operációs rendszereket, a fordítószerkesztést és sok mindent több. Dijkstra egyik legjelentősebb közreműködése a legrövidebb útvonalú algoritmusok leleményessége a gráfok számára, más néven Dijkstra legrövidebb útvonal -algoritmusa.

Dijkstra algoritmusa megtalálja a gráf egyetlen legrövidebb útját a forrástól az összes gráfcsúcsig. Az algoritmus minden iterációján egy csúcs kerül hozzáadásra a forrástól minimális távolsággal, és egy olyan, amely nem létezik a jelenlegi legrövidebb útvonalon. Ez a mohó tulajdonság, amelyet Djikstra algoritmusa használ.

Az algoritmus általában egy halmaz segítségével valósul meg. A Dijkstra algoritmusa nagyon hatékony, ha Min Heap -el valósítják meg; a legrövidebb utat csak O (V+ElogV) idő alatt találhatja meg (V a csúcsok száma és E az élek száma egy adott gráfban).

Dijkstra algoritmusának megvannak a maga korlátai; csak pozitív súlyú szélekkel rendelkező irányított és irányítatlan grafikonokon működik. Negatív súlyok esetén általában a Bellman-Ford algoritmus az előnyösebb.

Az interjúkérdések általában a Djikstra algoritmusát tartalmazzák, ezért javasoljuk, hogy ismerje meg bonyolult részleteit és alkalmazásait.

2. Rendezés egyesítése

Ezen a listán van néhány rendezési algoritmus, és az egyesítés az egyik legfontosabb algoritmus. Ez egy hatékony rendezési algoritmus, amely a Divide and Conquer programozási technikán alapul. A legrosszabb esetben az egyesítési rendezés csak O (nlogn) idő alatt rendezheti az „n” számokat. Az olyan primitív válogatási technikákhoz képest, mint pl Buborék rendezés (ez O (n^2) időt vesz igénybe), az egyesítés rendezése kiválóan hatékony.

Összefüggő: Bevezetés az egyesítési rendezési algoritmusba

Az összevonás rendezésében a rendezendő tömb többször ismétlődik altömbökre, amíg minden altömb egyetlen számból áll. A rekurzív algoritmus ezután többször összevonja az altömböket, és rendezi a tömböt.

3. Quicksort

A Quicksort egy másik rendezési algoritmus, amely a Divide and Conquer programozási technikán alapul. Ebben az algoritmusban először egy elemet választanak csuklópontnak, majd a teljes tömböt e partícióra osztják.

Amint azt valószínűleg sejtette, a jó elforgatás elengedhetetlen a hatékony rendezéshez. A pivot lehet egy véletlenszerű elem, a médiaelem, az első elem vagy akár az utolsó elem.

A gyorsortartalom megvalósításai gyakran különböznek a pivot kiválasztásában. Átlagos esetben a quicksort nagy tömböt rendez egy jó elforgatással mindössze O (nlogn) idő alatt.

A quicksort általános pszeudokódja többször is felosztja a tömböt a pivoton, és pozícionálja az altömb helyes pozíciójába. Ezenkívül a csuklónál kisebb elemeket balra, jobbra pedig a csuklónál nagyobb elemeket helyezi el.

4. Mélység első keresés

A mélységi első keresés (DFS) az egyik első gráf algoritmus, amelyet a diákoknak tanítottak. A DFS egy hatékony algoritmus a gráf bejárására vagy keresésére. Ezenkívül módosítható a fák bejárásához.

A DFS bejárása bármely tetszőleges csomópontból elindulhat, és minden egyes szomszédos csúcsba merül. Az algoritmus visszalép, ha nincs meg nem látogatott csúcs, vagy zsákutca van. A DFS -t tipikusan veremmel és logikai tömbvel valósítják meg, hogy nyomon kövessék a felkeresett csomópontokat. A DFS egyszerűen kivitelezhető és kivételesen hatékony; működik (V+E), ahol V a csúcsok száma és E az élek száma.

A DFS bejárásának tipikus alkalmazásai közé tartozik a topológiai rendezés, a ciklusok detektálása a gráfban, az útkeresés és az erősen összefüggő komponensek keresése.

5. Szélesség-első keresés

A szélesség-első keresés (BFS) más néven a fák szintbeli sorrendjének bejárása. A BFS O (V+E) -ben működik, hasonlóan a DFS algoritmushoz. A BFS azonban sorokat használ a verem helyett. A DFS belemerül a gráfba, míg a BFS szélességben keresztezi a gráfot.

A BFS algoritmus sorban követi a csúcsokat. A nem meglátogatott szomszédos csúcsokat meglátogatják, megjelölik és sorba állítják. Ha a csúcsnak nincs szomszédos csúcsa, akkor egy csúcsot eltávolít a sorból, és feltárja.

A BFS-t általánosan használják a peer-to-peer hálózatokban, a súlyozatlan gráf legrövidebb útján, és a minimális átfogó fa megkereséséhez.

6. Bináris keresés

Bináris keresés egy egyszerű algoritmus a szükséges elem megtalálására egy rendezett tömbben. Úgy működik, hogy többször felére osztja a tömböt. Ha a szükséges elem kisebb, mint a középső elem, akkor a középső elem bal oldala tovább feldolgozásra kerül; ellenkező esetben a jobb oldali felét felezik, és újra átkutatják. A folyamatot addig ismételjük, amíg meg nem találjuk a szükséges elemet.

A bináris keresés legrosszabb időbeli összetettsége az O (logn), ami nagyon hatékonyvá teszi a lineáris tömbök keresését.

7. Minimális Spanning Tree algoritmusok

A gráf minimális átfogó fa (MST) minimális költsége az összes lehetséges átfogó fa között. Az átívelő fa ára a széleinek súlyától függ. Fontos megjegyezni, hogy több minimális átfogó fa is lehet. Két fő MST algoritmus létezik, nevezetesen a Kruskal és a Prim.

A Kruskal algoritmusa úgy hozza létre az MST -t, hogy az élt minimális költséggel hozzáadja a növekvő halmazhoz. Az algoritmus először az éleket súlyuk szerint rendezi, majd a minimálistól kezdve hozzáadja az éleket az MST -hez.

Fontos megjegyezni, hogy az algoritmus nem ad hozzá éleket, amelyek ciklust alkotnak. Kruskal algoritmusa előnyös a ritka gráfok esetében.

A Prim algoritmusa mohó tulajdonságot is használ, és ideális sűrű grafikonokhoz. A Prim MST központi gondolata az, hogy két különböző csúcshalmaz legyen; az egyik halmaz a növekvő MST -t tartalmazza, míg a másik fel nem használt csúcsokat. Minden iterációnál ki kell választani azt a minimális súlyszélt, amely összeköti a két készletet.

A klaszteranalízishez, a rendszertanhoz és a műsorszóró hálózatokhoz elengedhetetlenek a minimális átfogó fa algoritmusok.

A hatékony programozó jártas az algoritmusokban

A programozók folyamatosan tanulják és fejlesztik készségeiket, és vannak alapvető tudnivalók, amelyekben mindenkinek jártasnak kell lennie. Egy képzett programozó ismeri a különböző algoritmusokat, mindegyik előnyeit és hátrányait, valamint azt, hogy melyik algoritmus lenne a legmegfelelőbb egy adott forgatókönyvhöz.

Bevezetés a héjrendező algoritmusba

Bár a héj rendezés nem a leghatékonyabb módszer, a kezdőknek sok hasznuk van a gyakorlásából.

Olvassa tovább

A szerzőről