第77回　計算量の数学　計算量と実際のコード　その3

何かを作るとき、全くゼロから作り始めると言うことはまれです。たいていは、何か「ひな形」になるものや、類似のものを用意して、それを変更したり、機能を付加して新しいものにしていくでしょう。そのとき、サンプルのカタログが手元にあると重宝します。どれだけたくさんのサンプルを持っているかが、技能・技術のレベルに大きく影響します。それは経験と言い換えることも出来るでしょう。

これまで、計算量がO (n ),O (log₂ (n )),O (1 )となるアルゴリズムとコードを紹介しました。今回はその他の代表的な計算量の値とそのときのコード例を紹介します。

これまでの連載とあわせれば、計算量とコードの小さなカタログになります。ご活用いただけると幸いです。なお、計算量に関する連載記事の内容は、きしだなおきさんのブログエントリを参考にさせていただきました。快く許可下さったきしださんに、この場を借りてお礼申し上げます。

計算量：O (n^a )となる場合

次のコードはO (n² )になります。n回の繰り返しをn回繰り返すのですから、実行回数はn×n＝n² です。3重のループならばO (n³ )になります。

入力量nが大きくなると、計算量が急激に大きくなります。

public void compute(int n) {
  for(int i = 0; i < n; ++ i){
    for(int j = 0; j < n; ++j){
      proc();//なにか処理
    }
  }
}

n回ループをa個「入れ子」にした場合の計算量はO (n^a )になるのですね。

多重ループの計算量

O (n^a )

計算量：O (aⁿ )となる場合

次のコードはO (2ⁿ )となります。確認できますか？

public void compute(int n) {
  if(n == 0){
    proc();//なにか処理
    return;
  }
  for(int i = 0; i < 2; ++i){
    compute(n - 1);
  }
}

初学者にとって、再帰を用いたコードの流れを追うのは大変なことです。

いきなり大きな入力を試さず、最もシンプルな場合から試すのが良い学習方法です。そこで、n =1の時から見てみましょう。コードの動きを表現するために、「⁠擬似コードのようなもの」を用いました。擬似コード[1]とは、コンピュータで実際に動くわけではありませんが、アルゴリズムをきちんと表現できる架空のプログラミング言語のことです。ここでは、プログラムの動きを表現するために、トレース[2]的に擬似コードのコマンドと値をセットで用いました。とにかくご覧頂ければ、何となく分かると思います。計算量の基準・単位に関数procの実行回数を用います。関数procが実行された回数を数えて下さい。

compute(1)
  n == 0 is false
  for(i=0..1,i=0)
    compute(0)
      n == 0 is true
      proc() ............(1)
  for(i=0..1,i=1)
    compute(0)
      n == 0 is true
      proc() ............(2)
    end of for
end of compute(1)

proc()は2回実行されました。では、n =2ではどうでしょうか。

compute(2)
  n == 0 is false
  for(i=0..1,i=0)
    compute(1)
      n == 0 is false
      for(i=0..1,i=0)
        compute(0)
          n == 0 is true
          proc() ............(1)
      for(i=0..1,i=1)
        compute(0)
          n == 0 is true
          proc() ............(2)
      end of for
    end of compute(1)
  for(i=0..1,i=1)
    compute(1)
      n == 0 is false
      for(i=0..1,i=0)
        compute(0)
          n == 0 is true
          proc() ............(3)
      for(i=0..1,i=1)
        compute(0)
          n == 0 is true
          proc() ............(4)
      end of for
    end of compute(1)
  end of for
end of compute(2)

proc()は4回実行されました。さらに実行の様子を探って見ると、どうやらproc()は2ⁿ実行されるようです。ということで、計算量はO (2ⁿ )になります。

a回ループで再帰呼び出しした場合の計算量

O (aⁿ )

問題　次のソースコードの計算量をオーダー表示しましょう。

このソースコードが実行されたとき、どれだけの計算量なるのかオーダー表示しましょう。

public void compute(int n) {
  if(n == 0){
    proc();//なにか処理
    return;
  }
  for(int i = 0; i < n; ++i){
    compute(n - 1);
  }
}

解説

問題　次のソースコードの計算量をオーダー表示しましょう。

小さな場合から実行の様子を追ってみましょう。先ずはn =1から。

compute(1)
  n == 0 is false
  for(i=0..0,i=0)
    compute(0)
      n == 0 is true
      proc() ............(1)
  end of for
end of compute(1)

proc()は1回実行されました。次はn =2で実行してみます。

compute(2)
  n == 0 is false
  for(i=0..1,i=0)
    compute(1)
      n== 0 is false
      for(i=0..0,i=0)
        compute(0)
          n == 0 is true
          proc() ............(1)
      end of for
    end of compute(1)
  for(i=0..1,i=1)
    compute(1)
      n== 0 is false
      for(i=0..0,i=0)
        compute(0)
          n == 0 is true
          proc() ............(2)
      end of for
    end of compute(1)
  end of for
end of compute(2)

proc()は2回実行されました。O (n )でしょうか？いやいや、コードとこれまでの実行状況を見ると、O (n! )となりそうです。ループの回数が再帰呼び出しのたびに一つ減っているからです。念のためにn =3で確かめてみましょう。

compute(3)
  n == 0 is false
  for(i=0..2,i=0)
    compute(2)
      n == 0 is false
      for(i=0..1,i=0)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(1)
          end of for
        end of compute(1)
      for(i=0..1,i=1)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(2)
          end of for
        end of compute(1)
      end of for
    end of compute(2)
  for(i=0..2,i=1)
    compute(2)
      n == 0 is false
      for(i=0..1,i=0)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(3)
          end of for
        end of compute(1)
      for(i=0..1,i=1)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(4)
          end of for
        end of compute(1)
      end of for
    end of compute(2)
  for(i=0..2,i=2)
    compute(2)
      n == 0 is false
      for(i=0..1,i=0)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(5)
          end of for
        end of compute(1)
      for(i=0..1,i=1)
        compute(1)
          n== 0 is false
          for(i=0..0,i=0)
            compute(0)
              n == 0 is true
              proc() ............(6)
          end of for
        end of compute(1)
      end of for
    end of compute(2)
  end of for
end of compute(3)

proc()は6回実行されました。6=3!=n!で間違いないようです。擬似コードで示した実行の様子を見ても、間違いなくO (n! )がこのコードの計算量です。

再帰呼び出しの度にループ回数が1減る場合の計算量

O (n! )

今回はここまで

代表的な計算量のパターンを一通り紹介しました。計算量とそのコードの例を知ることで「動かす前に実行時間の見立てがつく」ようになったはずです。コードを実行して初めて「おかしいな、なかなか終了しない」と思うことが減るはずです。あるいは「おかしいな、こんなに時間がかかるはずがない」という読みも出来るようになります。計算量の数学を身につけると言うことは、プログラマとして1つレベルが上がることだと思って間違いありません。少し高みから世界を眺めるような、そんな気持ちが味わえることでしょう。

計算量：O (na )となる場合

計算量：O (an )となる場合

問題 次のソースコードの計算量をオーダー表示しましょう。

解説

今回はここまで

計算量：O (n^a )となる場合

計算量：O (aⁿ )となる場合

問題　次のソースコードの計算量をオーダー表示しましょう。