2007年11月28日 18:00 [Edit]
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、
とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。
ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。
ヒントとなった
アルゴリズムではないですが・・・フィボナッチ数列 - Shuのつまづき日記アルゴリズムではないですが、フィボナッチ数列はすごいですねぇ。
に感謝。
フィボナッチ数列にO()を学ぶ
フィボナッチ数という数を聞いたことがあるでしょうか。数学ファンには実にお馴染みの数で、先日エミー賞にノミネートされた「たけしのコマネチ大学数学科」でも、第一回でこれが取り上げられました。
この数は不思議なことに、自然界の実に多くのところに登場します。詳しくは「404 Blog Not Found:The Fibonacci Code」で紹介した各書をあたってもらうことにして、本書はアルゴリズムの本なので、その計算法を見ていくことにしていきます。
まずはフィボナッチ数の定義から。
F(1) = 1 F(2) = 1 F(3) = 2 = 1+1 F(4) = 3 = 1+2 F(5) = 5 = 2+3
F(3)以降は、単純に前二つの数を足していけばいいことがわかります。定義をそのままJavaScriptに直すと、こうなるでしょう。
function fib(n){
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
では、これを早速動かしてみましょう。
- プログラム:
- 出力:
- エラー:
ナイーブな実装にはワナがある
たしかにうまく行きます。しかし、ここで上のプログラムのn <= 10を25とかにして見ましょう。どうなりましたか?かなり動作がもっさりとしませんでしたか?そうそう。30とかは絶対に入れないでください。ブラウザーが止まらなくなります。
なぜ、そうなったのでしょう。プログラムをもう一度よく見てみましょう。最後のところで、fib()は自分自身を二度呼んでいます。ということは、fib(3)は都合3回、fib(4)は5回、fib(5)は8回fib()を呼びます。一般化すると、n番目のフィボナッチ数をF(n)とすると、それを計算するにはfib()をF(n+1)回呼ばなければならないことになるのです。文字通り幾何級数的に手間が増えるのです。
この「ある問題を解くのに、データが大きくと解く手間がどれほど大きくなるのか」という問題を、計算機学者たちは「計算量問題」と呼びます。そしてそれをあらわすのにO(nの関数)という書き方をします。これは「問題を解く手間は、nの関数のオーダーで大きくなる」という意味になります。上の定義どおりの解き方＝アルゴリズムは、O(2n)ということになります。
ちょっとした工夫のすごさ
ここで、プログラムの書き方を少し変えてみましょう。自分自身を呼ぶ回数を、プログラムの中で2回ではなく1回にするのです。
- プログラム:
- 出力:
- エラー:
JavaScriptは関数の中に関数を定義できるので、ちょっと面白い書き方になっていますが、この関数の要点は、F(n-1)の結果とF(n-2)の結果を引数として渡していることです。上記のfが呼ばれる回数は、今度はnが3以上ならn-1回となります。オーダーで言えばO(n)ということになります。
それでも、nが増えていくに従って計算量が増えることには違いありません。さらによい方法はないでしょうか。
O(1)への道その1:公式を使う
実は、フィボナッチ数を一発で計算する公式がすでに存在します。
これをそのまま移植すれば、どんなにnが大きくてもこの式は一回しか計算しないので、この式がO(1)である限りO(1)、すなわちnの大きさに関わらず計算量は変わりません。
数学的に見ても実に美しい公式で、√が入っているのに整数を入れれば絶対に整数が返ってくるという点も不思議です。が、コンピューター上でやる場合にはこれが問題となりえます。
これを素直にJavaScriptに移植すると、こうなります。
- プログラム:
- 出力:
- エラー:
見ての通り、小数のものがどうしても混じってしまいます。これはコンピューターが厳密解を計算できない、厳密にはJavaScriptの演算では厳密解を出さないためです。1 / 3 * 3が1にならないのと同様の理由といえばお分かりでしょうか。
一応以下のようにすることで、この問題は回避できます。
- プログラム:
- 出力:
- エラー:
それでも、元の定義に比べてずいぶんと面倒です。整数のまま計算して、かつO(1)な方法はないのでしょうか?
O(1)への道その2:メモ化
フィボナッチ数F(n)は、nが同じなら必ず同じ数になります。それならば、一度計算した結果を覚えておけば、いちいち計算する必要はないことになります。実装すると、以下のようになります。
- プログラム:
- 出力:
- エラー:
こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(memoization)として知られています。見ての通り、定義通りなナイーブな計算法を使っているのに、O(2n)がO(1)（厳密には、最初の一回だけO(n))になってしまうのです。
これこそが、アルゴリズムの醍醐味です。
まとめ
- ナイーブな実装をそのまま使うかは、O()を吟味してから
- O()が小さいからといって、実装が楽だとは限らない
- 数学的な美しさが、プログラムに裏切られることがある
- ナイーブのアルゴリズムも、別のアルゴリズムの組み合わせによってO()が劇的に下がることもある
Dan the Algorithmic Man
この記事へのトラックバックURL
・定義と称して第1項から第5項を示す
・たかだか最初の5項から「F(3)以降は、〜わかります」と漸化式を決定する
の二つの点において少しばかり理解を超えています。
最初の5項だけなら、もしかしたら
F(n)=n-1 (n mod 4≠1) or n (n mod 4＝1)
という数列かもしれないというのに…
「F(1)からF(n)までをO(n)で求めるアルゴリズム」と言う言い方ならばアドバンテージも分かるしすっきりするのではないかと思うのですが、どうでしょう？
「F(n-1)までを記憶している前提でF(n)を求める」という問題設定ならO(1)と言えますけど、それを前提にしてしまうと、単純な足し算のO()を求める問題になってしまうわけで…。
や、その通りです。というわけでコード修正。
Shuさん、
おっしゃる通りです。厳密なO notationでは、c**nのcが違う場合は違うものと見なされるので。
Dan the Debugged
とありますが、9回ではないのでしょうか。
nが大きいときのfib(n)を知りたいときは公式版が有利と思いますが、この場合nはいくつくらいが境目になるんでしょうね。
→ 細かい話ですが、正確には、O（PHIのn乗）=O（1.618のn乗）ですよね？
＞30とかは絶対に入れないでください
やらないでと言われると、やりたくなるのが、人間。笑
javascriptだと、さすがにきついんですねぇ、固まって、その後に次のメッセージが、、、でも最終的には生き返りました。
【このページのスクリプトがIEの実行速度を遅くしています。
スクリプトを実行し続けると、コンピュータが反応しなくなる可能性があります。
スクリプトを中断しますか？】
ちなみに、Excel VBAだと、同じ「O(2のn乗)版のアルゴリズム」が30でもさくっと出てしまいました。
Oかぁ、懐かしいなぁ。。。
二つめのフィボナッチ
if (c == 2 ) return b;
じゃなくて
if (c == 2) return a;
ですよね。
xssってレベルじゃねーぞ
でないと、ひとつづつずれてます。
この企画、期待大です。
