午前問6
整列されたn個のデータの中から、求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。
| log n | |
| n | |
| n2 | |
| n log n |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- ア
解説
2分探索法は、探索対象の要素が昇順または降順に整列されている場合に有効なアルゴリズムです。
具体的なアルゴリズムは以下です。
1.探索の範囲内の中央の要素と目的の要素を比較します。
2.目的の要素と中央の要素が一致すれば探索を終了します。
3.目的の要素が中央の要素よりも小さければ前半部分を、大きければ後半部分を探索の範囲として 1. へ戻ります。
要素数がn個の場合、2分探索法での比較回数は、次の式で求めることができます。
log n
よって正解は「ア」となります。
具体的なアルゴリズムは以下です。
1.探索の範囲内の中央の要素と目的の要素を比較します。
2.目的の要素と中央の要素が一致すれば探索を終了します。
3.目的の要素が中央の要素よりも小さければ前半部分を、大きければ後半部分を探索の範囲として 1. へ戻ります。
要素数がn個の場合、2分探索法での比較回数は、次の式で求めることができます。
log n
よって正解は「ア」となります。