はじめMath! Javaでコンピュータ数学

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

この記事を読むのに必要な時間:およそ 3 分

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

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

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! )となる場合を紹介しました。

著者プロフィール

平田敦(ひらたあつし)

地方都市の公立工業高等学校教諭。趣味はプログラミングと日本の端っこ踏破旅行。2010年のLotYはRuby。結城浩氏のような仕事をしたいと妄想する30代後半♂。