技术支持东莞网站建设机械,有创意广告店名字大全,注册深圳公司恒诚信价格,世界工厂网怎么样斐波那契数列定义#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); //后序遍历的写法}
}
