7 algoritmer som alla programmerare borde veta

Som student i programmering har du troligtvis lärt dig många olika algoritmer under hela din karriär. Att bli skicklig i olika algoritmer är absolut nödvändigt för alla programmerare.

Med så många algoritmer kan det vara utmanande att hålla reda på vad som är viktigt. Om du förbereder dig för en intervju eller bara borstar dina färdigheter, kommer den här listan att göra det relativt enkelt. Läs vidare när vi listar de viktigaste algoritmerna för programmerare.

1. Dijkstras algoritm

Edsger Dijkstra var en av hans tids mest inflytelserika datavetare, och han bidrog till många olika områden inom datavetenskap, inklusive operativsystem, kompilatorbyggnad och mycket Mer. En av Dijkstras mest anmärkningsvärda bidrag är uppfinningsrikedomen i hans kortaste banalgoritm för grafer, även känd som Dijkstras kortaste vägalgoritm.

Dijkstras algoritm hittar den enda kortaste sökvägen i en graf från en källa till alla grafhörn. På varje iteration av algoritmen läggs en toppunkt till med det minsta avståndet från källan och en som inte finns i den nuvarande kortaste vägen. Detta är den giriga egenskapen som används av Djikstras algoritm.

Algoritmen implementeras vanligtvis med hjälp av en uppsättning. Dijkstras algoritm är mycket effektiv när den implementeras med en Min Heap; du kan hitta den kortaste vägen på bara O (V+ElogV) tid (V är antalet hörn och E är antalet kanter i en given graf).

Dijkstras algoritm har sina begränsningar; det fungerar bara på riktade och ostyrda grafer med kanter med positiv vikt. För negativa vikter är Bellman-Ford-algoritmen vanligtvis att föredra.

Intervjufrågor innehåller vanligtvis Djikstras algoritm, så vi rekommenderar starkt att förstå dess invecklade detaljer och applikationer.

2. Slå ihop Sortera

Vi har ett par sorteringsalgoritmer på den här listan, och sammanslagningssortering är en av de viktigaste algoritmerna. Det är en effektiv sorteringsalgoritm baserad på programmeringstekniken Divide and Conquer. I värsta fall kan sammanslagningssortera sortera "n" -tal på bara O (nlogn) tid. Jämfört med primitiva sorteringstekniker som t.ex. Bubble Sort (det tar O (n^2) tid), sammanslagningssort är utmärkt effektivt.

Relaterad: Introduktion till Merge Sort Algorithm

Vid sammanslagningssortering delas matrisen som ska sorteras upprepade gånger upp i delrader tills varje delruta består av ett enda nummer. Den rekursiva algoritmen sammanfogar sedan upprepade gånger med delraderna och sorterar matrisen.

3. Quicksort

Quicksort är en annan sorteringsalgoritm baserad på programmeringstekniken Divide and Conquer. I denna algoritm väljs först ett element som pivot, och hela matrisen partitioneras sedan runt denna pivot.

Som du säkert har gissat är en bra pivot avgörande för en effektiv sortering. Pivot kan antingen vara ett slumpmässigt element, mediaelementet, det första elementet eller till och med det sista elementet.

Implementeringar av kvicksort skiljer sig ofta åt i hur de väljer en svängning. I det genomsnittliga fallet kommer quicksort att sortera en stor array med en bra pivot på bara O (nlogn) tid.

Den allmänna pseudokoden för kvicksort uppdelar upprepade gånger matrisen på pivoten och placerar den i rätt position för delarrayen. Det placerar också elementen mindre än svängen till vänster och elementen större än svängen till höger.

4. Djup första sökning

Depth First Search (DFS) är en av de första grafalgoritmerna som eleverna lär sig. DFS är en effektiv algoritm som används för att gå igenom eller söka i en graf. Det kan också modifieras för att användas vid trädpassage.

DFS -traversalen kan utgå från vilken godtycklig nod som helst och den dyker in i varje intilliggande toppunkt. Algoritmen spårar tillbaka när det inte finns någon obesökt toppunkt, eller om det finns en återvändsgränd. DFS implementeras vanligtvis med en stack och en boolsk matris för att hålla reda på de besökta noder. DFS är enkel att implementera och exceptionellt effektiv; det fungerar (V+E), där V är antalet hörn och E är antalet kanter.

Typiska tillämpningar av DFS -transversalen inkluderar topologisk sortering, detektering av cykler i en graf, sökning efter sökvägen och att hitta starkt anslutna komponenter.

5. Utöka första sökningen

Breadth-First Search (BFS) är också känt som en nivåorderövergång för träd. BFS fungerar i O (V+E) som liknar en DFS -algoritm. BFS använder dock en kö istället för stacken. DFS dyker in i diagrammet, medan BFS korsar grafen i bredd.

BFS -algoritmen använder en kö för att hålla koll på hörnen. Oviserade intilliggande hörn besöks, markeras och köas. Om hörnet inte har något intilliggande hörn, tas ett hörn bort från kön och utforskas.

BFS används vanligtvis i peer-to-peer-nätverk, kortaste sökvägen till en oviktad graf och för att hitta det lägsta spanträdet.

6. Binär sökning

Binär sökning är en enkel algoritm för att hitta det nödvändiga elementet i en sorterad array. Det fungerar genom att upprepade gånger dela matrisen i hälften. Om det erforderliga elementet är mindre än det mellanliggande elementet, behandlas vänster sida av det mellersta elementet vidare; annars halveras höger sida och söks igen. Processen upprepas tills det nödvändiga elementet har hittats.

Den sämsta tidskomplexiteten för binär sökning är O (logn) vilket gör det mycket effektivt att söka linjära matriser.

7. Minsta omfattande trädalgoritmer

Ett minimumspanträd (MST) i en graf har minimikostnaden bland alla möjliga spanträd. Kostnaden för ett spänd träd beror på vikten av dess kanter. Det är viktigt att notera att det kan finnas mer än ett minimum som spänner över träd. Det finns två huvudsakliga MST -algoritmer, nämligen Kruskals och Prims.

Kruskals algoritm skapar MST genom att lägga kanten med minsta kostnad till en växande uppsättning. Algoritmen sorterar först kanter efter deras vikt och lägger sedan till kanter till MST med utgångspunkt från minimum.

Det är viktigt att notera att algoritmen inte lägger till kanter som bildar en cykel. Kruskals algoritm är att föredra för glesa grafer.

Prim's algoritm använder också en girig egenskap och är idealisk för täta grafer. Den centrala idén i Prims MST är att ha två olika uppsättningar hörn; en uppsättning innehåller den växande MST, medan den andra innehåller oanvända hörn. På varje iteration väljs den minsta viktkant som kommer att ansluta de två uppsättningarna.

Minsta omfattande trädalgoritmer är avgörande för klusteranalys, taxonomi och broadcast -nätverk.

En effektiv programmerare är skicklig med algoritmer

Programmerare lär sig ständigt och utvecklar sina färdigheter, och det finns några grundläggande väsentligheter som alla behöver vara skickliga i. En skicklig programmerare känner till de olika algoritmerna, fördelarna och nackdelarna med varje, och vilken algoritm som skulle vara mest lämplig för ett givet scenario.

En introduktion till skalsorteringsalgoritmen

Skalsortering är inte den mest effektiva metoden, men nybörjare har mycket att vinna på att öva på det.

Läs Nästa

Om författaren