Hvad er en algoritme?
En algoritme er en trin-for-trin procedure til at løse et problem. En god algoritme bør optimeres med hensyn til tid og rum. Forskellige typer problemer kræver forskellige typer af algoritmiske teknikker for at blive løst på den mest optimerede måde. Der er mange typer algoritmer, men de vigtigste og mest grundlæggende algoritmer, som du skal, diskuteres i denne artikel.
1. Brute Force Algoritme :
Dette er den mest grundlæggende og enkleste type algoritme. En Brute Force Algorithm er den ligefremme tilgang til et problem, dvs. den første tilgang, vi tænker på, når vi ser problemet. Mere teknisk er det ligesom at gentage alle tilgængelige muligheder for at løse det problem.
Eksempel:
Hvis der er en lås med 4-cifret PIN-kode. Cifrene, der skal vælges fra 0-9, så vil råstyrken prøve alle mulige kombinationer én efter én som 0001, 0002, 0003, 0004, og så videre, indtil vi får den rigtige PIN-kode. I værste fald vil det tage 10.000 forsøg at finde den rigtige kombination.
2. Rekursiv algoritme :
Denne type algoritme er baseret på rekursion . Ved rekursion løses et problem ved at bryde det op i delproblemer af samme type og kalde sit eget jeg igen og igen, indtil problemet er løst ved hjælp af en grundbetingelse.
Nogle almindelige problemer, der løses ved hjælp af rekursive algoritmer, er Faktoriel af et tal , Fibonacci-serien , Hanois tårn , DFS til Graph , etc.
e-r model diagram
en) Divide and Conquer-algoritme :
I Divide and Conquer algoritmer er tanken at løse problemet i to afsnit, det første afsnit deler problemet op i delopgaver af samme type. Det andet afsnit er at løse det mindre problem uafhængigt og derefter tilføje det kombinerede resultat for at producere det endelige svar på problemet.
Nogle almindelige problemer, der løses ved hjælp af Divide and Conquers-algoritmer, er Binær søgning , Flet sortering , Hurtig sortering, Strassens Matrix Multiplikation , etc.
b) Dynamiske programmeringsalgoritmer :
Denne type algoritme er også kendt som husketeknik fordi det her er tanken at gemme det tidligere beregnede resultat for at undgå at beregne det igen og igen. I dynamisk programmering skal du opdele det komplekse problem i mindre overlappende delproblemer og gem resultatet til fremtidig brug.
Følgende problemer kan løses ved hjælp af den dynamiske programmeringsalgoritme Rullesæk problem , Vægtet jobplanlægning , Floyd Warshall algoritme , etc.
teske vs spiseske
c) Grådig algoritme :
I Greedy Algorithm er løsningen bygget del for del. Beslutningen om at vælge næste del sker ud fra, at det giver en umiddelbar fordel. Den tager aldrig hensyn til de valg, der var blevet taget tidligere.
Nogle almindelige problemer, der kan løses gennem Greedy Algorithm er Dijkstra Shortest Path Algoritme , Prims algoritme , Kruskals algoritme , Huffman kodning , etc.
d) Tilbagesporingsalgoritme :
I Backtracking Algorithm løses problemet på en trinvis måde, dvs. det er en algoritmisk teknik til at løse problemer rekursivt ved at forsøge at bygge en løsning trinvist, et stykke ad gangen, og fjerne de løsninger, der ikke på nogen måde opfylder problemets begrænsninger. tidspunkt.
Nogle almindelige problemer, der kan løses gennem Backtracking-algoritmen, er Hamiltonsk cyklus , M-farveproblem , N Queen Problem , Rotte i labyrint-problem , etc.
3. Randomiseret algoritme :
I den randomiserede algoritme bruger vi et tilfældigt tal. Det hjælper med at bestemme det forventede resultat. Beslutningen om at vælge det tilfældige tal, så det giver den umiddelbare fordel
Nogle almindelige problemer, der kan løses gennem den randomiserede algoritme, er Quicksort: I Quicksort bruger vi det tilfældige tal til at vælge pivot.
4. Sorteringsalgoritme :
Sorteringsalgoritmen bruges til at sortere data i måske stigende eller faldende rækkefølge. Det bruges også til at arrangere data på en effektiv og brugbar måde.
Nogle almindelige problemer, der kan løses gennem sorteringsalgoritmen, er boblesortering, indsættelsessortering, flettesortering, udvælgelsessortering og hurtig sortering er eksempler på sorteringsalgoritmen.
5. Søgealgoritme :
Søgealgoritmen er den algoritme, der bruges til at søge efter den specifikke nøgle i bestemte sorterede eller usorterede data. Nogle almindelige problemer, der kan løses gennem søgealgoritmen, er binær søgning eller lineær søgning er et eksempel på en søgealgoritme.
6. Hashing-algoritme :
Hashing-algoritmer fungerer på samme måde som søgealgoritmen, men de indeholder et indeks med et nøgle-id, dvs. et nøgle-værdi-par. I hashing tildeler vi en nøgle til specifikke data.
Nogle almindelige problemer kan løses gennem hashing-algoritmen i adgangskodebekræftelse.