斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci[1]）以兔子繁殖为例子而引入，故又称为“兔子数列”。 指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义： F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*） #includeusing namespace std; //递归形式 //long long fibonacci(int i) //{ // return i < 2 ? i : fibonacci(i - 1) + fibonacci(i - 2); //} void test1() { cout << fibonacci(6) << endl;; } //非递归形式 long long fibonacci(int n) { int tem[2]; tem[0] = 1; tem[1] = 1; if (n == 0) { return 0; } if ( n == 1) { return 1; } else { for (int i = 2; i < n; i++) { int temp = tem[0] + tem[1]; tem[1] = tem[0]; tem[0] = temp; } return tem[0]; } } //优化 时间复杂度O（n） long long fibonacci(int n) { long long fibonacci[3] = { 0, 1, n }; for (int i = 2; i <= n; ++i) { fibonacci[2] = fibonacci[1]+fibonacci[0]; fibonacci[0] = fibonacci[1]; fibonacci[1] = fibonacci[2]; } return fibonacci[2]; } int main() { test1(); system("pause"); return 0; }
我们不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的.
在分析算法的时间复杂度的时候，我们也可以得到相同的结果，非递归使用的是for循环，其时间复杂度为O(n)。而递归的时间复杂度则比较复杂，其分析出来为O(2^n)。
这里需要说明的就是，非递归的for循环其时间复杂度O(n)虽然很小，但是其空间复杂度缺比递归调用差得多。因为，for循环在每次循环的时候，都把相应的数值保存下来了，而递归调用却不会保存相应的数值。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
