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

2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな

[samurairodeo]

“チ数F(n)は、nが同じなら必ず同じ数になります。それならば、一度計算した結果を覚えておけば、いちいち計算する必要はないことになります。実装すると、以下のようになります。”

[xrekkusu]

@masawada ここらへん見るとメモ化っていう手法での高速化が

[Cherenkov]

code golf

[webmarksjp]

プログラミング

[rakudaininja]

[programming]

[tanakaBox]

メモ化って凄く繁雑な手続きが必要かと思ってた。簡単じゃん。SICPの続き読もう。

[hiromark]

すばらしい記事。

[namikister]

フィボナッチ数列を計算するアルゴリズムの話．単純なのにすごい話がひろがるなぁ．おもしろい

[hnw]

roundするんだったら((1-√5)/2)^n計算する必要ないよ、ってのがSICPの演習問題にもあったと思うんですが、ツッコミ待ちですか？議論の方向からすると些細な話ですけど。

[adsty]

フィボナッチ数列は美しい。そして説明は分かりやすい。

[mathatelle]

数学はおもしろい

[sea_side]

ほんと数学っておもしろい。HSPでDCTを書き終わった時はちょっとうれしかった。なんでHSPって、プログラミング自体には興味ないから・・・

[denken]

フィボなっちありがとう数列

[ag-commerce]

http://blog.livedoor.jp/dankogai/archives/50958771.html

[NSR250R-SP]

フィボナッチ数列

[sezu]

O()ってよく理解できてなかったんだけど、これはわかりやすい。プログラム初心者にもおすすめ。

[hiroponz]

アルゴリズムによって計算量のオーダーが大きく異なることやコンピュータでは厳密解を求められないことがあるなど非常に分かりやすい

[poolmmjp]

おもしろかった。2番目のコードちょっと変だけど。

[seamlessbias]

fibはナイーブな実装をすると実用に耐えないんで、公式使うとかmemoizeするとか。

[thrakt]

f(a,b,c)で脱帽です こんなの思いつかねぇ

[nik9]

incorrect. O( ((1+\sq 5)/2) ^ n ) < O( 2^n )

[sshi]

「O()」こう書くのははじめてみた。

[blakichi]

面白い！

[lakehill]

これは判りやすい、大学でやってたことを思い出した。

[TakahashiMasaki]

(これはいい

[suttang]

O() の意味をはじめて知った

[Makots]

Fibonacci

[gotin]

メモ化