探索アルゴリズムの平均比較回数とは？

探索アルゴリズムの平均比較回数とは、探索方式の性能を、データ件数nに対する比較回数の期待値として求める考え方。すべての要素が等確率で探索対象になる前提では、線形探索は約(n+1)/2回、二分探索は約log₂n回、ハッシュ表は衝突が無ければ約1回となる。応用情報では計算問題として頻出。

たんさくあるごりずむのへいきんひかくかいすう

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）

探索アルゴリズムの平均比較回数の意味

探索方式の性能を、データ件数nに対する比較回数の期待値として求める考え方。すべての要素が等確率で探索対象になる前提では、線形探索は約(n+1)/2回、二分探索は約log₂n回、ハッシュ表は衝突が無ければ約1回となる。応用情報では計算問題として頻出。

n=1,000,000なら線形探索は平均50万回、二分探索は約20回。ただし二分探索には整列が前提で、整列コストはO(n log n)かかる。1回しか探索しないなら整列せず線形探索、何度も探索するなら整列して二分探索、という判断につながる。

「探索が失敗する場合」の比較回数は成功時と異なり、線形探索では常にn回になる。問題文が成功時の平均を問うているのか、最悪や失敗時を問うているのかを読み違えると答えがずれる。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。