平成24年度春期 応用情報技術者試験 午前 問9

正解：イ

AI解説

n 個のデータを m 個ずつのブロックに分けるとブロック数は n/m 個である。第1段階では各ブロック最後尾を線形探索するので平均比較回数は約 (n/m)÷2=n/2m 回、第2段階では m 個のブロック内を線形探索するので平均約 m/2 回である。合計すると m/2+n/2m となりイが正しい。線形探索の平均比較回数は要素数の約半分という性質を2段階に適用する。 ア: m+n/m は各段階とも平均ではなく最悪に近い回数を足した形である。 イ: 正解。ブロック探索の平均 n/2m とブロック内探索の平均 m/2 の和である。 ウ: n/m はブロックを探す線形探索の最悪回数だけでブロック内の探索を含んでいない。 エ: n/2m はブロック探索の平均のみで、ブロック内の探索を忘れている。 💡 「線形探索の平均比較回数≒要素数の半分」「多段探索は各段階の平均の和」と覚える。なお m/2+n/2m は m=√n のとき最小になることも頻出知識である。