平成24年度 秋期 午前 問3

✓ これが正解アlog₂n n 1

解説

2分探索はlog₂n、線形探索はn、ハッシュ探索は1です。

実行時間のオーダは、データの数が増えたときに手数が何に比例して伸びるかを表したものです。軸は三つの探索方法それぞれで、対象をどれだけ速く絞り込めるかが違う点にあります。整列済みのデータを毎回半分に切り詰めていく2分探索は、1回照合するたびに残りが半分になるので、数が2倍になっても手数は1つ増えるだけです。先頭から順に照合していく線形探索は、最悪の場合は最後まで見ることになるため、手数はデータの数に比例します。鍵から格納位置を計算して直接たどるハッシュ探索は、衝突を無視できるという前提が置かれているので、数がいくら増えても手数は変わりません。この三つの伸び方を正しく割り当てた組合せを選びます。

ほかの選択肢はなぜ違うのか

• イn log₂n n log₂n：2分探索にnとlog₂nを掛けた形を、ハッシュ探索にlog₂nを割り当てた組合せです。半分ずつ絞る方法は1回で残りが半分になるだけなので、データの数を掛けた形にはなりません。
• ウn log₂n n² 1：線形探索にn²を割り当てた組合せです。先頭から順に照合する方法は、最悪でもデータの数だけ照合すれば必ず終わるので、二乗の形に膨らむことはありません。
• エn² 1 n：2分探索にn²、線形探索に1、ハッシュ探索にnを割り当てた組合せです。三つとも実際の伸び方と結び付いておらず、とりわけ順に照合する方法がデータの数によらず一定になることはありません。