基本情報技術者平成27年春期 午前問6

午前問6

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1/2に狭めて探索することを再帰的に繰り返して目的のデータを探索するアルゴリズムです。

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

 n=2x

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

 log2n=x

つまり計算量のオーダは O(log n) になります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop