BitCell

Atunci când nu avem nici o informație privind elementele unui vector, dar știm că elementele respective pot fi comparate între ele, o modalitate directă de a căuta o valoare dorită într-un set ar fi printr-o parcurgere secvențială, directă a elementelor setului urmată de o compararea individuală cu valoarea căutată.

Astfel, ținând cont de convenția în notare stabilită, putem să creionăm următorul pseudocod :


În urma execuției logice a acestui pseudocod, variabila "găsit" ne va spune dacă sau nu elementul căutat "ș" se găsește în vectorul A.

Această abordare ne va spune dacă există un element dorit într-o listă, dar nu și unde. Pentru a afla și acest lucru este necesară o altă abordare pe care o evidențiem în cele ce urmează:



La sfârșitul secvenței, dacă "index găsire" va avea o valoare validă, atunci acea valoare va fi chiar poziția elementului căutat în cadrul vectorului inițial.

Lucrând cu informațiile introduse de smith în articolul său : Introducere în algoritmică, putem să exprimăm performanțele acestui algoritm în termeni de notație O. În acest sens facem observația că ciclul evocat de structura Pentru se va executa tot timpul de n ori (n fiind numărul de elemente a lui A). Prin urmare, performanța algoritmului este, după simplificare, mereu O(n). Un ordin nu prea bun pentru o operație de căutare într-un vector, așa cum vom vedea în comparație cu alte metode de căutare.

---

L.E. (-- 24 Jul 2011, 15:43 --)

Să continuăm această metodă, simplistă de altfel, de căutare cu o observație ce ne permite o șlefuire a performanței medii relative a algoritmului.

Vom face o observație asupra timpului mediu de găsire a unui element oarecare într-un eșantion de valori asupra căreia nu există nici o informație apriori. Am precizat timp de găsire și nu timp de parcurgere al eșantionului pentru a arăta faptul că o parcurgere integrală a valorilor nu mai este necesară de moment ce valoarea căutată a fost găsită.

Conform teoriei limite centrale, putem să concluzionăm că, în mediu, vom putea găsi o valoare într-un eșantion dat realizând n/2 comparații obținându-se, în lumina noilor prezumții, o complexitate de O(n/2). Se poate observa ușor că această teorie ne-a permis atingerea unei clase de complexitate de 2 ori mai rapide decât antecedenta valoare de O(n).

înarmați cu aceste calcule teoretice, pseudocodul suferă următoarele modificări (vom discuta de algoritmul care ne indică și poziția elementului căutat în vector pentru că acesta înglobează și rezultatul căutării : găsit/negăsit) :

Cam atât deocamdată,
Spor prieteni