斐波那契数列
JavaScript实现LeetCode第509题：斐波那契数列
斐波那契数列
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
1.暴力递归
/**
* @param {number} N
* @return {number}
*/
var fib = function(N) {
// N小于等于1，则直接返回 N
if (N <= 1) {
return N;
}
// 通过递归关系调用自身
return fib(N-1) + fib(N-2);
};
- 时间复杂度：O(2^n)。这是计算斐波那契数最慢的方法。因为它需要指数的时间。
- 空间复杂度：O(N)，在堆栈中我们需要与 N 成正比的空间大小。该堆栈跟踪 fib(N) 的函数调用，随着堆栈的不断增长如果没有足够的内存则会导致 栈溢出。
该方法存在大量重复的递归计算，例如 f(N) 和 f(N - 1) 两者向下递归需要 各自计算 f(N - 2) 的值。
2. 递归加缓存
原理：在递归法的基础上，新建一个长度为 N 的数组，用于在递归时存储 f(0) 至 f(N) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
/**
* @param {number} N
* @return {number}
*/
let cache = [0, 1];
function fib(N) {
return typeof cache[N] === 'number' ? cache[N] : cache[N] = fib(N - 1) + fib(N - 2);
}
- 时间复杂度：O(N)。
- 空间复杂度：O(N)，使用了空间大小为 N 的数组。
3. 动态规划
使用 dp数组
/**
* @param {number} N
* @return {number}
*/
function fib(N) {
const dp = [0, 1];
for(let i = 2; i <= N; i++) {
dp[i] = dp[i -1] + dp[i-2];
}
return dp[N];
}
- 时间复杂度：O(N)。
- 空间复杂度：O(N)，使用了空间大小为 N 的 dp 数组。
空间复杂度优化：
- 由于 dp 数组的第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个变量 current, prev1, prev2 ，利用辅助变量 current 使 prev1, prev2 两数字交替前进即可
- 节省了 dp 数组的空间，因此空间复杂度降至 O(1) 。
/**
* @param {number} N
* @return {number}
*/
function fib(N) {
// 若 N <= 1，则返回 N
if (N <= 1) {
return N;
}
// 若 N == 2，则返回 fib(2-1) + fib(2-2) = 1
if (N == 2) {
return 1;
}
// 至少需要三个变量存储 fib(N), fib(N-1) 和 fib(N-2)。
let current = 0; // 代表 fib(N)
let prev1 = 1; // 代表fib(N-1)
let prev2 = 1; // 代表 fib(N-2)
for (let i = 3; i <= N; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
- 时间复杂度：O(N)。
- 空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。
这是一道经典的面试题，笔者已经记不清楚有多少次面试中被问过这道题目了，其实想明白之后就会非常简单，要搞清楚为什么这三种方法，尤其是后两种比前一种做了哪些优化使其性能提升了。当然这道题有个限制 0 ≤ N ≤ 30 ，所以执行的时候，这三种方法的差异并不是很大，大家可以尝试一下比较大的数，就能体会到差异，真的是差很多。
参考
- leetcode题解[1]
参考资料
[1]
leetcode题解: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/mian-shi-ti-10-i-fei-bo-na-qi-shu-lie-dong-tai-gui/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-04-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
