java - 为什么这样写显著提升了Fibonacci sequence性能？？
问题来自Algorithms(算法，第四版)的1.1.19练习题。
题目如下：
在计算机上运行一下程序：
Javapublic class Fibonacci { public static long F(int N) { if (N == 0) return 0; if (N == 1) return 1; return F(N-1) + F(N-2); } public static void main(String[] args) { for (int N = 0; N < 100; N++) StdOut.println(N + " " + F(N)); } }
计算机用这段程序在一小时内能得到的F(N)结果的最大N值是多少？开发F(N)的一个更好的实现，用数组保存已经计算的值。
---------题目结束--------------
首先我在计算机上(windows8.1 64位系统)运行上面程序，如下：
发现用上面题目给出的方法运行到N = 40多时，程序已经明显慢下来了，
问题1：慢下来是因为处理的数据太大了，而且每次都要再次计算？还是因为其他什么原因？
问题2：题目中要预测计算机在一小时内能够得到F(N)结果的最大N值，这个怎么做？
然后在这里提供了题目问题的代码，如下：
javapublic class Ex_1_1_19 { public static long F(int N) { if (N == 0) return 0; if (N == 1) return 1; return F(N-1) + F(N-2); } public static long Fib(int N) { long[] f = new long[N+1]; return Fib(N, f); } public static long Fib(int N, long[] f) { if (f[N] == 0) { if (N == 1) f[N] = 1; else if (N > 1) f[N] = Fib(N-1, f) + Fib(N-2, f); } return f[N]; } public static void main(String[] args) { // for (int N = 0; N < 100; N++) // StdOut.println(N + " " + F(N)); for (int N = 0; N < 100; N++) StdOut.println(N + " " + Fib(N)); } }
再次运行时，居然在1秒多就运行完了:
问题3：
很好奇为什么这么快，自己尝试分析下，用N=0,1,2,3试，但是在Fib函数中为什么要if (f[N] == 0)呢？数组最后一个元素为0？
是因为用数组 f 保存已经计算过的值了，所以不需要再重新计算了所以才快了很多吗？
问题4：
最后结果从93行开始，93,95，96,97,99行出现的负数，大致知道是和操作系统运算有关，但又不是很清楚，求解释？
