平成27年度 春期 午前 問6

✓ これが正解アlog n

解説

見る範囲が毎回半分になるので log n に比例します。

2 分探索は、整列済みの並びの真ん中と目的の値を比べ、探す範囲を半分に絞ることを繰り返す方法です。1 回比べるごとに残る範囲が半分になるので、n 個から始めて残りが 1 個になるまでの回数は、n を 2 で何回割れるかで決まります。これが対数で表される回数です。判定の軸は、1 回の操作で残りがどれだけ減るかという一点で、一定の割合ずつ減る処理の計算量は対数の大きさになります。オーダは底の違いや定数倍を区別しないので、log n と書き表します。

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

• イn：先頭から順に一つずつ照合していく探し方に現れる大きさです。要素の数に比例して比較の回数が増えるので、範囲を半分ずつ絞る方法の速さを表していません。
• ウn²：要素の数の 2 乗に比例する大きさで、一つ一つの要素について全体をもう一度たどるような処理に現れます。整列済みの並びを絞り込むだけの処理はここまで増えません。
• エn log n：要素の数に比例する回数だけ絞り込みを繰り返す形で、並べ替えの手法などに現れることが知られている大きさです。一つの値を見つけるだけの処理には当てはまりません。