平成27年春期試験午前問題 問6

整列されたn個のデータの中から,求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

  • log n
  • n
  • n2
  • n log n
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1/2に狭めて探索することを再帰的に繰り返して目的のデータを探索するアルゴリズムです。

2分探索法では、データの個数 n と計算量 x の関係は下表のようになっています。
06.gif
この関係を立式すると

 n=2x

2を底として対数(log)をとると、

 log2n=x

つまり計算量のオーダは O(log n) になります。

Pagetop