アルゴリズムの設計と探索

要点と定義

アルゴリズムは、問題を解くための処理手順です。流れ図では、順次、判定による分岐、繰返しを使って手順を表します。読むときは、各処理の順番と判定後の進み先を追い、繰返しの終了条件も確かめます。

分割統治法は、問題を小さな部分問題に分け、それぞれを解いて結果を組み合わせ、元の問題を解く設計方法です。部分問題を独立に処理できることが典型的な特徴です。部分問題の解を統合するところまでが方法の要点であり、局所的に最善の選択を重ねる貪欲法や、候補を絞る探索とは考え方が異なります。分割後の解を統合するかどうかが、この方法を見分ける手掛かりです。

整列アルゴリズムは、途中状態の要素の動きからも見分けられます。バブルソートは隣り合う要素を比較し、昇順なら左の値が大きいときに交換します。一回の走査で、最大の未整列要素が右端へ移動します。例えば「8, 3, 6, 2」を左から走査すると、8が隣の値と順に交換され、走査の終わりに右端へ進みます。完成した列だけでなく、一回ごとの交換を追うと方式を判別できます。

クイックソートは、基準値より小さい値と大きい値に分け、部分列をさらに処理します。分割の細かな規則は、問題で指定された方法に従います。例えば列「12, 5, 15, 9」を左端の12を基準に分け、グループ内の順序を保つなら、「5, 9」と「15」に分かれます。基準値は元の列にある値から選び、入力にない値を加えません。また、分割しただけでは各部分列の中まで整列済みとは限りません。

探索では、データの並びや格納方式が前提になります。線形探索は順に調べ、二分探索は整列済みの範囲を比較で半分ずつ絞ります。ハッシュ表探索はハッシュ値から格納位置を求めます。衝突がない条件なら、データ数が増えても探索時間は理論上一定、すなわち O(1) です。衝突時の追加処理や探索時間は、ハッシュ表の方式や対策によります。衝突がないという条件が、一定時間と判断する根拠です。

二分木などの再帰処理では、再帰を止める条件と、子と自分自身を処理する順番を定義から読み取ります。例えば「右の部分木、左の部分木、自分」の順なら、その順を各部分木にも適用します。子の順序や出力位置が変われば、同じ木でも結果は変わります。右、左、自分という定義が出力順を決めるため、再帰処理の問題ではこの順を忠実に追います。

適用条件と例

二分探索は対象範囲が整列しているときに使えます。中央の値との比較で不要な半分を除き、範囲を繰り返し縮めます。初期区間の幅を1とすれば、k回の縮小後の幅は 1/2^k です。幅を0.001未満にする場合は、1/2^k < 0.001、すなわち 2^k > 1000 を満たす最小の整数kを求めます。k=9では512、k=10では1024なので、最小のkは10です。この反復回数を求めるには、区間が各回で半分になることと停止条件の両方を使います。単調な関数で区間の両端が根を挟む場合に、区間を狭めて近似値を求める考え方にもつながります。近似値を求める反復計算は、過去の出題で扱った補足です。

整列済みのデータをm個ずつに分け、各ブロックの末尾を順に調べてから該当ブロック内を線形探索する場合、平均比較回数には両方の探索を含めます。データ数をnとし、目的データが必ずあり、各位置が同程度に選ばれるとします。ブロック数はn/mです。ブロック末尾を調べる平均回数はおよそn/(2m)、ブロック内の平均回数はおよそm/2なので、主要項は n/(2m)+m/2 です。これはブロック数が整数になるなどの条件で考える平均比較回数です。どちらか片方の探索だけを数えると、合計を誤ります。この平均比較回数の分析は、過去の出題で扱った補足です。

アルゴリズムを選ぶときは、入力の性質、求める結果、途中の処理を合わせて確認します。隣接交換の連続ならバブルソート、基準値での分割なら指定されたクイックソートの規則と照合します。衝突のない条件でハッシュ表探索を評価する場合は、衝突による追加探索がないことを確かめます。