Algoritmi de căutare

Când dorim să căutăm date, diferența dintre o aplicație rapidă și una mai lentă constă în utilizarea precisă a algoritmului de căutare. Algoritmul de căutare este un pas de bază, fundamental în calcul, realizat prin metode de localizare a anumitor date dintr-o colecție mai mare de date. Toți algoritmii de căutare folosesc o cheie de căutare pentru a duce la capăt procedura. Rezultatul căutării se așteaptă a fi o stare de succes sau de eșec, în valoare booleană adevărată sau falsă. În informatică, există diverse tipuri de algoritmi de căutare disponibili, iar modul în care sunt utilizați decide performanța și eficiența programelor.

Un algoritm este o procedură/ o secvență de pași care rezolvă o problemă dată într-un mod repetabil și cu resurse (timp și memorie) finite; primește un set de date de intrare și returnează o soluție – set de date de ieșire.

Un algoritm de căutare este orice algoritm care rezolvă problema căutării, și anume, preluarea de  informații stocate în cadrul unei structuri de date, sau calculate în spațiul de căutare al unui domeniu de problemă, fie cu valori discrete, fie continue. Algoritmii de căutare sunt proiectați pentru a verifica sau a prelua un element din orice structură de date în care este stocat. Aceste operațiuni dau unul dintre cele două rezultate posibile - Succes sau Eșec, adică „Succes” când ținta este găsită și „Eșec” când ținta nu este găsită.

Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare pentru execuția algoritmului. Prin resurse se înțelege:

• Spațiul de memorie necesar pentru stocarea datelor pe care le prelucrează algoritmul. 
• Timpul necesar pentru execuția tuturor prelucrărilor specificate în algoritm.

Această analiză este utilă pentru a stabili dacă un algoritm utilizează un volum acceptabil de resurse pentru rezolvarea unei probleme. În acest fel timpul de execuție va fi exprimat prin numărul de operații elementare executate. Sunt considerate operații elementare cele aritmetice (adunare, scădere, înmulțire, împărțire), comparațiile și cele logice (negație, conjuncție și disjuncție). Este așadar suficient să se contorizeze doar operațiile elementare, cele de bază. Timpul de execuție al întregului algoritm se obține însumând timpii de execuție ai prelucrărilor componente.

Pentru a obține timpul de execuție al unui algoritm, în informatică este folosită notația Big O. În teoria analitică a numerelor⁠, notația Big O este adesea folosită pentru a exprima o legătură între diferența dintre o funcție aritmetică⁠ și o aproximare mai bine înțeleasă; un exemplu celebru de astfel de diferență este termenul rest din teorema numerelor prime. Notația Big O caracterizează funcțiile după vitezele lor de creștere: funcții diferite cu aceeași viteză de creștere pot fi reprezentate folosind aceeași notație O. Litera “O” este folosită deoarece viteza de creștere a unei funcții este numită și ordin al funcției. O descriere a unei funcții în ceea ce privește notația Big O, de obicei, oferă doar o limită superioară⁠ a vitezei de creștere a funcției.

Notația nu determină durata absolută a unui algoritm, ci doar pe cea relativă. De exemplu, în cazul lui O(1), această definire nu înseamnă că programul durează o milisecundă, o secundă sau un timp foarte mic, ci arată că indiferent de mărimea datelor, algoritmul este constant și va dura la fel, chiar dacă este vorba de un singur element sau un milion. Evident, în cele mai multe cazuri durata este una foarte mică, dar trebuie să ținem cont că acest lucru nu este literă de lege. Spre exemplu, o funcție de criptare poate dura câteva minute indiferent de ce mesaj este criptat, algoritmul având complexitate O(1).

Structura de date este un mod de a organiza și stoca o colecție de date pentru a facilita manipularea lor, cum ar fi accesul/ modificarea, adăugarea, ștergerea, găsirea unui element sau  sortarea colecției. Deseori o alegere bine făcută a structurii de date va permite și implementarea unui algoritm eficient. Structura de date aleasă este derivată de multe ori dintr-un tip de dată abstract. O structură de date bine concepută permite efectuarea varietății operațiilor de bază, utilizând puține resurse, ca de exemplu memoria necesară și timpul de execuție. Structurile de date se implementează utilizând tipuri de date, referințe și operații asupra acestora, toate facilitate de către un limbaj de programare.

Există anumite tipuri de structuri de date care sunt foarte specializate pe anumite sarcini/aplicații. De exemplu, arborii B sunt foarte potriviți pentru implementarea bazelor de date, în timp ce tabelele de rutare se folosesc îndeosebi pentru interconectarea elementelor din rețelele de calculatoare. În designul multor tipuri de programe, alegerea structurii de date este principalul obiectiv al specificațiilor de implementare. Experiența în construirea sistemelor informatice mari a arătat că dificultatea implementării, precum și calitatea și performanța produsului final depind în mare măsură de alegerea structurilor de date. Dacă tipurile de structuri de date au fost alese în mod avantajos, algoritmii ce vor trebui utilizați devin de multe ori aproape evidenți. Câteodată însă situația este mai complicată; atunci structurile de date sunt alese pe baza necesităților sarcinilor cheie.

Din cauză că structurile de date au o importanță atât de mare

, multe dintre ele sunt incluse în bibliotecile standard ale multor limbaje de programare și medii de dezvoltare, cum ar fi 

Standard Template Library

 pentru C++, sau 

Java Collections Framework

. Elementele fundamentale pentru construirea structurilor de date sunt 

vectorii, înregistrările, structurile de tip uniune (union), și referințele

. De exemplu, referința invalidabilă, o referință ce poate conține valoarea „nulă” (zero), este o combinație de referințe și structuri de tip „uniune”, iar cel mai simplu model de structură de date înlănțuite, 

lista simplu înlănțuită

, este construită din înregistrări și referințe invalidabile. Structurile de date reprezintă implementări ale unor interfețe: o structură de date poate fi văzută ca o interfață între două funcții sau ca o implementare a metodelor de accesare a depozitului care este organizat în concordanță cu tipul de dată asociat.