0

先日、正規の悪いフィボナッチアルゴリズムを見ていました：

public static int fib(int n)
{
    // Base Case
    if (n < 2)
    return 1;       
    else 
    return fib(n-1) + fib(n-2);     
}

興味深い観察をしました。fib(n) を呼び出すと、1 と n の間の k に対して fib(k) は正確に fib(n-k+1) 回 (または fib(0) の定義に応じて fib(nk) ) 呼び出されます。また、fib(0) は fib(nk-1) 回呼び出されます。これにより、 fib(100) で fib 関数への呼び出しが正確に 708449696358523830149 あることがわかります。

あなたが知っているこの機能に関する他の興味深い観察はありますか?

追記：私はメモ化などについての素晴らしいことをすべて知っています...私はそれを最適化する方法について尋ねているわけではありません。

4

3 に答える 3

2

これは、メモ化がフィボナッチなどの関数で非常に便利な最適化である理由の素晴らしい例です。

2*fib(n)-1ご覧のとおり、 からへの関数呼び出しの数を減らすことができますn。これは桁違いに優れています。

数学的には、フィボナッチ数には他にも多くの興味深い特性があります。

于 2010-03-20T16:28:26.213 に答える
2

ユヴァルが言ったことに追加して...

メモ化と同様に、密接に関連する「動的プログラミング」も言及する価値があります。非常に密接に関連しています-個人的には、メモ化が動的プログラミングの特殊なケースであるかどうかについてはあまり明確ではありません。とにかく、この場合、標準的な反復ソリューションは動的計画法のソリューションと呼ぶことができます。

反復解では、 を計算しようとするとfib(n)、すでに部分解が計算されているため、事前に計算された部分解fib(n-2)をfib(n-1)再利用するだけです。ループで実行されることは、動的計画法にとって重要ではありません。メモ化は特殊な​​ケースになる可能性があります（厳密な定義によれば、常に特殊なケースであるかどうかはわかりません）。重要な点は、各部分解が記憶されているため、一度だけ計算する必要があることです。

于 2010-03-20T17:00:00.637 に答える
0

このより数学的なメモを投げ入れます。あなたのアルゴリズムの大きな O 表記は確かに F(n) ですが、私たちが通常考えている O(N^2) や O(NlogN) と比較して、それは一体何を意味するのでしょうか?

そのクレイジーな悪い点: O(e^N) の空間と時間の複雑さがあります。数学的には、 lim (N-> \inf) F(n) = ((1+\sqrt(5))/2)^N を示すことができます

于 2014-07-09T06:14:18.137 に答える