în programatori algoritmi de viață și structuri de date este subiectul cel mai important în cazul în care doresc să iasă în lumea de programare și fă niște bani. Astăzi, vom vedea ce fac și unde sunt folosite cu exemple mai simple. Această listă este pregătită ținând cont de utilizarea lor în programarea competitivă și practicile actuale de dezvoltare.

algoritmi de sortare

sortarea este conceptul cel mai intens studiat în informatică. Ideea este de a aranja elementele unei liste într-o anumită ordine. Deși fiecare limbaj de programare major are biblioteci de sortare încorporate, este util dacă știți cum funcționează. În funcție de cerința poate doriți să utilizați oricare dintre acestea.

• Merge Sort
• Quick Sort
• Bucket Sort
• Heap Sort
• numărarea Sort

mai important, ar trebui să știm când și unde să le folosim. Câteva exemple în care puteți găsi aplicarea directă a tehnicilor de sortare includ:

• sortarea după preț, popularitate etc. în site-urile de comerț electronic

algoritmi de căutare

Căutare binară (în structuri de date liniare)

căutarea binară este utilizată pentru a efectua o căutare foarte eficientă pe setul de date sortate. Complexitatea timpului este o (log2N). Ideea este de a împărți în mod repetat în jumătate porțiunea din listă care ar putea conține elementul, până când vom restrânge la un element posibil. Unele aplicații sunt:

• când căutați un nume de melodie într-o listă sortată de melodii, acesta efectuează căutarea binară și potrivirea șirurilor pentru a returna rapid rezultatele.
• folosit pentru a depana în git prin GIT bisect

adâncime/lățime prima Căutare (în structuri de date Grafic)

DFS și BFS sunt copac / grafic traversează și căutarea structuri de date. Nu am intra adânc în modul în care funcționează DFS/BFS, dar vom vedea cum sunt diferite prin animația următoare.

aplicații:

• folosit de motoarele de căutare pentru web-crawling
• folosit în inteligența artificială pentru a construi roboți, de exemplu un bot de șah
• Găsirea calea cea mai scurtă între două orașe într-o hartă și multe alte astfel de aplicații

Hashing

hash Lookup este în prezent cea mai utilizată tehnică pentru a găsi date adecvate prin cheie sau ID. Accesăm datele prin indexul său. Anterior ne-am bazat pe sortarea+Căutare binară pentru a căuta index, în timp ce acum folosim hashing.

structura de date este denumită Hash-Map sau hash-Table sau dicționar care mapează cheile la valori, în mod eficient. Putem efectua căutări de valoare folosind tastele. Ideea este de a utiliza o funcție hash adecvată care face cheia -> maparea valorii. Alegerea unei funcții hash bune depinde de scenariu.

Aplicații:

• în routere, pentru a stoca adresa IP- > pereche de căi pentru mecanismele de rutare
• pentru a efectua verificarea dacă o valoare există deja într-o listă. Căutarea liniară ar fi costisitoare. Putem folosi, de asemenea, Set structura de date pentru această operațiune.

Programare dinamică

Programare dinamică (DP) este o metodă pentru rezolvarea unei probleme complexe prin descompunerea acesteia în subprobleme mai simple. Rezolvăm subproblemele, ne amintim rezultatele lor și folosindu-le ne croim drum pentru a rezolva rapid problema complexă.

*scrie în jos „1+1+1+1+1+1+1+1 =” pe o foaie de hârtie * cu ce este egal?
*numărarea * opt!
*scrie un alt „1+” pe stânga* ce zici de asta?
*repede * nouă!
De unde ai știut că sunt nouă atât de repede?
Tocmai ai adaugat inca una
deci nu trebuia sa povestesti pentru ca ti-ai amintit ca erau opt! Programarea dinamică este doar un mod fantezist de a spune ‘amintirea lucrurilor pentru a economisi timp mai târziu’

aplicații:

• există mulți algoritmi și aplicații DP, dar aș numi unul și te-aș arunca în aer, metoda Duckworth-Lewis în cricket.

Exponențierea prin pătrat

spuneți că doriți să calculați 232. În mod normal, am repeta de 32 de ori și am găsi rezultatul. Ce se întâmplă dacă ți-am spus că se poate face în 5 iterații?

Exponențierea prin pătrat sau exponențierea binară este o metodă generală pentru calculul rapid al puterilor întregi pozitive mari ale unui număr în o(log2N). Nu numai aceasta, metoda este folosită și pentru calculul puterilor polinoamelor și matricilor pătrate.

aplicație:

• calculul puterilor mari ale unui număr este în mare parte necesar în criptarea RSA. RSA folosește, de asemenea, aritmetica modulară împreună cu exponențierea binară.

șir de potrivire și parsare

model de potrivire / căutarea este una dintre cele mai importante probleme în informatică. Au existat o mulțime de cercetări pe această temă, dar vom înrola doar două necesități de bază pentru orice programator.

algoritmul KMP (potrivirea șirurilor)

algoritmul Knuth-Morris-Pratt este utilizat în cazurile în care trebuie să potrivim un model scurt într-un șir lung. De exemplu, atunci când am Ctrl + F un cuvânt cheie într-un document, vom efectua model de potrivire în întregul document.

expresie regulată (String Parsing)

de multe ori trebuie să validăm un șir de parsare peste o restricție predefinită. Este foarte utilizat în dezvoltarea web pentru analiza și potrivirea adreselor URL.

algoritmi de testare a Primalității

există modalități deterministe și probabilistice de a determina dacă un anumit număr este prim sau nu. Vom vedea atât moduri deterministe, cât și probabiliste (nedeterministe).

sită de Eratostene (determinist)

dacă avem o anumită limită a intervalului de numere, să zicem determinați toate numerele prime în intervalul 100-1000 atunci Sita este o modalitate de a merge. Lungimea intervalului este un factor crucial, deoarece trebuie să alocăm o anumită cantitate de memorie în funcție de interval.

pentru orice număr n, testarea incrementală până la sqrt(n) (determinist)

în cazul în care doriți să verificați câteva numere care sunt slab răspândite pe o rază lungă de acțiune (să zicem de la 1 la 1012), Sieve nu va putea aloca suficientă memorie. Puteți verifica Fiecare număr n traversând doar până la sqrt (n) și efectuați o verificare a divizibilității pe n.

testul primalității Fermat și testul primalității Miller–Rabin (ambele sunt nedeterministe)

ambele sunt teste de compoziție. Dacă un număr este dovedit a fi compus, atunci sigur nu este un număr prim. Miller-Rabin este unul mai sofisticat decât cel al lui Fermat. de fapt, Miller-Rabin are și o variantă deterministă, dar apoi este un joc de comerț între complexitatea timpului și acuratețea algoritmului.

aplicație:

• cea mai importantă utilizare a numerelor prime este în criptografie. Mai precis ,ele sunt utilizate în criptare și decriptare în algoritmul RSA, care a fost prima implementare a Criptosistemelor cu cheie publică
• o altă utilizare este în funcțiile Hash utilizate în tabelele Hash