Introduktion till algoritmer
En algoritm är en sekvens av steg som beskriver hur ett problem kan lösas. Varje datorprogram som slutar med ett resultat är i princip baserat på en algoritm. Algoritmer är emellertid inte bara begränsade för användning i datorprogram, de kan också användas för att lösa matematiska problem och i många frågor i det dagliga livet. Baserat på hur de fungerar kan vi dela algoritmer i flera typer. Låt oss ta en titt på några av de viktiga.
Typer av algoritm
Det finns många typer av algoritmer men de grundläggande typerna av algoritmer är:
1) Rekursiv algoritm
Detta är en av de mest intressanta algoritmerna eftersom den kallar sig själv med ett mindre värde som ingångar som det får efter att ha löst för de aktuella ingångarna. I enklare ord är det en algoritm som kallar sig upprepade gånger tills problemet är löst.
Problem som Tower of Hanoi eller DFS of a Graph kan enkelt lösas med hjälp av dessa algoritmer.
Här är till exempel en kod som hittar en fabrik med hjälp av en rekursionsalgoritm:
Faktum (y)
Om y är 0
retur 1
return (y * Fact (y-1)) / * det är här rekursionen händer * /
2) Dela upp och erövra algoritmen
Detta är ett annat effektivt sätt att lösa många problem. I Divide and Conquer-algoritmer, dela algoritmen i två delar, de första delarna delar upp problemet till hands i mindre delproblem av samma typ. Sedan på den andra delen löses dessa mindre problem och läggs sedan tillsammans (kombineras) för att producera den slutliga lösningen av problemet.
Sorteringssortering och snabb sortering kan göras med dividerings- och erövringsalgoritmer. Här är pseudokoden för algoritmen för sammanslagningssortering för att ge dig ett exempel:
MergeSorting (ar (), l, r)
Om r> l
- Hitta mittpunkten för att dela upp det givna arrayet i två halvor:
mitten m = (l + r) / 2
- Call mergeSortering för första halvåret:
Call mergeSorting (ar, l, m)
- Call mergeSortering för andra halvåret:
Call mergeSorting (ar, m + 1, r)
- Slå ihop halvorna sorterade i steg 2 och 3:
Samtalssammanslagning (ar, l, m, r)
3) Dynamisk programmeringsalgoritm
Dessa algoritmer fungerar genom att komma ihåg resultaten från tidigare körningar och använda dem för att hitta nya resultat. Med andra ord, dynamisk programmeringsalgoritm löser komplexa problem genom att dela upp den i flera enkla underproblem och sedan löser den var och en av dem och lagrar dem sedan för framtida användning.
Fibonacci-sekvens är ett bra exempel för algoritmer för dynamisk programmering, du kan se den fungera i pseudokoden:
Fibonacci (N) = 0 (för n = 0)
= 0 (för n = 1)
= Fibonacci (N-1) + Finacchi (N-2) (för n> 1)
4) girig algoritm
Dessa algoritmer används för att lösa optimeringsproblem. I denna algoritm hittar vi en lokalt optimal lösning (utan att ta hänsyn till någon konsekvens i framtiden) och hoppas hitta den optimala lösningen på global nivå.
Metoden garanterar inte att vi kan hitta en optimal lösning.
Algoritmen har 5 komponenter:
- Den första är en kandidatuppsättning från vilken vi försöker hitta en lösning.
- En urvalsfunktion som hjälper dig att välja den bästa kandidaten.
- En genomförbarhetsfunktion som hjälper till att avgöra om kandidaten kan användas för att hitta en lösning.
- En objektiv funktion som tilldelar värde till en möjlig lösning eller till en partiell lösning
- Lösningsfunktion som berättar när vi har hittat en lösning på problemet.
Huffman Coding och Dijkstra's algoritm är två främsta exempel där Greedy algoritm används.
Vid Huffman-kodning går algoritmen igenom ett meddelande och beroende på frekvensen för tecknen i det meddelandet tilldelar den för varje tecken en kodning med variabel längd. För att göra Huffman-kodning måste vi först bygga ett Huffman-träd från inmatningstecken och sedan gå igenom trädet för att tilldela koder till tecknen.
5) Brute Force Algoritm
Detta är en av de enklaste algoritmerna i konceptet. En brute-kraftalgoritm itererar blindt alla möjliga lösningar för att söka efter en eller flera lösningar som kan lösa en funktion. Tänk på brute force som att använda alla möjliga kombinationer av siffror för att öppna ett kassaskåp.
Här är ett exempel på sekventiell sökning med hjälp av brute force:
Algoritm S_Search (A (0..n), X)
A (n) ← X
i ← 0
Medan A (i) ≠ X gör
i ← i + 1
om jag <n återvänder i
annars returnerar -1
6) Backtracking-algoritm
Backtracking är en teknik för att hitta en lösning på ett problem i en inkrementell strategi. Den löser problem rekursivt och försöker komma till en lösning på ett problem genom att lösa en del av problemet åt gången. Om en av lösningarna misslyckas tar vi bort den och backspårar för att hitta en annan lösning.
Med andra ord, en backtracking-algoritm löser ett delproblem och om det inte lyckas lösa problemet ångrar det sista steget och börjar igen för att hitta lösningen på problemet.
N Queens-problem är ett bra exempel för att se Backtracking-algoritmen i aktion. N drottningsproblemet säger att det finns N bitar av drottningar i ett schackbräde och att vi måste ordna dem så att ingen drottning kan attackera någon annan drottning i styrelsen en gång organiserad.
Låt oss nu titta på SolveNQ-algoritmen och Kontrollera giltiga funktioner för att lösa problemet:
CheckValid (schackbräde, rad, kolumn)
Start
Om det finns en drottning till vänster om den aktuella kolumnen, returnera falskt
Om drottningen är längst upp till vänster diagonal, returnera då falskt
Om drottningen är längst ner till vänster diagonal, returnera då falskt
Återvänd sant
Slutet
SolveNQ (styrelse, kolumn)
Start
Om alla kolumner är fulla, returnera true
För varje rad som finns i schackbrädet
Do
Om, CheckValid (kort, x, kolumn), sedan
Ställ drottningen vid cell (x, kolumn) på brädet
Om SolveNQ (tavla, kolumn + 1) = Sann, returnerar du sant.
Annars, ta bort drottningen från cellen (x, kolumn) från brädet
Gjort
Returnera falskt
Slutet
Slutsats - typer av algoritmer
Algoritmer ligger bakom de flesta av de imponerande saker datorer kan göra och dessa är kärnan i de flesta datoruppgifter. Att bli bättre med algoritmer hjälper dig inte bara att vara en framgångsrik programmerare, men du kommer också att bli effektivare.
Rekommenderade artiklar
Detta har varit en guide till typer av algoritmer. Här diskuterar vi de sex viktigaste typerna av algoritmer med deras funktioner. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer -
- Introduktion till algoritm
- Algoritm i programmering
- Algoritmintervjufrågor
- Factorial i Python | Tekniker
- Snabbsorteringsalgoritmer i Java
- Topp 6 sorteringsalgoritm i JavaScript