Problém vyhľadávania

Zisťovanie všetkých objektov v dátovom súbore, spĺňajúcich určitú podmienku – kritérium vyhľadávania.
Vyhľadávanie v zozname prvkov je jeden zo základných vyhľadávacích algoritmov. Cieľ je nájsť umiestnenie prvku množiny podľa určitého kľúča.

^ TOP

Algoritmy

Najjednoduchší vyhľadávací algoritmus je sekvenčné vyhľadávanie, ktoré postupne skontroluje každý prvok. Má časovú zložitosť O(n), kde je n počet prvkov.
Rýchlejšie je binárne vyhľadávanie, s časovou zložitosťou O(log n), predpokladá sa ale utriedený vstupný dátový súbor.
Hašovacie tabuľky sa tiež používajú na vyhľadávanie. V priemernom čase potebujú na vyhľadanie konštantný čas, ale potrebujú veľa pamäte a v najhoršom prípade až O(n) času na vyhľadanie.
Ďalšími dátovými štruktúrami zameranými na rýchle vyhľadávanie sú samovyvažovacie vyhľadávacie stromy. Čas potrebný na nájdenie prvku je O(log n) a s určitými úpravami sa dajú zlepšiť aj časy vkladania a mazania prvkov.

Problém vyhľadávania sa dá modifikovať aj na nájdenie všetkých prvkov väčších (menších) ako hľadaný prvok.
Implemetácia v sekvenčnom vyhľadávaní, binárnom vyhľadávaní a v stromoch je triviálna. Toto ale nie je možné pri hašovacích tabuľkách.

^ TOP

Metódy

Rozlišuje sa medzi vnútornými a vonkajšími metódami vyhľadávania. Pri vnútorných metódach sa predpokladá, že celý dátový súbor je v operačnej pamäti. Ak sa prevažná časť dátového súboru počas vyhľadávania nachádza v externej pamäti, hovoríme o vonkajšom vyhľadávaní. Typickými vnútornými metódami vyhľadávania sú sekvenčné vyhľadávanie, binárne vyhľadávanie a vyhľadávanie v binárnych stromoch. Vyhľadávanie v B-stromoch a hašovanie sú prevažne vonkajšie metódy.

^ TOP