2007年11月28日 18:00 [Edit]

アルゴリズム百選 - フィボナッチ数列にO()を学ぶ

404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、#bookmarksもいくとは。

とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本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

この記事へのトラックバック
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ【】at 2012年01月17日 18:17
前エントリのクロージャ導入ネタついでの発展的例題として、フィボナッチ数列あたりがいいかなと考えて探していたのだが、またしてもdankogai氏に行き着いた。「フィボナッチ数列にO()を学ぶ」、これが実に分かりやすい。いや、この人はほんとに頭がいいのかも、と初めて(?)...
ScalaとJavaScript その2dankogai氏の「フィボナッチ数列にO()を学ぶ」【Weblog towards a Word-Progress】at 2009年11月07日 15:07
前エントリのクロージャ導入ネタついでの発展的例題として、フィボナッチ数列あたりがいいかなと考えて探していたのだが、またしてもdankogai氏に行き着いた。「フィボナッチ数列にO()を学ぶ」、これが実に分かりやすい。いや、この人はほんとに頭がいいのかも、と初めて(?)...
ScalaとJavaScript その2dankogai氏の「フィボナッチ数列にO()を学ぶ」【Weblog towards a Word-Progress】at 2009年11月06日 23:50
あいかわらずの体調不良です。1つ前のエントリーで体調不良と数学について書いたら、hyuki先生から「お大事に」とのコメントをいただきました。これはもう「数学ガール/フェルマーの最終定理」買っちゃいなよ!ということなんだと思います。しかし、財布の中には千円しか入
[数学塾]フィボナッチ数列を求める公式とか計算量(オーダー)の話とか【医者を志す妻を応援する夫の日記】at 2009年02月20日 22:15
今回は、ユークリッドの互除法を取り上げます。
アルゴリズム百選 - ユークリッドの互除法【404 Blog Not Found】at 2007年12月11日 16:36
 「最近あなたのブログ、プログラミングの話ばっかりじゃない?」とは妻の指摘。確かにその通りなんだが、これとかこれを読んでしまうと、どうしてもそちらに走りたくなるのが私の性分。ということで、とことん「ギーク街道」堕ちてみた。  今回の作品は、
フィボナッチ関数とJavascriptの黒魔術と【Life is beautiful】at 2007年12月06日 03:28
「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがある...
O(1)というのはご機嫌に速いということ?【Inquisitor】at 2007年12月05日 01:32
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ この記事のJavaScriptプログラムを、C言語で書き直してみた。 #1: ナイーブな実装 O(2のn乗) ソース /* * fivonacci.c - フィボナッチ数列を出力するプログラム */ #include <stdio.h> int n; i
[C]フィボナッチ数列にO()を学ぶ C言語バージョン【stafooの日記】at 2007年12月01日 03:03
この記事へのコメント
アルゴリズムと無関係だから触れられていないのかもしれませんが…
・定義と称して第1項から第5項を示す
・たかだか最初の5項から「F(3)以降は、〜わかります」と漸化式を決定する
の二つの点において少しばかり理解を超えています。
最初の5項だけなら、もしかしたら
F(n)=n-1 (n mod 4≠1) or n (n mod 4=1)
という数列かもしれないというのに…
Posted by noname at 2007年12月06日 04:03
追加です。
「F(1)からF(n)までをO(n)で求めるアルゴリズム」と言う言い方ならばアドバンテージも分かるしすっきりするのではないかと思うのですが、どうでしょう?
Posted by garyu at 2007年12月05日 07:33
これ、「F(n)を求める」という問題ならばO(n)になると思います。
「F(n-1)までを記憶している前提でF(n)を求める」という問題設定ならO(1)と言えますけど、それを前提にしてしまうと、単純な足し算のO()を求める問題になってしまうわけで…。
Posted by garyu at 2007年12月05日 07:30
sさん、
や、その通りです。というわけでコード修正。
Shuさん、
おっしゃる通りです。厳密なO notationでは、c**nのcが違う場合は違うものと見なされるので。
Dan the Debugged
Posted by at 2007年12月04日 23:24
> fib(5)は8回fib()を呼びます

とありますが、9回ではないのでしょうか。
Posted by yt at 2007年12月04日 15:17
実装を考えると、nが小さい場合と、例題のようにnを変化させてそれぞれのfib(n)を知りたい場合は数学関数を使用しないメモ化版が良さそうですね。

nが大きいときのfib(n)を知りたいときは公式版が有利と思いますが、この場合nはいくつくらいが境目になるんでしょうね。
Posted by t at 2007年12月02日 11:19
>アルゴリズムは、O(2のn乗)ということになります
→ 細かい話ですが、正確には、O(PHIのn乗)=O(1.618のn乗)ですよね?
Posted by Shu at 2007年11月30日 02:39
取り上げていただいてありがとうございます。

>30とかは絶対に入れないでください
やらないでと言われると、やりたくなるのが、人間。笑
javascriptだと、さすがにきついんですねぇ、固まって、その後に次のメッセージが、、、でも最終的には生き返りました。

【このページのスクリプトがIEの実行速度を遅くしています。
スクリプトを実行し続けると、コンピュータが反応しなくなる可能性があります。
スクリプトを中断しますか?】

ちなみに、Excel VBAだと、同じ「O(2のn乗)版のアルゴリズム」が30でもさくっと出てしまいました。
Oかぁ、懐かしいなぁ。。。
Posted by Shu at 2007年11月30日 01:22

二つめのフィボナッチ
if (c == 2 ) return b;
じゃなくて
if (c == 2) return a;

ですよね。
Posted by s at 2007年11月29日 18:01
びっくりした。
xssってレベルじゃねーぞ
Posted by anon at 2007年11月29日 10:22
f(a, b, c)の終了条件で c==1 のときは、a を返すべきではー。
でないと、ひとつづつずれてます。
この企画、期待大です。
Posted by いぼなっち at 2007年11月29日 03:19
「フィボナッチ数を計算する公式では、n乗の計算が必要なので、O(1)ではないと思うのですが」と書きましたが、指数関数と対数関数を組み合わせるので、O(1)と考えることも出来るのですね。どうもすみません。ところで、fib(n)*fib(n)+fib(n-1)*fib(n-1)=fib(2*n-1)を使うと、O(n)よりも少し改良できます。
Posted by m-riho at 2007年11月28日 18:56
フィボナッチ数を計算する公式では、n乗の計算が必要なので、O(1)ではないと思うのですが。

Posted by m-riho at 2007年11月28日 18:32