算法设计------斐波那契数列

发表于 | 分类于

斐波那契数列

斐波那契数列又称黄金分割数列，这个数列从第三项开始，每一项都等于前两项之和。

递推公式

F(0) = 1;
F(1) = 1;
F(n) = F(n-1) + F(n-1);

通项公式

递推公式算法实现

1
2
3
4
5
int Fib( n )
{
    if ( n == 1 || n == 2 ) return 1;
    else return Fib(n-1) + Fib(n-2);
}
时间复杂度：O(2^n)

动态规划算法实现

递推公式计算Fib(n-1)时Fib(n-2)又被计算了一次，所以导致大量重复计算，为了避免重复计算，我们可以将之前计算出来的结果存储起来，这就是动态规划的思想了。

1
2
3
4
5
6
7
8
int Fib( n )
{
    int F[ MAXSIZE ];
    F[ 1 ] = F[ 2 ] = 1;
    for ( int i = 3 ; i <= n ; ++ i )
        F[ i ] = F[ i-2 ] + F[ i-1 ];
    return F[ n ];
}
时间复杂度：O(n)

通项公式算法实现

通项公式方式实现，其实回到了快速幂的计算方法

1
2
3
4
5
6
double pow (double a, int n){
 	if (n == 0) return 1;
    if (n == 1) return n;
    double t = pow(a, n/2);
    return t * t * pow(a, n%2);
}
时间复杂度：O(㏒ n)

相关链接

斐波那契数列通项公式是怎样推导出来的？

如果对你有帮助的话，Star✨下一吧！