Ce este un algoritm?

Un algoritm este o procedură pas cu pas pentru a rezolva o problemă. Un algoritm bun ar trebui optimizat în termeni de timp și spațiu. Diferite tipuri de probleme necesită diferite tipuri de tehnici algoritmice pentru a fi rezolvate în cel mai optimizat mod. Există multe tipuri de algoritmi, dar cei mai importanți și fundamentali algoritmi pe care trebuie să-i fie sunt discutați în acest articol.

ora cinei vs cină

1. Algoritmul de forță brută :

Acesta este cel mai simplu și cel mai simplu tip de algoritm. Un algoritm de forță brută este abordarea simplă a unei probleme, adică prima abordare care ne vine în minte când vedem problema. Mai mult din punct de vedere tehnic, este ca și cum ați repeta fiecare posibilitate disponibilă pentru a rezolva această problemă.

Exemplu:

Dacă există o blocare a codului PIN din 4 cifre. Cifrele care urmează să fie alese de la 0 la 9, apoi forța brută va încerca toate combinațiile posibile una câte una, cum ar fi 0001, 0002, 0003, 0004 și așa mai departe până când obținem PIN-ul corect. În cel mai rău caz, va fi nevoie de 10.000 de încercări pentru a găsi combinația potrivită.

2. Algoritm recursiv :

Acest tip de algoritm se bazează pe recursiunea . În recursivitate, o problemă este rezolvată prin împărțirea ei în subprobleme de același tip și apelând din nou și din nou propriul sine până când problema este rezolvată cu ajutorul unei condiții de bază.
Unele probleme comune care sunt rezolvate folosind algoritmi recursivi sunt Factorial al unui număr , Seria Fibonacci , Turnul din Hanoi , DFS pentru Graph , etc.

A) Algoritmul Divide and Conquer :

În algoritmii Divide and Conquer, ideea este de a rezolva problema în două secțiuni, prima secțiune împarte problema în subprobleme de același tip. A doua secțiune este de a rezolva problema mai mică în mod independent și apoi de a adăuga rezultatul combinat pentru a produce răspunsul final la problemă.
Unele probleme comune care sunt rezolvate folosind algoritmii Divide and Conquers sunt Căutare binară , Merge Sort , Sortare rapida, Înmulțirea matricei a lui Strassen , etc.

b) Algoritmi de programare dinamică :

Acest tip de algoritm este cunoscut și sub numele de tehnica de memorare deoarece în aceasta ideea este de a stoca rezultatul calculat anterior pentru a evita calcularea lui din nou și din nou. În programarea dinamică, împărțiți problema complexă în mai mici subprobleme suprapuse și stocați rezultatul pentru utilizare ulterioară.
Următoarele probleme pot fi rezolvate folosind algoritmul de programare dinamică Problemă la rucsac , Programarea ponderată a locurilor de muncă , Algoritmul Floyd Warshall , etc.

c) Algoritmul lacom :

În algoritmul Greedy, soluția este construită parte cu parte. Decizia de a alege următoarea parte se face pe baza faptului că oferă un beneficiu imediat. Nu ia în considerare niciodată alegerile care au fost luate anterior.
Unele probleme comune care pot fi rezolvate prin algoritmul Greedy sunt Algoritmul Dijkstra cea mai scurtă cale , Algoritmul lui Prim , Algoritmul lui Kruskal , Codarea Huffman , etc.

d) Algoritmul de backtracking :

În Backtracking Algorithm, problema este rezolvată într-un mod incremental, adică este o tehnică algoritmică pentru rezolvarea problemelor recursiv, încercând să construiască o soluție în mod incremental, o bucată la un moment dat, eliminând acele soluții care nu reușesc să satisfacă constrângerile problemei. punct de timp.
Unele probleme comune care pot fi rezolvate prin intermediul algoritmului de backtracking sunt Ciclul Hamiltonian , Problema M-Colorare , Problema N Queen , Problema șobolanului în labirint , etc.

3. Algoritm randomizat :

În algoritmul randomizat, folosim un număr aleator. Acesta ajută la deciderea rezultatului așteptat. Decizia de a alege numărul aleatoriu astfel încât să ofere beneficii imediate
Câteva probleme comune care pot fi rezolvate prin algoritmul randomizat sunt Quicksort: În Quicksort folosim numărul aleator pentru selectarea pivotului.

4. Algoritm de sortare :

Algoritmul de sortare este folosit pentru a sorta datele în ordine crescătoare sau descrescătoare. De asemenea, este folosit pentru aranjarea datelor într-un mod eficient și util.
Unele probleme comune care pot fi rezolvate prin intermediul algoritmului de sortare sunt sortarea cu bule, sortarea prin inserare, sortarea prin îmbinare, sortarea prin selecție și sortarea rapidă sunt exemple ale algoritmului de sortare.

5. Algoritm de căutare :

Algoritmul de căutare este algoritmul care este utilizat pentru căutarea unei chei specifice, în special în date sortate sau nesortate. Unele probleme comune care pot fi rezolvate prin intermediul algoritmului de căutare sunt căutarea binară sau căutarea liniară este un exemplu de algoritm de căutare.

6. Algoritmul de hashing :

Algoritmii de hashing funcționează la fel ca algoritmul de căutare, dar conțin un index cu un ID cheie, adică o pereche cheie-valoare. În hashing, atribuim o cheie unor date specifice.
Unele probleme obișnuite pot fi rezolvate prin intermediul algoritmului de hashing în verificarea parolei.