CO-K47｜情報Ⅰ 対策問題

正答

1

この問題のポイント

アルゴリズムの効率（計算量の考え方） を問う問題です。「データ量が増えたら手間はどう増えるか」という見方を身につけましょう。

解説

アルゴリズムの「効率」は、データ量nが増えたときに、計算回数(手間)がどのように増えるかで評価します。特定のコンピュータでの実行時間は機械の速さに左右されますが、「増え方」はアルゴリズム自体の性質なので、公平な比較ができるのです。

代表的な増え方を並べてみましょう。線形探索はnに比例(データ2倍で手間2倍)。バブルソートはn²に比例(データ2倍で手間4倍)。二分探索はlog₂nに比例(データが2倍になっても手間は1回増えるだけ)。

差は劇的です。n=100万のとき、n²はおよそ1兆回ですが、log₂nは約20回。同じ問題でも、選ぶアルゴリズム次第で手間に天と地ほどの差がつきます。「速いコンピュータを買うより良いアルゴリズムを選ぶ方が効く」ことがある、というのがこの単元のメッセージです。

共通テストでは、線形探索と二分探索の比較回数を具体的なデータ数で比べさせる形や、「データ量が増えたときの手間の増え方で比較する」という考え方自体を選ばせる形で出題されます。作者名や見た目など、処理の手間と無関係な観点を混ぜた誤答に惑わされないようにしましょう。

選択肢の確認

1．○ データ量に対する計算回数の増え方が効率の指標。
2．× 誰が書いたかは処理の手間と無関係。
3．× 文字の色は表示上の見た目で、実行の手間と無関係。
4．× 変数名の長さは読みやすさの問題で、効率の指標ではない。

ここだけは覚えよう

効率=nが増えたときの手間の増え方 — 線形探索はn、バブルソートはn²、二分探索はlog₂nに比例。