有哪些网站或者公司招募做视频的,企业网站排名优化公司,房地产网站推广,网页设计公司平台斐波那契数列定义#xff1a;
斐波那契数列大家都非常熟悉。它的定义是#xff1a; 对于给定的整数 x #xff0c;我们希望求出#xff1a; f ( 1 ) f ( 2 ) … f ( x ) f(1)f(2)…f(x) f(1)f(2)…f(x) 的值。
有两种方法,分别是递推(迭代)与递归
具体解释如下图 备注…斐波那契数列定义
斐波那契数列大家都非常熟悉。它的定义是 对于给定的整数 x 我们希望求出 f ( 1 ) f ( 2 ) … f ( x ) f(1)f(2)…f(x) f(1)f(2)…f(x) 的值。
有两种方法,分别是递推(迭代)与递归
具体解释如下图 备注递推(迭代)的方式是利用开一个有 x 个元素的数组表示由 x 种的状态本质上是利用空间换时间然后循环迭代每一个状态其中一个新状态是由两个旧状态递推出来的整个递推过程只需要 O ( n ) O(n) O(n) 的时间复杂度所以此种方法运行的时间复杂度要低于递归的方法。
递归的方法更像是一种暴搜(暴力搜索每一种状态)所有搜索到的状态构成一颗递归搜索树搜索的次数就是所有树上的节点的个数可以看到递归搜索树的节点树远大于循环迭代次数其时间复杂度大约为 O ( 2 n − 2 ) O(2^{n - 2}) O(2n−2) 。
代码
方法一递推(迭代)
时间复杂度 O ( n ) O(n) O(n)
typedef long long ll;
const int N 70;ll fib_dp(int x) //递推
{vectorll dp(N,0);dp[0] 0,dp[1] 1;for (int i 2;i x;i ) {dp[i] dp[i - 1] dp[i - 2];}return dp[x];
}方法二递归
时间复杂度 O ( 2 n − 2 ) O(2^{n - 2}) O(2n−2)
typedef long long ll;
const int N 70;ll fib_recursion(int x) //递归
{if (!x) return 0;else if (x 1 || x 2) return 1;else {return fib_recursion(x - 1) fib_recursion(x - 2); //后序遍历的写法}
}
