主記憶上で、配列にＮ個の見出し (key) 付きデータが格納されているものとする。このデータに対する操作に関する次の記述のうち、最も不適切なものはどれか。
① 線形探索法を用いて見出し探索を行う場合、1つの見出しの探索に要する最悪の計算量はＯ(Ｎ)である。
② 2分探索法を用いて見出 し探索を行う場合、1つの見出しの探索に要する最悪の計算量はＯ(log2Ｎ)である。
③ データが見出し順にソートされているとき、新たなデータをその状態をくずさないように追加するために必要な最悪の計算量はＯ(log2Ｎ) である。
④ 2分探索法を用いて見出し探索を行う場合には、事前にデータを見出し順にソートしておかねばならない。
⑤ 2分探索法は、見出しの探索空間を1回の比較操作ごとに約2分の1ずつに狭める探索法である。
③
計算量はオーダー記法Ｏ( )で表される大体 (というより大雑把) の処理時間を捉えるための指標である。
数字が1～32まであったとして、1がどこにあるか調べるとき、1が先頭にあったら計算量は1であり、Ｏ(1) と表記する。
もし1が一番最後にあったら1を見つけるのに32回調べないといけないので、計算量は32ということになり、Ｏ(32) と表記する。
① 線形検索法は、最初から順番に検索していく方法である。上記のとおり最悪の計算量はＯ(Ｎ) である。
② 2分検索法は、検索値と、データを2分割した真ん中の値を比較し、検索値がデータの真ん中の値よりも小さければデータの前半部分を、大きければデータの後半部分を検索して、検索範囲を2分の1ずつ狭めていく方法である。
例えば32個のデータから9を調べるとき、16 → 8 → 12 → 10 → 9の順番で検索する。
最悪の計算量は Ｏ(log2Ｎ) となる。
③ 不適切である。2分検索法であれば、Ｏ(log2Ｎ) であるが、方法が明記されていないため、線形法で処理した場合、最悪の計算量はＯ(Ｎ) である。
④ 正しい。
⑤ 正しい。
| Ⅰ－１ | 目次 | Ⅰ－３ |