如何用c语言编程实现斐波那契数列（C语言实现黄金分割数列）

方法1：递归

递归实现：

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

时间复杂度: O(2ⁿ)

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

因为每个节点在递归调用之外的工作时间为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，我们可以看到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)