リスト探索

ウィキペディア小見出し辞書

リスト探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/15 03:07 UTC 版)

「探索」の記事における「リスト探索」の解説

線形探索 二分探索 内挿探索 リスト探索（英: list search）アルゴリズムは、おそらく最も基本的な探索アルゴリズムである。その目的は、リストから何らかのキーを持つ要素を探すことである。計算機科学では最もよく研究されている分野であり、それらのアルゴリズムの計算量もよく研究されている。 その中でも最も単純なアルゴリズムが線型探索であり、単純にリスト上の各要素を調べていく。その実行時間は O(n) であり、n はリスト上のアイテムの数だが、どんなリストでも適用可能である。 より洗練されたリスト探索アルゴリズムとして二分探索があり、実行時間は O(log n) である。データが多ければ多いほど線型探索よりも性能がよくなるが、探索の前にソートしておく必要があり、またランダムアクセスが可能でなければならない。 特別なデータ構造を使った別の探索法として、平衡2分探索木を使った探索があり、実行時間は二分探索と同様にO(log n) である。これは、二分探索の考え方を拡張して、挿入と削除を高速化できるようにしたものである。 内挿探索は分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる。 グローバーのアルゴリズムは量子コンピュータ用アルゴリズムで、ソートされていないリストでの線型探索に対して二乗の性能向上をもたらす。しかし、量子コンピュータはまだ実用化されていない。 ハッシュテーブルもリスト探索に使われ、実行時間は平均ケースでO(1)であるが、必要とする領域は他のデータ構造よりも多く、最悪ケースでは O(n) もかかる。リスト探索のデータ構造については、ハッシュテーブルも参照されたい。 なお、線型探索、二分探索、平衡2分探索木といったリスト探索アルゴリズムの多くは、若干のコスト追加で、与えられたキー以下（あるいは以上）の全ての値を探すことができる。このような探索を「範囲探索(英: range search)」と呼ぶ。例外はハッシュテーブルであり、そのような探索を効率的には行えない。