分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

データ数がnの線形リストを先頭から探索する場合、最小探索回数は1回、最大探索回数はn回なので、目的のデータがある場合の平均探索回数はn＋12回です。一方、目的のデータが存在しない場合は、リストの最後まで検索することになるので探索回数は常にn回となります。

データが存在しない確率がaなので、データが存在する確率は(1－a)です。したがって、設問の探索処理における平均探索回数は、以下の2つを足し合わせた式で表すことができます。

対象がリストに存在する場合の平均探索回数×対象が存在する確率

n＋12×(1－a)

対象がリストに存在しない場合の探索回数×対象が存在しない確率

n×a

つまり、
　平均比較回数＝n＋12×(1－a)＋n×a
となり、この数式を整えると、(n＋1)(1－a)2＋na になります。