アルゴリズム (全80問中27問目)
No.27
整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダーを表す式はどれか。
出典：平成27年春期 問6
- log n
- n
- n2
- n log n
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1／2に狭めて探索することを再帰的に繰り返して目的のデータを探索するアルゴリズムです。
2分探索法では、データの個数 n と計算量 x の関係は下表のようになっています。
この関係を立式すると
n＝2x
2を底として対数(log)をとると、
log2n＝x
つまり計算量のオーダーは O(log n) になります。
2分探索法では、データの個数 n と計算量 x の関係は下表のようになっています。
n＝2x
2を底として対数(log)をとると、
log2n＝x
つまり計算量のオーダーは O(log n) になります。