何かを作るとき，全くゼロから作り始めると言うことはまれです。たいていは，何か「ひな形」になるものや，類似のものを用意して，それを変更したり，機能を付加して新しいものにしていくでしょう。そのとき，サンプルのカタログが手元にあると重宝します。どれだけたくさんのサンプルを持っているかが，技能・技術のレベルに大きく影響します。それは経験と言い換えることも出来るでしょう。
これまで，計算量がO (n ),O (log2 (n )),O (1 )となるアルゴリズムとコードを紹介しました。今回はその他の代表的な計算量の値とそのときのコード例を紹介します。
これまでの連載とあわせれば，計算量とコードの小さなカタログになります。ご活用いただけると幸いです。なお，計算量に関する連載記事の内容は，きしだなおきさんのブログエントリを参考にさせていただきました。快く許可下さったきしださんに，この場を借りてお礼申し上げます。
図77.1 ベテランこそひな形の価値を知っている
計算量：O (na )となる場合
次のコードはO (n2 )になります。n回の繰り返しをn回繰り返すのですから，実行回数はn×n＝n2 です。3重のループならばO (n3 )になります。
入力量nが大きくなると，計算量が急激に大きくなります。
public void compute(int n) {
for(int i = 0; i < n; ++ i){
for(int j = 0; j < n; ++j){
proc();//なにか処理
}
}
}
n回ループをa個「入れ子」にした場合の計算量はO (na )になるのですね。
多重ループの計算量
O (na )
計算量：O (an )となる場合
次のコードはO (2n )となります。確認できますか？
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()は2n実行されるようです。ということで，計算量はO (2n )になります。
a回ループで再帰呼び出しした場合の計算量
O (an )
- ※1）
- Pseudo code（読み：すーどう・こーど）
- ※2）
- トレースとは，プログラム実行中のコンピュータ内部の様子を，変数の値の一覧表を更新しながら追いかける作業のことです。
