TIN066 Vyhledávání v setříděné posloupnosti
Množina S je reprezentována v setříděném poli A (délky n), hledáme daný prvek; mám kraje d, h, vím, že hledaný prvek x je $ A[d] \le x \le A[h] $. Kraje postupně přibližuji k sobě, když se potkají, našel jsem prvek.
Zaveďme si pomocnou operaci NEXT, ta vrátí novou hodnotu kraje (kterého? snadno poznáme porovnáním). Podle konkrétní podoby NEXT rozlišujeme několik druhů vyhledávání:
- unární: NEXT := d+1. Prostě jedeme popořadě, očekávaný počet dotazů je n/2, ale nejhorší n, tedy to trvá $ O(n) $.
- binární: NEXT := $ \left\lceil {d+h \over 2} \right\rceil $. Půlíme interval. Očekávaný i nejhorší počet dotazů je $ O(\log n) $.
- interpolační: NEXT := $ d + \left\lceil(h - d){x - A[d] \over A[h] - A[d]}\right\rceil $. Přes kraje protáhneme přímku a píchneme tam, kde by na ní mělo být x. Očekávaný počet dotazů je kdovíproč $ O(\log \log n) $ (nedokazuje se), nejhorší $ O(n/2) $.
Zobecněné kvadratické vyhledávání
...je taková strašlivá zdivočelost. Chtěli bychom zkombinovat binární a interpolační vyhledávání tak, abychom měli pěknou očekávanou i nejhorší složitost. Myšlenka spočívá v tom, že si vždy v našem rozsahu interpolačním dotazem vytyčíme výchozí bod hledání, postavíme velikost unárního skoku $ c=\sqrt{h-d+1} $, a z výchozího bodu pak střídavě putujeme binárními a unárními dotazy ve směru x, dokud není unární skok větší než velikost úseku - v té chvíli znovu položíme interpolační dotaz, atd.
Co na to složitost? V nejhorším případě se rozdíl h-d sníží na polovinu během tří kroků, to znamená $ O(\log n) $. Očekávaná složitost je očekávaný počet intepolačních dotazů krát očekávaný počet dotazů v jednom interpolačním kroku. To prvé již víme že je $ O(\log \log n) $, ukazuje se, že to druhé je konstantní! Takže očekávaná složitost je $ O(\log \log n) $.
Idea konstantnosti: Zjistíme, že počet prvků na začátku úseku menších než x sleduje binomické rozdělení; známe i jeho rozptyl atd., tedy můžeme použít Čebyševovu nerovnost, ta nám dá řadu $ 1/i^2 $, jejíž součet je z analýzy konečný.
