Co je to algoritmus?

Algoritmus je postup krok za krokem k vyřešení problému. Dobrý algoritmus by měl být optimalizován z hlediska času a prostoru. Různé typy problémů vyžadují různé typy algoritmických technik, které mají být řešeny co nejoptimálnějším způsobem. Existuje mnoho typů algoritmů, ale nejdůležitější a základní algoritmy, které musíte, jsou popsány v tomto článku.

1. Algoritmus hrubé síly :

Toto je nejzákladnější a nejjednodušší typ algoritmu. Algoritmus hrubé síly je přímý přístup k problému, tedy první přístup, který nás napadne, když vidíme problém. Technicky je to jako opakování všech dostupných možností k vyřešení tohoto problému.

Příklad:

Pokud je zámek 4místný PIN. Číslice, které mají být vybrány od 0 do 9, pak bude hrubá síla zkoušet všechny možné kombinace jednu po druhé, jako je 0001, 0002, 0003, 0004, a tak dále, dokud nezískáme správný PIN. V nejhorším případě bude hledání správné kombinace trvat 10 000 pokusů.

2. Rekurzivní algoritmus :

Tento typ algoritmu je založen na rekurze . V rekurzi se problém řeší rozdělením na podproblémy stejného typu a opakovaným voláním vlastního já, dokud není problém vyřešen pomocí základní podmínky.
Některé běžné problémy, které se řeší pomocí rekurzivních algoritmů, jsou Faktoriál čísla , Řada Fibonacci , Hanojská věž , DFS pro graf , atd.

A) Algoritmus rozděl a panuj :

V algoritmech Divide and Conquer je myšlenkou vyřešit problém ve dvou částech, první část rozděluje problém na podproblémy stejného typu. Druhá část je samostatně vyřešit menší problém a poté přidat kombinovaný výsledek, aby se vytvořila konečná odpověď na problém.
Některé běžné problémy, které se řeší pomocí algoritmů Divide and Conquers, jsou Binární vyhledávání , Sloučit třídění , Rychlé řazení, Strassenovo násobení matice , atd.

b) Algoritmy dynamického programování :

Tento typ algoritmu je také známý jako technika zapamatování protože v tomto je myšlenkou uložit dříve vypočítaný výsledek, aby se zabránilo jeho opakovanému výpočtu. V dynamickém programování rozdělte komplexní problém na menší překrývající se dílčí problémy a výsledek uložte pro budoucí použití.
Následující problémy lze vyřešit pomocí algoritmu dynamického programování Problém s batohem , Vážené plánování úloh , Algoritmus Floyda Warshalla , atd.

C) Chamtivý algoritmus :

V Greedy Algorithm je řešení sestavováno část po části. Rozhodnutí o výběru další části se provádí na základě toho, že poskytuje okamžitý užitek. Nikdy nezohledňuje volby, které byly učiněny dříve.
Některé běžné problémy, které lze vyřešit pomocí Greedy Algorithm, jsou Algoritmus nejkratší cesty Dijkstra , Primův algoritmus , Kruskalův algoritmus , Huffmanovo kódování , atd.

d) Algoritmus zpětného sledování :

V Backtracking Algorithm je problém řešen inkrementálním způsobem, tj. je to algoritmická technika pro rekurzivní řešení problémů tím, že se pokouší sestavit řešení postupně, jeden kus po druhém, přičemž se odstraní ta řešení, která v žádném případě nesplňují omezení problému. časový bod.
Některé běžné problémy, které lze vyřešit pomocí algoritmu Backtracking, jsou Hamiltonovský cyklus , Problém M-Coloring , Problém N Queen , Problém krysy v bludišti , atd.

3. Randomizovaný algoritmus :

V randomizovaném algoritmu používáme náhodné číslo. To pomáhá rozhodnout o očekávaném výsledku. Rozhodnutí zvolit náhodné číslo tak dává okamžitý užitek
Některé běžné problémy, které lze vyřešit pomocí náhodného algoritmu, jsou Quicksort: V Quicksort používáme náhodné číslo pro výběr pivotu.

4. Algoritmus řazení :

Algoritmus řazení se používá k řazení dat ve vzestupném nebo sestupném pořadí. Používá se také k efektivnímu a užitečnému uspořádání dat.
Některé běžné problémy, které lze vyřešit pomocí třídícího algoritmu, jsou bublinové třídění, vkládání třídění, slučovací třídění, výběrové třídění a rychlé třídění jsou příklady třídícího algoritmu.

5. Algoritmus hledání :

Vyhledávací algoritmus je algoritmus, který se používá pro vyhledávání konkrétního klíče v konkrétních setříděných nebo netříděných datech. Některé běžné problémy, které lze vyřešit pomocí vyhledávacího algoritmu, jsou binární vyhledávání nebo lineární vyhledávání je jedním z příkladů vyhledávacího algoritmu.

6. Hašovací algoritmus :

Hašovací algoritmy fungují stejně jako vyhledávací algoritmus, ale obsahují index s ID klíče, tj. pár klíč-hodnota. V hashování přiřadíme klíč konkrétním datům.
Některé běžné problémy lze vyřešit pomocí hashovacího algoritmu při ověřování hesla.