アルゴリズムの基本と代表手法

要点と定義

アルゴリズムは、問題を解くための処理手順です。処理の順次実行、条件による分岐、繰返しを、擬似言語や流れ図などで表します。流れ図を読むときは、各処理の順序と、判定結果によって進む経路を追います。

整列はデータを順序に並べる処理です。バブルソートは隣り合う要素を比べ、昇順なら左の値が右より大きいときに交換します。交換がなくなれば終了する方式では、交換がない走査を終了条件にします。交換の有無にかかわらず所定回数走査する実装もあります。隣接比較と逆順時の交換が、他の整列方法と見分ける手掛かりです。 過去の出題で扱った補足として、走査ごとに未整列部分の最大値が右端へ移る状態推移もありますが、ここでは特定の図や配列の推移を一般化しません。

分割統治法は、問題を複数の部分問題に分け、それぞれを解き、その結果を統合して元の問題を解く設計方法です。部分問題が独立している場合もありますが、独立性を定義の必須条件とはしません。

後置記法では演算子を被演算子の後に置きます。左から読み、演算子に出会ったら直前の二つの値を使って計算します。過去の出題で扱った計算では、C−D＝2、B×2＝16、A＋16＝32の順に処理します。この数値と順序はその設問の値に基づくものです。 中置表記を後置記法に直す場合は、元の式の演算順位を保ちます。乗算を加算より先に行う前提なら、A＋B×CはABC×＋です。

再帰アルゴリズムは、処理の中で同じ処理をより小さな対象に適用する方法です。終了条件と、部分問題へ進む条件を確認します。二分木の巡回順は定義に従います。過去の出題で扱った定義では、右の部分木、左の部分木、自ノードの順に出力し、子があればそれぞれの再帰処理を終えてから自ノードを出力します。この順番はその定義に従うもので、すべての木の再帰処理に共通する順序ではありません。

探索は目的のデータを見つける処理です。ブロック探索では、整列済みの表を一定件数ごとのブロックに分け、各ブロックの末尾を順に調べて対象ブロックを絞り、その中を線形探索します。各ブロックが同じ大きさで、目的データが必ず存在し、各位置が同程度に選ばれるとき、ブロック数をn/mとすると厳密な平均比較回数はn/(2m)+m/2+1です。選択肢にあるm/2+n/(2m)は定数項1を省いた近似表現と区別します。mが十分に大きいという条件だけで、厳密式から定数項を消すことはできません。

適用条件と例

整列方法は、どの要素を比較し、どの範囲をどう更新するかで識別します。たとえば選択ソートなら、未整列部分から最小値を選び、その先頭と交換して整列済み部分を広げます。これは手順を追うための例であり、特定の過去問の配列や状態推移を示すものではありません。

クイックソートでは、基準値を使って値を分割し、各部分をさらに処理します。過去の出題で扱った設問固有の条件は、基準値を部分配列の左端とし、基準値より小さい値と大きい値に分け、各グループ内の順序を保つことでした。その条件では、1回目・2回目の分割後とも列は1, 2, 3, 5, 4です。グループ内の順序を保つ規則をクイックソート一般の性質とは扱いません。

ブロック探索の平均値は、ブロック末尾を調べる回数と、該当ブロック内を調べる回数を分けて求めます。ブロック数をB=n/mとすると、前者の平均は(B+1)/2、後者は(m+1)/2です。合計を整理するとn/(2m)+m/2+1になります。これは目的データが必ずあり、位置が同程度に選ばれるという条件での計算です。