TS数据结构与算法之求斐波那契数列的第n值
需求
- 用JS计算斐波那契数列的第n个值
- 注意时间复杂度
- 0 1 1 2 3 5 8 13 21 34...
公式
- f(0) = 0
- f(1) = 1
- f(n) = f(n-1) + f(n-2)
功能实现-递归方式
/**
* @description 斐波那契数列 - 递归方式实现
*/
export const fibonacci = (n: number): number => {
if (n <= 0) return 0;
if (n === 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
递归分析
- 大量的重复计算
- 时间复杂度是 O(2^n)
- 递归方式完全不可用
优化
- 不用递归，用循环
- 记录中间结果
- 时间复杂度为 O(n)
功能实现 - 循环方式
0 1 1 2 3 5 8 13 21 34
| | |
n2 n1 res
每次循环 n1 n2 整体后移
/**
* @description 斐波那契数列 - 循环方式实现
*/
export const fibonacciLoop = (n: number): number => {
if (n <= 0) return 0;
if (n === 1) return 1;
let n1 = 1; // 记录 n - 1 的结果
let n2 = 0; // 记录 n - 2 的结果
let res = 0;
for (let i = 2; i <= n; i++) {
res = n1 + n2;
// 记录中间结果
n2 = n1;
n1 = res;
}
return res;
}
功能测试
export const fibonacciFunctionalTest = () => {
console.log(fibonacciLoop(0)); // 0
console.log(fibonacciLoop(3)); // 2
console.log(fibonacciLoop(6)); // 8
console.log(fibonacciLoop(9)); // 34
}
单元测试
/**
* @description 斐波那契数列单元测试
*/
import { fibonacciLoop } from '../src/utils/fibonacci';
describe('斐波那切数列', () => {
test('0 和 1', () => {
expect(fibonacciLoop(0)).toBe(0);
expect(fibonacciLoop(1)).toBe(1);
});
test('正常情况', () => {
expect(fibonacciLoop(2)).toBe(1);
expect(fibonacciLoop(3)).toBe(2);
expect(fibonacciLoop(6)).toBe(8);
});
test('n 小于 0', () => {
expect(fibonacciLoop(-1)).toBe(0);
});
});
运行 yarn jest:
PASS tests/fibonacci.test.ts
斐波那切数列
√ 0 和 1 (2 ms)
√ 正常情况 (1 ms)
√ n 小于 0
动态规划
- 把一个大问题，拆解为多个小问题，逐级向下拆解
- 用递归的思路分析问题，再改为循环来实现
- 算法三大思维：贪心、二分、动态规划
动态规划（dynamic programming，DP）是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划是对某类问题的解决方法，重点在于如何鉴定一类问题是动态规划可解的而不是纠结用什么解决方法。动态规划中状态是非常重要的，它是计算的关键，通过状态的转移来实现问题的求解。当尝试使用动态规划解决问题时，其实就是要思考如何将这个问题表达成状态以及如何在状态间转移。动态规划总是假设当前已取得最好结果，再依据此结果去推导下一步行动。递归法将大问题分解为小问题，调用自身。而动态规划从小问题推导到大问题，推导过程的中间值要缓存起来，这个推导过程称为状态转移。
动态规划代码是迭代，比递归代码简洁不少，不像递归版本算法，它减少了栈的使用。但要意识到，能为一个问题写递归解决方案并不意味着它就是最好的的解决方案。
递归费栈，容易爆内存。动态规划则不好找准转移规则和起始条件，而这两点又是必须的，所以动态规划好用，不好理解，代码很简单，理解很费劲儿。同样的问题，有时递归和动态规划都能解决，比如斐波那契数列问题，用两者都能解决。
注意，能用递归解决的，用动态规划不一定都能解决。因为这两者本身就是不同的方法，动态规划需要满足的条件，递归时不一定能满足。这一点一定牢记，不要为了动态规划而动态规划。
所有递归算法都必须要满足三定律，递归在某些情况下可以代替迭代，但迭代不一定能替代递归。递归算法通常可以自然地映射到所解决的问题的表达式，看起来很直观简洁。递归并不总是好的方案，有时递归解决方案可能比迭代算法在计算上更昂贵。尾递归是递归的优化形式，能一定程度上减少栈资源使用。动态规划可用于解决最优化问题，通过小问题逐步构建大问题，而递归是通过分解大问题为小问题来逐步解决。
