何かを作るとき、全くゼロから作り始めると言うことはまれです。たいていは、何か「ひな形」になるものや、類似のものを用意して、それを変更したり、機能を付加して新しいものにしていくでしょう。そのとき、サンプルのカタログが手元にあると重宝します。どれだけたくさんのサンプルを持っているかが、技能・技術のレベルに大きく影響します。それは経験と言い換えることも出来るでしょう。
これまで、計算量がO (n ),O (log2 (n )),O (1 )となるアルゴリズムとコードを紹介しました。今回はその他の代表的な計算量の値とそのときのコード例を紹介します。
これまでの連載とあわせれば、計算量とコードの小さなカタログになります。ご活用いただけると幸いです。なお、計算量に関する連載記事の内容は、きしだなおきさんのブログエントリを参考にさせていただきました。快く許可下さったきしださんに、この場を借りてお礼申し上げます。
計算量:O (na )となる場合
次のコードはO (n2 )になります。n回の繰り返しをn回繰り返すのですから、実行回数はn×n=n2 です。3重のループならばO (n3 )になります。
入力量nが大きくなると、計算量が急激に大きくなります。
n回ループをa個「入れ子」にした場合の計算量はO (na )になるのですね。
計算量:O (an )となる場合
次のコードはO (2n )となります。確認できますか?
初学者にとって、再帰を用いたコードの流れを追うのは大変なことです。
いきなり大きな入力を試さず、最もシンプルな場合から試すのが良い学習方法です。そこで、n =1の時から見てみましょう。コードの動きを表現するために、「擬似コードのようなもの」を用いました。擬似コード[1]とは、コンピュータで実際に動くわけではありませんが、アルゴリズムをきちんと表現できる架空のプログラミング言語のことです。ここでは、プログラムの動きを表現するために、トレース[2]的に擬似コードのコマンドと値をセットで用いました。とにかくご覧頂ければ、何となく分かると思います。計算量の基準・単位に関数proc
の実行回数を用います。関数proc
が実行された回数を数えて下さい。
proc()
は2回実行されました。では、n =2ではどうでしょうか。
proc()
は4回実行されました。さらに実行の様子を探って見ると、どうやらproc()
は2n実行されるようです。ということで、計算量はO (2n )になります。
問題 次のソースコードの計算量をオーダー表示しましょう。
このソースコードが実行されたとき、どれだけの計算量なるのかオーダー表示しましょう。
解説
問題 次のソースコードの計算量をオーダー表示しましょう。
小さな場合から実行の様子を追ってみましょう。先ずはn =1から。
proc()
は1回実行されました。次はn =2で実行してみます。
proc()
は2回実行されました。O (n )でしょうか?いやいや、コードとこれまでの実行状況を見ると、O (n! )となりそうです。ループの回数が再帰呼び出しのたびに一つ減っているからです。念のためにn =3で確かめてみましょう。
proc()
は6回実行されました。6=3!=n!で間違いないようです。擬似コードで示した実行の様子を見ても、間違いなくO (n! )がこのコードの計算量です。
今回はここまで
代表的な計算量のパターンを一通り紹介しました。計算量とそのコードの例を知ることで「動かす前に実行時間の見立てがつく」ようになったはずです。コードを実行して初めて「おかしいな、なかなか終了しない」と思うことが減るはずです。あるいは「おかしいな、こんなに時間がかかるはずがない」という読みも出来るようになります。計算量の数学を身につけると言うことは、プログラマとして1つレベルが上がることだと思って間違いありません。少し高みから世界を眺めるような、そんな気持ちが味わえることでしょう。