27a - Vyhľadávanie

pojmy:

• prístupová doba - čas od okamihu keď mám daný kľúč do momentu keď sa jednoznačne dozviem, či bol nájdený alebo nie
• minimálna doba hľadania
•  maximálna doba hľadania
• priemerná doba hľadania
•  doba úspešného a neúspešného hľadania

klasifikácia:

• vyhľadávanie v dátovej štruktúre s priamym prístupom
• vyhľadávanie v dátovej štruktúre so sekvenčným prístupom

Základná štruktúra vyhľadávacieho algoritmu:

bool Nasel = false;
while (!(nasel && <množina prvků není vyčerpána>))
{
 //prozkoumej další prvek, a je-li to hledaný, nastav Nasel na true
} //while
bool Search = Nasel;

1. Pre vyhľadávanie potrebujeme reláciu „rovnosť“ nad typom, ktorý predstavuje kľúč.
2. Pre vyhľadávanie v zoradenom poli potrebujeme aj reláciu „usporiadanie“.

Sekvenčné vyhľadávanie v nezoradenom poli:

• intuitívna metóda, prechádzame pole až kým nenarazíme na hľadaný prvok, alebo kým neprídeme na koniec poľa.
• najhorší prípad - je daný hodnotou N
• najlepší prípad - hodnota 1
• priemerná doba hľadania - N/2
• čas neúspešného hľadania - N
• najrýchlejšie sú nájdené položky na začiatku poľa
• časová zložitosť = N

Vyhľadávanie so zarážkou:

• na koniec poľa vložím pred začiatkom hľadania položku s kľúčom, ktorý hľadám
• umožňuje vynechať test na koniec poľa ⇒ algoritmus sa zrýchli
• treba na konci zistiť či sme našli položku alebo len zarážku
• efektívna veľkosť poľa sa znižuje o jeden prvok
• časová zložitosť = N

• nevýhoda - treba stále udržiavať pole zoradené (pri vkladaní, rušení prvku)

Sekvenčné vyhľadávanie v zoradenom poli:

• musí byť definovaná relácia „usporiadanie“
• hľadanie končí keď narazí na položku, ktorej kľúč je rovný alebo vyšší ako hľadaný kľúč
• vyhľadávanie sa zrýchli len pri neúspešnom vyhľadávaní
• časová zložitosť = N

Vyhľadávanie v poli zoradenom podľa počtu vyhľadávaní:

• zoradenie poľa tak, aby najčastejšie hľadané položky boli na jeho začiatku (napr. občasným zoradením položiek podľa počtu vyhľadávaní danej položky)
• varianta „Vyhľadávanie s adaptívnou rekonfiguráciou poľa podľa počtu vyhľadávaní“:
  • po každom prístupe k položke sa položka vymení so svojim ľavým susedom (ak už sama nie je na prvej pozícii)
• časová zložitosť = N

Binárne vyhľadávanie:

• prevádza sa nad zoradeným poľom
• jedna z najýchlejších metód v zmysle, že zaručuje krátke vyhľadávanie v najhoršom prípade
• podobné ako metóda „pulení intervalu“
• princíp: ak je hľadaný prvok väčší ako prvý prvok a meší ako posledný prvok, pozrieme sa na stredný, ak je ten väčší tak na stred intervalu <1, N/2>, atď
• stred = (ľavý + pravý) / 2
• zvlášť výhodné pre statické tabuľky, kde nie je treba posun segmentu poľa
• Insert a Delete majú rovnaký charakter ako pri sekvenčnom vyhľadávaní v zoradenom poli
• treba vedieť napísať algoritmus pri štátniciach
• časová zložitosť = log2(N)

left:=1; (* levý index *)
right:=n; (* pravý index *)
 
repeat
  middle:=(left+right) div 2;
  if K < Tab[middle].Klic
    then right:=middle - 1 (* hledaná položka je v levé polovině *)
  else left:= middle +1; (* hledaná položka je v pravé polovině *)
until (K=Tab[middle].Klic) or (right < left);
 
Search:= K=Tab[middle].Klic;

Dijkstrova varianta binárneho vyhľadávania:

• nepoužíva sa v klasických vyhľadávacích tabuľkách, lebo porušuje pravidlo vyhľadávacej tabuľky (2 prvky majú rovnaký kľúč)
• vychádza z predpokladu, že v zoradenom poli je viac položiek s rovnakým kľúčom
• hľadá posledný prvok z rovnakých prvkov (skončí keď je v rade rovnakých prvkov a narazí už na väčší prvok)
• zvlášť výhodné pre statické tabuľky, kde nie je treba posun segmentu poľa
• Insert a Delete majú rovnaký charakter ako pri sekvenčnom vyhľadávaní v zoradenom poli
• najhorší prípad uspešného aj neúspešného vyhľadávanie - log(n) - rozdiel oproti „klasickému“ binárnemu
• „dobře se zkouší a já to velice rád používám“
• časová zložitosť - log2(N)

Uniformné binárne vyhľadávanie:

• pulení je v niektorých PC časovo náročné ⇒ stráca sa výhoda rýchlosti pulení
• princíp - vytvorenie tabuľky, v ktorej sú indexy polovíc - myšlienka „dopredu si to spočítam a potom to budem používať“
• „uniformní“ - lebo sa vytvára tabuľka odchýliek (na jednej úrovni sú rovnaké odchýlky)
• Sharova metóda:
  • zvolíme nejaké N
  • ak je hľadaný prvok menší ako N, hľadáme v časti <1, N>
  • ak je daný prvok väčší ako N, posunieme si začiatok do N a pokračujeme s časťou <N, 2*N> (prakticky znížim hodnotu všetkých prvkov väčších ako N o hodnotu N a tým pádom robím s rovnakými číslami) atď
• časová zložitosť - log2(N)

Fibonacciho vyhľadávanie:

• je založená na Fibonacciho postupnosti
• Fibonacciho strom (obrázok)
• delenie intervalu podľa Fibonacciho stromu - napr. pre 12 prvkov začnem na indexe 8 (viď obrázok)
• Sharova metóda - viď v „Uniformné bin. vyhľadávanie“
• časová zložitosť - log(N)