大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
一 题目：斐波那契数列
题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：
二 效率很低的解法
很多C/C++/C#/Java语言教科书在讲述递归函数的时候，大多都会用Fibonacci作为例子，因此我们会对这种解法烂熟于心
#include "stdio.h" #include <iostream> using namespace std; int Fibs(int n) { if (0 == n) { return 0; } else if (1 == n) { return 1; } return Fibs(n-1) + Fibs(n-2); } void main() { cout << "斐波那契数列：" << endl; cout <<Fibs(0)<<" "; cout <<Fibs(1)<<" "; cout <<Fibs(2)<<" "; cout <<Fibs(3)<<" "; cout <<Fibs(4)<<" "; cout <<Fibs(5)<<" "; cout <<Fibs(6)<<" "; cout <<Fibs(7)<<" "; cout <<Fibs(8)<<" " << endl; return; }
上述递归的解法有很严重的效率问题，通过求解第10项的调用过程图来分析：
从上图中不难发现：在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。
三 时间复杂度为O(n)的解法
改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了。这里的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。
#include "stdio.h" #include <iostream> using namespace std; int Fibs(int n) { int nFibs = 0; if (0 == n) { return 0; } else if(1 == n) { return 1; } int nSubOne = 1; // Fibs(n-1) int nSubTwo = 0; // Fibs(n-2) for (int i = 2; i <= n; i ++) { nFibs = nSubOne + nSubTwo; nSubTwo = nSubOne; nSubOne = nFibs; } return nFibs; } void main() { cout << "斐波那契数列：" << endl; cout <<Fibs(0)<<" "; cout <<Fibs(1)<<" "; cout <<Fibs(2)<<" "; cout <<Fibs(3)<<" "; cout <<Fibs(4)<<" "; cout <<Fibs(5)<<" "; cout <<Fibs(6)<<" "; cout <<Fibs(7)<<" "; cout <<Fibs(8)<<" " << endl; return; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120168.html原文链接：https://javaforall.net
