アルゴリズム

要点と定義

アルゴリズムは、問題を解くための処理手順です。手順を追うときは、処理の順番、判断する条件、繰返しの開始と終了を分けて確認します。流れ図では、条件を判定する位置が処理の前か後かによって、繰り返す回数が変わります。たとえば、積を求める処理で「値を掛ける」「変数を増やす」「終了条件を調べる」の順なら、終了判定時の変数は最後に掛けた値より一つ大きくなります。正の整数を1からMまで掛ける例では、Mを掛けた後に変数がM＋1になった時点で終わる条件は n＞M です。

整列では、操作の特徴を見分けます。バブルソートは隣り合う要素を比較し、順序が逆なら交換する方法です。選択ソートは未処理部分から最小値を探して先頭と交換し、クイックソートは基準値を決めて小さい値と大きい値に分割します。マージソートは列を小さな部分に分け、整列しながら併合します。クイックソートの分割結果を追うときは、指定された基準値、対象範囲、要素の順序を保つ条件を一つずつ適用します。

探索の平均比較回数は、成功と失敗を分けて期待値を求めます。n件から先頭順に線形探索し、検索値が存在しない確率をaとすると、成功確率は1−aです。成功時の位置が一様なら平均比較回数は( n＋1 )／2、失敗時は全件を調べてn回です。したがって期待比較回数は ( n＋1 )( 1−a )／2 ＋ na です。

逆ポーランド表記は、演算子を対象の値の後に置く表記です。左から読み、値をスタックに積み、演算子が現れたら必要な値を取り出して計算します。例えば A＋B×C は、BとCを先に掛けてからAを足すので、後置式では B C × A ＋ となります。

再帰処理は、処理の中から同じ処理をより小さな対象に対して呼び出す方法です。木構造では、子の処理順とノード自身を出力する位置を確認します。右の子、左の子、自身の順に処理するなら、各部分木でも同じ順序を適用します。

適用条件と例

可変量メモリの最適適合では、要求量以上の空き領域から最小のものを選びます。空き領域の大きさをキーとする二分探索木なら、要求量以上で最小のキーを探せます。木が平衡であれば探索は平均 O(log n) となり、空き領域を大きさ順に並べた連結リストを先頭から調べる方法より効率よく候補を探せます。一方、アドレスをキーにした木はアドレス順の探索には向きますが、最小の適合サイズを直接選ぶ基準にはなりません。

クイックソートの分割では、分割後に各部分列へ同じ処理を繰り返します。例として、列 6, 8, 3, 7, 2 を基準値6で分けると、小さい側は 3, 2、大きい側は 8, 7 です。問題で部分列内の順序を維持すると指定されていれば、分割だけで 2, 3 や 7, 8 に並べ替えてはいけません。続く分割も、指定された側の部分列とその基準値だけを対象にします。

経路や仕事の順番を決める問題では、許される順序ごとの遷移コストを足し、最小値を求めます。四つの仕事を一度ずつ行う例なら、候補順序の遷移時間を順に合計し、最小値を比較します。最小候補を示すだけでなく、各遷移の下限などからそれより小さくならないことを確かめると、最小である根拠を示せます。