アルゴリズムのステップ数法（歩数法）とは？計算量解析の基本を解説

ステップ数法（歩数法）とは

ステップ数法（歩数法）は、アルゴリズムの効率を分析する手法の一つです。この方法では、アルゴリズム内の各命令が何回実行されるかを数え、その結果からアルゴリズムの計算量（時間計算量）を求めます。

具体的には、各命令の実行に必要なコスト（実行時間）を c1, c2, … のように定義し、「実行回数 × コスト」の合計を計算することで、アルゴリズム全体の実行時間を見積もります。

例：逐次探索（線形探索）の分析

ここでは、配列から特定のキー値を探す「逐次探索（シーケンシャルサーチ）」を例に、ステップ数法を使った計算量の求め方を見ていきましょう。最悪の場合（キーが配列中に存在しない、または末尾にある場合）を想定して分析します。

上記の表では、各命令が最悪ケースで何回実行されるかを示しています。たとえば、初期化 i := 0 は1回だけ実行されますが、while文の条件判定はループ終了時にも評価されるため n+1 回実行されます。また、if文による比較は最大で n 回発生します。

コストの計算

各命令の実行回数とコストを掛け合わせて合計すると（最悪ケースを想定）、次のようになります。

    Cost = c1 + (n+1)c2 + nc3 + c4 + c5

これを整理すると、

    Cost = c1 + nc2 + c2 + nc3 + c4 + c5

    Cost = n(c2 + c3) + c1 + c4 + c5

    Cost = n(c2 + c3) + C

ここで、定数部分である c1 + c4 + c5 を C と置くと、最終的な式は直線の方程式 y = mx + b と同じ形になります。つまり、この関数は入力サイズ n に対して線形に増加することがわかります。

結論：計算量は O(n)

このことから、逐次探索の時間計算量は O(n)、すなわち線形時間であると結論付けられます。入力データのサイズが大きくなるほど、実行時間もそれに比例して増加するということを、ステップ数法によって数学的に示すことができました。

ステップ数法は、このように各命令の実行回数を丁寧に追跡することで、アルゴリズムの性能を厳密に評価できる基本的かつ重要な解析手法です。