Finger search とは

コンピュータ科学では、データ構造上の指検索は、データ構造内の要素への参照(指)がクエリと共に与えられる、構造がサポートするあらゆる検索操作の拡張である。要素の検索時間は、データ構造内の要素の数の関数として最も頻繁に表されるが、指の検索時間は、要素と指との間の距離の関数である。
n要素の集合では、2つの要素xとyの間の距離d(x、y)(または単に曖昧でないときはd)はランクの差です。 xとyが構造内のi番目とj番目に大きい要素である場合、ランクの差は| i – j |です。ある構造の通常の探索が通常O(f(n))時間かかる場合、指yを用いたxの指探索は理想的にはO(f(d))時間を取るべきである。 d≤nであるため、最悪の場合、指探索は通常の探索と同じくらい悪いことになる。しかしながら、実際には、これらの縮退フィンガーサーチは、通常のサーチよりも多く働く。例えば、f(n)がlog(n)であり、フィンガーサーチが最悪の場合の通常サーチの2倍の比較を行う場合、d>√nのときフィンガーサーチは遅くなる。したがって、指の探索は、ターゲットが実際に指に近づくと合理的に予想できる場合にのみ使用してください。