斐波那契数列介绍

斐波那契数列（Fibonacci sequence）指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、55、89、144、……

在数学上，斐波那契数列的方法定义：

f(0) = 0f(1) = 1f(n) = f(n - 1) + f(n - 2)（n ≥ 2）

这个数列从第3项开始，每一项都等于前两项之和。

方法1：递归

递归实现：

int fRecursion(int n){   if (n == 0) return 0;   if (n == 1) return 1;   return fRecursion(n - 1) + fRecursion(n - 2);}

时间复杂度: O(2ⁿ)

我们用下面的递归调用树来理解递归实现的时间复杂度：

图1

因为每个节点在递归调用之外的工作时间为O(1), 所以运行时间等于调用的次数，即树中节点的总数。

这棵树有多少节点呢？假设我们要计算f(n), 根据图1我们可以知道树的深度为(n - 1)。

如果这是一棵完全二叉树，则树的总节点数为(2ⁿ-1)，因此时间复杂度为O(2ⁿ)。

通过观察图1，我们可以看到右子树节点数总是比左子树节点数少，因此这棵树的总节点数比同样深度的完全二叉树少（真实运行时间接近O(1.6ⁿ))。因为O(2ⁿ)描述的是运行时间的上界，我们可以简单地说递归实现的时间复杂度为 O(2ⁿ)。

方法2：自上而下的动态规划

通过观察图1，我们可以看到很多重复的节点。其中f(3)出现了2次，f(2)出现了3次。为什么要重复地计算f(3), f(2)......? 如果我们把计算过的f(i)的值缓存起来，下次遇到计算过的值直接从缓存里取。递归过程如下图（灰色圆圈的值从缓存取）：

图2

根据图2，我们可以看到f(n)的调用次数不超过O(n)。

自上而下的动态规划实现：

int fDynamicUpDown(int n){   return fDynamicUpDown(n, new int[n+1]);}int fDynamicUpDown(int i, int[] num) {   if (i == 0) return 0;   if (i == 1) return 1;   if(num[i] == 0){      num[i] = fDynamicUpDown(i - 1, num) + fDynamicUpDown(i - 2, num);   }   return num[i];}

时间复杂度: O(n)

方法3：自下而上的动态规划

从已知条件中已经知道f(1)和f(0)的值，通过利用f(1)和f(0)的值，我们可以计算出f(2)的值。接着我们可以根据已知的值计算出f(3)、f(4)......

自下而上的动态规划实现：

int fDynamicDownUp(int n){   if (n == 0) return 0;   if (n == 1) return 1;   int[] num = new int[n];   num[0] = 0;   num[1] = 1;   for (int i = 2; i < n; i++) {      num[i] = num[i-1] + num[i-2];   }   return num[n-1] + num[n-2];}

时间复杂度: O(n)

空间复杂度: O(n)

方法4：空间优化方法3

观察方法3，你会发现num[i]只会被使用2次：

num[i+1] = num[i] + num[i-1]

num[i+2] = num[i+1] + num[i]

我们可以用变量来存储中间值，不需要使用额外的num数组来存储中间值。

空间优化方法实现：

int fDynamicSpaceOpt(int n){   if (n == 0) return 0;   if (n == 1) return 1;   int a = 0, b= 1;   for (int i = 2; i < n; i++) {      int c = a + b;      a = b;      b = c;   }   return a + b;}

时间复杂度: O(n)

空间复杂度: O(1)