糟糕的斐波那契算法的属性
前几天我正在研究规范的坏斐波那契算法：
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 函数。
您知道关于这个函数还有其他有趣的观察吗？
附加说明：我知道有关记忆等的所有很酷的东西......我不是问如何优化它。
I was looking at the canonical bad fibonacci algorithm the other day:
public static int fib(int n)
{
// Base Case
if (n < 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
I made the interesting observation. When you call fib(n), then for k between 1 and n fib(k) is called precisely fib(n-k+1) times (or fib(n-k) depending on your definition of fib(0) ). Also, fib(0) is called fib(n-k-1) times. This then allows me to find that in fib(100) there are exactly 708449696358523830149 calls to the fib function.
Are there other interesting observations on this function you know of?
Additional note: I know all the cool stuff about memoization etc... I am NOT asking on how to optimize it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一个很好的案例，说明了为什么记忆化是一种非常有用的优化在斐波那契等函数中。
正如您所看到的，您可以将函数调用次数从
2*fib(n)-1减少到n- 这要好几个数量级。在数学方面，斐波那契数还有许多其他有趣的属性。
This is a wonderful case for why memoization is a very useful optimization in functions such as Fibonacci.
As you can see, you can reduce the number of function calls from
2*fib(n)-1ton- which is orders of magnitude better.Mathematics-wise, the Fibonacci numbers have many other interesting properties.
添加 Yuval 所说的内容...
除了记忆之外，还值得一提的是密切相关的“动态编程”。 非常密切相关 - 就我个人而言，我不太清楚记忆化是否是动态编程的特殊情况。无论如何，在这种情况下，标准迭代解决方案可以称为动态规划解决方案。
在迭代解中，当您尝试计算
fib(n)时，您已经计算了部分解fib(n-2)和fib(n- 1)所以你只需重复使用那些预先计算的部分解决方案。它是在循环中完成的对于动态编程来说并不重要。记忆化可能是一种特殊情况（我只是不确定根据严格的定义它是否始终是一种特殊情况）。关键是每个部分解都会被记住，因此只需要计算一次。Adding to what Yuval has said...
As well as memoization, it's also worth mentioning the closely related "dynamic programming". Very closely related - personally, I'm not too clear on whether memoization is a special case of dynamic programming or not. Anyway, in this case, the standard iterative solution could be called a dynamic programming solution.
In the iterative solution, when you try to calculate
fib(n), you have already calculated the partial solutionsfib(n-2)andfib(n-1)so you just re-use those precalculated partial solutions. That it is done in a loop isn't important to dynamic programming. Memoization can be a special case (I'm just not sure whether it's always a special case according to strict definitions). The key point is that each partial solution is remembered, so that it only needs to be calculated once.我将添加更多的数学注释。您的算法的大 O 表示法确实是 F(n)，但是与我们通常考虑的 O(N^2) 或 O(NlogN) 相比，这到底意味着什么？
它非常糟糕：它具有 O(e^N) 空间和时间复杂度。在数学上你可以证明 lim (N-> \inf) F(n) = ((1+\sqrt(5))/2)^N
I'll just toss this more mathematical note in. The big O notation for your algorithm is indeed F(n), but what the heck does that mean compared to O(N^2) or O(NlogN) we normally think about?
Its crazy bad: it has O(e^N) space and time complexity. Mathematically you can show that lim (N-> \inf) F(n) = ((1+\sqrt(5))/2)^N