斐波那契数列的三种C++实现及时间复杂度分析 |
您所在的位置：网站首页 › 用递归求斐波那契数列时间复杂度 › 斐波那契数列的三种C++实现及时间复杂度分析 |
斐波那契数列的三种C++实现及时间复杂度分析
|
本文介绍了斐波那契数列的三种C++实现并详细地分析了时间复杂度。 斐波那契数列定义：F(1)=1, F(2)=1, F(n)=F(n-1) + F(n-2) (n>2) 如何计算斐波那契数 F(n) 及时间复杂度 T(n) 呢? 我参考了一些资料总结了以下3种方法：递归法、顺序法和矩阵乘法，并给出了基于C++的简单代码实现和时间复杂度分析。 如有不当，欢迎指正。 方法1：递归法 实现： 
#include
#include
using namespace std;
long long Fibonacci1(int n)
{
if (n < 1)
{
return 0;
}
if (n == 1 || n == 2)
{
return 1;
}
return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}
int main()
{
char cont = 'y';
int n = 0;
long long f = 0;
cout >= 1)
{
if ((p & 1) != 0)
{
result = MatrixMultiply(result, m);
}
m = MatrixMultiply(m, m);
}
}
return result;
}
long long Fibonacci3(int n)
{
if (n < 1)
{
return 0;
}
if (n == 1 || n == 2)
{
return 1;
}
Matrix m1(2, 2);
m1.p[0][0] = 1;
m1.p[0][1] = 1;
m1.p[1][0] = 1;
m1.p[1][1] = 0;
Matrix result = MatrixPowder(m1, n - 2);
if (g_nStatus == kInvalid)
{
cout |
【本文地址】
今日新闻 |
推荐新闻 |