Vad är en algoritm?
En algoritm är en steg-för-steg procedur för att lösa ett problem. En bra algoritm bör vara optimerad när det gäller tid och rum. Olika typer av problem kräver olika typer av algoritmiska tekniker för att lösas på det mest optimerade sättet. Det finns många typer av algoritmer men de viktigaste och mest grundläggande algoritmerna som du måste diskuteras i den här artikeln.
1. Brute Force Algorithm :
Detta är den mest grundläggande och enklaste typen av algoritm. En Brute Force Algorithm är den enkla inställningen till ett problem, det vill säga det första tillvägagångssättet som vi tänker på när vi ser problemet. Mer tekniskt är det precis som att upprepa alla tillgängliga möjligheter för att lösa det problemet.
Exempel:
Om det finns ett lås med 4-siffrig PIN-kod. Siffrorna som ska väljas från 0-9, då kommer råstyrkan att försöka alla möjliga kombinationer en efter en som 0001, 0002, 0003, 0004, och så vidare tills vi får rätt PIN-kod. I värsta fall kommer det att ta 10 000 försök att hitta rätt kombination.
2. Rekursiv algoritm :
Denna typ av algoritm är baserad på rekursion . Vid rekursion löser man ett problem genom att dela upp det i delproblem av samma typ och kalla det egna jaget om och om igen tills problemet är löst med hjälp av ett basvillkor.
Några vanliga problem som löses med hjälp av rekursiva algoritmer är Faktoriell av ett nummer , Fibonacci-serien , Hanois torn , DFS för Graph , etc.
a) Dela och erövra algoritm :
I Divide and Conquer-algoritmer är tanken att lösa problemet i två avsnitt, det första avsnittet delar upp problemet i delproblem av samma typ. Det andra avsnittet är att lösa det mindre problemet självständigt och sedan lägga till det kombinerade resultatet för att producera det slutliga svaret på problemet.
Några vanliga problem som löses med Divide and Conquers-algoritmer är Binär sökning , Sammanfoga sortering , Snabb sortering, Strassens matrismultiplikation , etc.
b) Dynamiska programmeringsalgoritmer :
Denna typ av algoritm är också känd som memoiseringsteknik för i detta är tanken att lagra det tidigare beräknade resultatet för att undvika att beräkna det om och om igen. I dynamisk programmering, dela upp det komplexa problemet i mindre överlappande delproblem och lagra resultatet för framtida bruk.
Följande problem kan lösas med algoritmen för dynamisk programmering Knapsäcksproblem , Viktad jobbschemaläggning , Floyd Warshall-algoritm , etc.
c) Girig algoritm :
I Greedy Algorithm byggs lösningen del för del. Beslutet att välja nästa del görs utifrån att det ger en omedelbar fördel. Den tar aldrig hänsyn till de val som hade gjorts tidigare.
Några vanliga problem som kan lösas genom den giriga algoritmen är Dijkstra Shortest Path Algoritm , Prims algoritm , Kruskals algoritm , Huffman-kodning , etc.
d) Backtracking-algoritm :
I Backtracking Algorithm löses problemet på ett inkrementellt sätt, det vill säga det är en algoritmisk teknik för att lösa problem rekursivt genom att försöka bygga en lösning stegvis, en bit i taget, och ta bort de lösningar som inte tillfredsställer problemets begränsningar. tidpunkt.
Några vanliga problem som kan lösas genom Backtracking Algorithm är Hamiltons cykel , M-färgningsproblem , N Queen Problem , Problem med råtta i labyrint , etc.
3. Randomiserad algoritm :
I den randomiserade algoritmen använder vi ett slumptal. Det hjälper till att avgöra det förväntade resultatet. Beslutet att välja det slumpmässiga numret så det ger den omedelbara fördelen
Några vanliga problem som kan lösas genom den randomiserade algoritmen är Quicksort: I Quicksort använder vi slumptalet för att välja pivot.
4. Sorteringsalgoritm :
Sorteringsalgoritmen används för att sortera data i kanske stigande eller fallande ordning. Den används också för att ordna data på ett effektivt och användbart sätt.
Några vanliga problem som kan lösas med hjälp av sorteringsalgoritmen är Bubbelsortering, infogningssortering, sammanslagningssortering, urvalssortering och snabbsortering är exempel på sorteringsalgoritmen.
5. Sökalgoritm :
Sökalgoritmen är den algoritm som används för att söka efter den specifika nyckeln i viss sorterad eller osorterad data. Några vanliga problem som kan lösas genom sökalgoritmen är binär sökning eller linjär sökning är ett exempel på en sökalgoritm.
6. Hashing-algoritm :
Hashingalgoritmer fungerar på samma sätt som sökalgoritmen men de innehåller ett index med ett nyckel-ID, dvs ett nyckel-värdepar. I hashing tilldelar vi en nyckel till specifik data.
Vissa vanliga problem kan lösas genom hashing-algoritmen vid lösenordsverifiering.