配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述として、適切なものはどれか。
| ア | 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。 |
| イ | 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。 |
| ウ | 線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順または降順にソートされている必要がある。 |
| エ | 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。 |
答え イ
【解説】
線形探索は目的とするデータを、1つ1つ順番に比較し探す方法で、探索対象のデータは整列(ソート)されてなくてもよい。
2分探索は整列されているデータにたいし、中央の値より探索している値が大きいか小さいかを判断し、探索範囲を半分にしながら探索する方法。
| ア | 探索対象となる配列の先頭の要素から順に探索するのは、線形探索法です。(×) |
| イ | 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例します。(〇) |
| ウ | 線形探索法を用いるときは、探索対象となる配列の要素は要素の値で昇順または降順にソートされている必要がない。(×) |
| エ | 探索対象となる配列が同一であれば、探索に必要な計算量の期待値は、2分探索法が線形探索法よりも少ない。(×) |
【キーワード】
・計算量
- 計算量
コンピュータの処理時間を考えた場合、最も正確に測定する方法は実際にプログラムを作って実機で処理時間を計測する方法であるが、プログラムの設計段階で2つのアルゴリズムの計算時間を比較する場合には、プログラムを作って比べることは難しいため、各アルゴリズムの計算量を調べて、計算量で比較を行います。
一般にコンピュータの処理で時間がかかるのは、比較演算であるので計算量を考えるときは、そのアルゴリズムの比較演算の回数を用います。
計算量を表す記号はオーダ(程度)を意味するO ( )を使用します。
もっと、「計算量」について調べてみよう。
戻る
一覧へ
次へ