RobbEr's Blog

Welcome

例题-斐波那契数列

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 962 阅读时长 ≈ 1 分钟

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

即f[n] = f[n-1] + f[n-2] ,当n>=2。

此题n≤39

解题思路

1. 暴力递归

递归是最直接的解题思路，由f[n] = f[n-1] + f[n-2]
代码如下

1
2
3
4
5
int Fibonacci(int n) 
{
    if (n==0 || n==1) return n;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

优点： 代码简单容易想到

缺点： 在n稍微大的情况下会很慢且超时

时间复杂度： O(2^n)

空间复杂度： 递归栈的空间

2. 动态规划

此题满足动态规划的条件，即当n>2时f[n]都是由f[n-1]与f[n-2]来决定的

1
2
3
4
5
6
7
8
9
int Fibonacci(int n) 
{
    vector<int> dp(n+1, 0);//0~n有n+1个元素
        dp[1] = 1;
        for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
}

时间复杂度： O(n)

空间复杂度： O(n)

3. 空间优化

在计算f[5]时发现，只用到了f[4]与f[3]，而f[2]…f[0]则是浪费了空间，所以还能继续优化

1
2
3
4
5
6
7
8
9
10
11
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（1）

转自牛客题解：斐波那契数列

基于编译器优化的递归优化(updated：2021-9-16)

C++11 引入的 constexpr 说明符在编译器支持内联展开优化时，将以增加编译时间的代价换取运行时间减少

1
2
3
4
constexpt int Fibonacci(int n) 
{
    return (n <= 1)? n : fib1(n-1) + fib1(n-2); 
}

优点： 代码简单容易想到

缺点： 需要编译器支持且在n稍微大的情况下会编译不通过

时间复杂度： O(n)

空间复杂度： 递归栈的空间