整列されたn 個のデータの中から、求める要素を2分探索法で探索する。 この処理の計算量のオーダを表す式はどれか。
答え ア
【解説】 2分探索法は1回探索を行うごとに、探索する範囲を半分にしながら行っていくので、m 個のデータ配列についての探索の回数はlog2m であり、これを計算量を表すオーダにするとlog n (ア)になります。
【キーワード】 ・2分探索法
戻る 一覧へ 次へ