No.84 整列されたn個のデータの中から，求める要素を2分探索法で探索する。
この処理の計算量のオーダを表す式はどれか。
この処理の計算量のオーダを表す式はどれか。
⭕️
❌
💾
| 🖊 | ☑️ |
| ⭕️ | [[ AnswerCalc[0] ]] % | A | [[ AnswerCalc[1] ]] |
|
|
|
|
|
|
|
|
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) になります。
💾
✔️
| [[ d.CommentTxt ]] |
| < | > |
| 🥇 |