アルゴリズム

アルゴリズムは、与えられた入力から目的の出力を得るための、曖昧でない有限個の処理手順です。正しさだけでなく、停止性、時間計算量、空間計算量、適用条件を評価します。

■ 試験で押さえるポイント

• 同じ問題でも線形探索、二分探索、各種整列など複数の手順があり、入力規模nに対する処理回数をO記法で比較します。

• 二分探索は整列済み配列を半分ずつ絞るためO(log n)ですが、未整列データへそのまま適用できません。前提条件もアルゴリズムの一部です。

• 擬似言語、流れ図、決定表などで実装言語に依存せず表現し、全入力に対する正当性と境界・例外条件を検証してからコード化します。

• 時間を短くするためメモリを多く使うなどトレードオフがあり、最悪・平均計算量、データ特性、実装容易性を目的に応じて選びます。

■ 選択肢での判断ポイント

有限回で終了する明確な手順と計算量が要点です。特定言語で書かれたプログラムそのものではなく、その背後にある解法です。

例: 要素数1,024の整列済み配列を二分探索すると、探索範囲を1,024→512→…→1と半減でき、最大比較回数は概ねlog2(1,024)＝10回です。