基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成27年 春期 基本情報技術者 午前 問06
問06   2分探索法の計算量

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

ア log n        イ n        ウ n 2        エ n log n
解答←クリックすると正解が表示されます

解説

 2分探索法は、ソートされたデータの中央のデータと探索するデータを比較し、 前方にあるか後方にあるかを判断する。 探索するデータが、前方にあるの場合は、次に前半のデータの中央のデータと比較する。 この操作を繰り返すことによって、データを探索する。

 要素数が n 個の場合に2分探索法を使った場合の比較回数は, 次の式で求めることができる。

平均比較回数:(log n)回
最大比較回数:(log n)+1回

【平成21年春 問07 IT パスポート 類題】


[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]