IPA 整列・探索・計算量 — 頻出論点と過去問

頻出論点

1. この分野は何か

データを規則正しい順序に並べ替える手順や、並んだデータの中から目的の値を探し出す手順と、それらに要する処理回数の見積もり方を学びます。アルゴリズムの仕組みをステップごとに追いかけ、データの件数が増えたときに比較や反復の回数がどのように増えるかを数式やオーダー記法で評価します。

2. 実際の出題のされ方

探索アルゴリズムの性質の比較や、手順文に従ってデータを並べ替えるときの実行回数は、ITパスポートで問われています。線形探索法と2分探索法について、事前のソートの要否や要素数に対する計算量の増え方を比べる問題や、最大値を選んで末尾と入れ替え整列対象から外していく一連の手順が終了までに何回実行されるかを求める問題が出ています。

整列法を手順や途中の状態から見分ける問題と、探索の比較回数を式で表す問題が、応用情報技術者の午前と高度試験の午前Iの中心です。整列では、文章・データ列の状態推移・流れ図からバブルソートを特定する問題が複数回出ており、クイックソートで指定されたルールに従って2回目の分割が終わった時点の配列状態を求める問題もあります。探索と反復回数の計算では、昇順の表をブロックに分割してブロック単位とブロック内の2段階で線形探索する平均比較回数の式、探索対象が表に存在しない確率を考慮した線形探索法の平均比較回数の式、連続関数の区間を中点で半分に狭めながら指定した精度になるまで繰り返す実行回数が問われています。このほか、非負の整数の階乗を返す関数の再帰的な定義や、アルゴリズムの設計手法を選ぶ問題が出ています。

データベーススペシャリストの午前IIでは、関係データベースにおいて二つの表を入れ子ループ法で結合する場合の計算量をオーダー記法で求める問題が出題されています。

3. 学習のポイント

代表的な整列アルゴリズムは、1回の操作で何が確定するかと、途中の状態をどう見分けるかで区別します。

クイックソートの途中状態を追跡する問題では、基準値の選び方（グループの左端など）と、分割後のグループ内の並び順（元の配列の順序を保つなど）について問題文の指定を確認します。1回目の分割で要素数が1になったグループはそれ以上分割されないため、2回目の分割がどのグループに対して行われるかを落ち着いてたどることが大切です。

次に、線形探索と2分探索法の性質と平均比較回数の導出を押さえます。

• 線形探索法: 先頭から順に比較するため事前の整列は不要で、要素数 $n$ に対する計算量は $O(n)$ です。目的のデータが1番目から $n$ 番目に等確率で存在する場合、平均比較回数は $\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}$ 回となります。データが存在しない場合は全要素と比較するため、比較回数は必ず $n$ 回です。
• ブロック分割探索: 1,000件を100件ずつ10ブロックに分けると、ブロックを探すのが平均 $(10+1)/2 = 5.5$ 回、ブロック内が平均 $(100+1)/2 = 50.5$ 回で、合わせて平均56回です。各段の平均を足すのが要点です。
• 区間を半分にする反復と2分探索法: 整列された配列の中央と比較して探索範囲を半分に絞り込む2分探索法や、解の存在区間を半分ずつ縮める二分法では、区間の幅が毎回半分になります。例えば幅1を0.01未満にするには $2^k > 100$、つまり7回かかります。終了条件で判定する量が区間の幅そのものか、その半分（中点から端までの距離）かを問題文で確かめることが重要です。

さらに、アルゴリズムの構造と計算量の対応を確認します。大きな問題を小さな問題に分割して独立に処理し、結果をつなぎ合わせて元の問題を解く設計手法が分割統治法です。関数が自分自身を呼び出す再帰的な定義では、再帰を止める基底の条件と、引数を基底に近づける再帰ステップの両方を見ます。例えば1から $n$ までの和を返す $sum(n)$ なら、$n=0$ のとき $0$ を返し、それ以外は $n + sum(n-1)$ を返します。基底で返す値は演算によって決まり（和なら $0$、積なら $1$）、再帰呼出しの引数は基底に近づく向きに変えます。計算量のオーダーについては、1回の走査が $O(n)$、区間を半分にする探索が $O(\log n)$、片方の表の各行についてもう片方を全件調べる入れ子ループ法が $O(n^2)$ となる対応を押さえておきます。

4. 間違えやすいところ

2分探索法と線形探索法の比較では、2分探索の方が常に比較が少ないとする誤答肢がありました。最大計算量のオーダーは2分探索法の方が小さいものの、探す値が先頭にあれば、線形探索は1回で見つかります。

平均比較回数の立式では、段階や場合分けの漏れに注意が必要です。2段の探索の一方の段だけの平均や、平均でなく最大回数を足した式、見つからない場合の比較回数を足し忘れた式が誤答肢でした。

反復回数や再帰的定義を問う問題では、終了条件の読み違いから生じる値や式が誤答肢にありました。

• 整列手順の実行回数: 手順を続ける条件（例えば「整列対象に要素が1個以上残っていれば，(1)から(3)の一連の手順を実行する」のように、残りが1個以上か2個以上か）で回数が1回変わるので、終了条件の文を読み落とさないようにします。
• 二分法の反復回数: 終了条件の数値から回数をそのまま読み取る誤りに注意します。
• 再帰的定義の終了条件: 掛け算を繰り返す再帰で基底が $0$ を返すと計算結果がすべて $0$ になる定義や、再帰呼出しで引数を増やしてしまい基底に届かない定義が誤答肢でした。