大家好,又见面了,我是全栈君,今天给大家准备了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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120168.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...