データサイエンティスト検定 リテラシーレベル データエンジニアリング 練習問題 第49問: 会員番号の一覧から、指定した番号を探す処理を考える。線形探索は一覧を先頭から順に比べ、二分探索は昇順に並べた一覧で探す範囲を半分ずつ狭めるものとする。一覧の件数
データエンジニアリング
– / 81 解いた
第49問
会員番号の一覧から、指定した番号を探す処理を考える。線形探索は一覧を先頭から順に比べ、二分探索は昇順に並べた一覧で探す範囲を半分ずつ狭めるものとする。一覧の件数が1,000件から4,000件に増えたとき、探す番号が一覧に無い場合の比較の回数の変わり方として、最も適切なものはどれか。回数はおよその値でよい。
解答と解説を先に見る
先に見ると、この問題は今回は育ちません。
正解: 2. 線形探索は約4倍になり、二分探索は約2回増える
「線形探索は約4倍になり、二分探索は約2回増える」が適切です。線形探索は先頭から順に比べるので、番号が無い場合は全件と比べ、回数は1,000回から4,000回へと件数に比例して約4倍になります。
二分探索は1回比べるごとに範囲を半分にするので、回数は範囲が1件になるまで半分にする回数です。2の10乗は1,024、2の12乗は4,096なので、1,000件では約10回、4,000件では約12回となり、件数が4倍(2の2乗)でも増えるのは約2回です。
二分探索も約4倍・約2倍とした肢は、回数が件数に比例すると取り違えています。約12回増えるとした肢は、4,000件のときの回数を増えた回数とした誤りで、線形探索の約2倍も件数の比と合いません。
二分探索には事前の並べ替えが要る点も押さえましょう。出典:『高等学校情報科「情報Ⅰ」教員研修用教材』(文部科学省)を加工して作成
関連キーワード: 線形探索・二分探索・計算量・アルゴリズム
模試 (100問)
この問題が解けたら、本試験はどうですか?本番形式で、ほかの科目もまとめて確かめる
本番形式の模擬試験で実力チェックPremium (月980円)Premium (ご利用中)本番と同じ制限時間
広告