Čo je to algoritmus?
Algoritmus je krok za krokom postup na vyriešenie problému. Dobrý algoritmus by mal byť optimalizovaný z hľadiska času a priestoru. Rôzne typy problémov vyžadujú rôzne typy algoritmických techník, ktoré sa majú vyriešiť čo najoptimalizovanejším spôsobom. Existuje mnoho typov algoritmov, ale tie najdôležitejšie a najzákladnejšie algoritmy, ktoré musíte, sú popísané v tomto článku.
1. Algoritmus hrubej sily :
Toto je najzákladnejší a najjednoduchší typ algoritmu. Algoritmus hrubej sily je priamy prístup k problému, t. j. prvý prístup, ktorý nás napadne pri pohľade na problém. Technickejšie je to ako opakovanie všetkých dostupných možností na vyriešenie tohto problému.
Príklad:
ako zatvoriť režim vývojára
Ak je zablokovaný 4-miestny PIN. Číslice, ktoré sa majú vybrať od 0 do 9, potom bude hrubá sila skúšať všetky možné kombinácie jednu po druhej, napríklad 0001, 0002, 0003, 0004 atď., kým nezískame správny PIN. V najhoršom prípade to bude trvať 10 000 pokusov nájsť správnu kombináciu.
2. Rekurzívny algoritmus :
Tento typ algoritmu je založený na rekurzia . Pri rekurzii sa problém rieši rozdelením na podproblémy rovnakého typu a opakovaným volaním vlastného ja, kým sa problém nevyrieši pomocou základnej podmienky.
Niektoré bežné problémy, ktoré sa riešia pomocou rekurzívnych algoritmov, sú Faktoriál čísla , Séria Fibonacci , Hanojská veža , DFS pre graf , atď.
a) Algoritmus rozdeľuj a panuj :
V algoritmoch Divide and Conquer je cieľom vyriešiť problém v dvoch častiach, pričom prvá časť rozdeľuje problém na podproblémy rovnakého typu. Druhá časť je vyriešiť menší problém nezávisle a potom pridať kombinovaný výsledok, aby sa vytvorila konečná odpoveď na problém.
Niektoré bežné problémy, ktoré sa riešia pomocou algoritmov Divide and Conquers, sú Binárne vyhľadávanie , Zlúčiť triedenie , Rýchle triedenie, Strassenovo násobenie matice , atď.
b) Algoritmy dynamického programovania :
Tento typ algoritmu je známy aj ako memoizačná technika pretože v tomto je myšlienkou uložiť predtým vypočítaný výsledok, aby sa predišlo jeho opakovanému výpočtu. V dynamickom programovaní rozdeľte komplexný problém na menšie prekrývajúce sa čiastkové problémy a výsledok uložte pre budúce použitie.
Nasledujúce problémy možno vyriešiť pomocou algoritmu dynamického programovania Problém s batohom , Vážené plánovanie úloh , Algoritmus Floyda Warshalla , atď.
c) Chamtivý algoritmus :
V Greedy Algorithm je riešenie zostavené časť po časti. Rozhodnutie o výbere ďalšej časti sa robí na základe toho, že poskytuje okamžitý úžitok. Nikdy nezohľadňuje voľby, ktoré boli prijaté predtým.
Niektoré bežné problémy, ktoré možno vyriešiť pomocou algoritmu Greedy, sú Algoritmus najkratšej cesty Dijkstra , Primov algoritmus , Kruskalov algoritmus , Huffmanovo kódovanie , atď.
d) Algoritmus spätného sledovania :
V Backtracking Algorithm sa problém rieši prírastkovým spôsobom, t. j. ide o algoritmickú techniku rekurzívneho riešenia problémov, pri ktorej sa pokúšame postupne zostaviť riešenie, jeden kus po druhom, pričom sa odstránia tie riešenia, ktoré v žiadnom prípade nespĺňajú obmedzenia problému. časový bod.
Niektoré bežné problémy, ktoré možno vyriešiť pomocou algoritmu Backtracking, sú Hamiltonovský cyklus , Problém M-Coloring , Problém N Queen , Problém potkanov v bludisku , atď.
3. Randomizovaný algoritmus :
V randomizovanom algoritme používame náhodné číslo. Pomáha to rozhodnúť o očakávanom výsledku. Rozhodnutie vybrať si náhodné číslo tak dáva okamžitý úžitok
Niektoré bežné problémy, ktoré možno vyriešiť pomocou náhodného algoritmu, sú Quicksort: V Quicksort používame náhodné číslo na výber pivotu.
4. Algoritmus triedenia :
Algoritmus triedenia sa používa na triedenie údajov vo vzostupnom alebo zostupnom poradí. Používa sa tiež na usporiadanie údajov efektívnym a užitočným spôsobom.
Niektoré bežné problémy, ktoré možno vyriešiť pomocou triediaceho algoritmu, sú bublinové triedenie, vkladanie triedenia, zlučovacie triedenie, triedenie výberu a rýchle triedenie sú príklady triediaceho algoritmu.
5. Algoritmus vyhľadávania :
Vyhľadávací algoritmus je algoritmus, ktorý sa používa na vyhľadávanie konkrétneho kľúča v konkrétnych triedených alebo netriedených údajoch. Niektoré bežné problémy, ktoré možno vyriešiť pomocou vyhľadávacieho algoritmu, sú binárne vyhľadávanie alebo lineárne vyhľadávanie je jedným z príkladov vyhľadávacieho algoritmu.
6. Hašovací algoritmus :
Hašovacie algoritmy fungujú rovnako ako vyhľadávací algoritmus, ale obsahujú index s ID kľúča, t. j. pár kľúč – hodnota. Pri hashovaní priraďujeme kľúč ku konkrétnym údajom.
Niektoré bežné problémy možno vyriešiť pomocou hashovacieho algoritmu pri overovaní hesla.