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(nk) 取决于您对 fib(0) 的定义）。此外，fib(0) 被称为 fib(nk-1) 次。这让我发现在 fib(100) 中恰好有 708449696358523830149 调用 fib 函数。

你知道这个函数还有其他有趣的观察吗？

附加说明：我知道所有关于记忆等很酷的东西......我不是在问如何优化它。

4

3 回答 3

2

这是一个很好的例子，说明为什么记忆化是斐波那契等函数中非常有用的优化。

如您所见，您可以将函数调用的数量从2*fib(n)-1to减少几个数量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 回答