Fibonacci数列实现C++
Fibonacci
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
方法一：递归
斐波那契数列公式为： F ( n ) = { 0 , n = 0 1 , n = 1 , 2 F [ n − 1 ] + F [ n − 2 ] , n > 2 F(n) = \begin{cases} 0, & n=0 \\ 1, & n =1,2 \\ F[n-1]+F[n-2], &n>2 \end{cases} F(n)=⎩⎪⎨⎪⎧0,1,F[n−1]+F[n−2],n=0n=1,2n>2, 初始值 F [ 0 ] = 0 , F [ 1 ] = 1 F[0]=0,F[1]=1 F[0]=0,F[1]=1考虑使用递归的方法。
class Solution {
public:
int Fibonacci(int n) {
if (n == 0 || n == 1) return n;
return Fibonacci(n-1) + Fibonacci(n-2);
}
};
递归算法实现简单，代码量少，但时间复杂度为
o
(
2
n
)
o(2^n)
o(2n)，空间复杂度为递归栈的空间
为什么时间复杂度为
o
(
2
n
)
o(2^n)
o(2n)，可以从二叉树的节点个数来考虑，递归算法可以展开为一个二叉树，所以有
n
n
n项的递归数列，可以看成深度为
n
n
n二叉树，故算法运算次数为二叉树上至多含有的节点个数
2
n
−
1
2^n-1
2n−1，时间复杂度为
o
(
2
n
)
o(2^n)
o(2n)。
方法二：动态规划
递归算法的时间复杂度高是因为存在很多重复的计算，改进办法是将计算的过程保存。动态规划是不用递归过程，直接从子树求得答案，过程是从下往上。简而言之，我们已知前两项的值，然后我们就可以用前两项的值求出第3项的值，接着求第4、第5、……，直到求出第n项的值。
int Fibonacci(int n) {
vector<int> dp(n+1, 0);
dp[1] = 1;
for (int i=2; i<=n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
继续优化，例如求第五项的时候只用到第四项和第三项，因此前面的项就不需要保存，来占用内存空间。通过定义三个变量交替存储计算结果。
class Solution {
public:
int Fibonacci(int n) {
if (n == 0 || n == 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i){
c = a + b;
a = b;
b = c;
}
return c;
}
};
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)