需求
- 用JS計算斐波那契數(shù)列的第n個值
- 注意時間復(fù)雜度
- 0 1 1 2 3 5 8 13 21 34...
公式
- f(0) = 0
- f(1) = 1
- f(n) = f(n-1) + f(n-2)
功能實現(xiàn)-遞歸方式
/**
* @description 斐波那契數(shù)列 - 遞歸方式實現(xiàn)
*/
export const fibonacci = (n: number): number => {
if (n <= 0) return 0;
if (n === 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
遞歸分析
- 大量的重復(fù)計算
- 時間復(fù)雜度是 O(2^n)
- 遞歸方式完全不可用
優(yōu)化
- 不用遞歸芬骄，用循環(huán)
- 記錄中間結(jié)果
- 時間復(fù)雜度為 O(n)
功能實現(xiàn) - 循環(huán)方式
0 1 1 2 3 5 8 13 21 34
| | |
n2 n1 res
每次循環(huán) n1 n2 整體后移
/**
* @description 斐波那契數(shù)列 - 循環(huán)方式實現(xiàn)
*/
export const fibonacciLoop = (n: number): number => {
if (n <= 0) return 0;
if (n === 1) return 1;
let n1 = 1; // 記錄 n - 1 的結(jié)果
let n2 = 0; // 記錄 n - 2 的結(jié)果
let res = 0;
for (let i = 2; i <= n; i++) {
res = n1 + n2;
// 記錄中間結(jié)果
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 斐波那契數(shù)列單元測試
*/
import { fibonacciLoop } from '../src/utils/fibonacci';
describe('斐波那切數(shù)列', () => {
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
斐波那切數(shù)列
√ 0 和 1 (2 ms)
√ 正常情況 (1 ms)
√ n 小于 0
動態(tài)規(guī)劃
- 把一個大問題管毙，拆解為多個小問題，逐級向下拆解
- 用遞歸的思路分析問題寸谜，再改為循環(huán)來實現(xiàn)
- 算法三大思維：貪心鲸阻、二分六荒、動態(tài)規(guī)劃
動態(tài)規(guī)劃（dynamic programming养距，DP）是運籌學(xué)的一個分支尤筐，是求解決策過程最優(yōu)化的數(shù)學(xué)方法汇荐。動態(tài)規(guī)劃是對某類問題的解決方法，重點在于如何鑒定一類問題是動態(tài)規(guī)劃可解的而不是糾結(jié)用什么解決方法盆繁。動態(tài)規(guī)劃中狀態(tài)是非常重要的掀淘，它是計算的關(guān)鍵，通過狀態(tài)的轉(zhuǎn)移來實現(xiàn)問題的求解改基。當(dāng)嘗試使用動態(tài)規(guī)劃解決問題時繁疤，其實就是要思考如何將這個問題表達成狀態(tài)以及如何在狀態(tài)間轉(zhuǎn)移。動態(tài)規(guī)劃總是假設(shè)當(dāng)前已取得最好結(jié)果秕狰，再依據(jù)此結(jié)果去推導(dǎo)下一步行動稠腊。遞歸法將大問題分解為小問題，調(diào)用自身鸣哀。而動態(tài)規(guī)劃從小問題推導(dǎo)到大問題架忌，推導(dǎo)過程的中間值要緩存起來，這個推導(dǎo)過程稱為狀態(tài)轉(zhuǎn)移我衬。
動態(tài)規(guī)劃代碼是迭代叹放，比遞歸代碼簡潔不少饰恕，不像遞歸版本算法，它減少了棧的使用井仰。但要意識到埋嵌，能為一個問題寫遞歸解決方案并不意味著它就是最好的的解決方案。
遞歸費棧俱恶，容易爆內(nèi)存雹嗦。動態(tài)規(guī)劃則不好找準(zhǔn)轉(zhuǎn)移規(guī)則和起始條件，而這兩點又是必須的合是，所以動態(tài)規(guī)劃好用了罪，不好理解，代碼很簡單聪全，理解很費勁兒泊藕。同樣的問題，有時遞歸和動態(tài)規(guī)劃都能解決难礼，比如斐波那契數(shù)列問題娃圆，用兩者都能解決。
注意鹤竭，能用遞歸解決的踊餐，用動態(tài)規(guī)劃不一定都能解決。因為這兩者本身就是不同的方法臀稚，動態(tài)規(guī)劃需要滿足的條件吝岭，遞歸時不一定能滿足。這一點一定牢記吧寺，不要為了動態(tài)規(guī)劃而動態(tài)規(guī)劃窜管。
所有遞歸算法都必須要滿足三定律，遞歸在某些情況下可以代替迭代稚机，但迭代不一定能替代遞歸幕帆。遞歸算法通常可以自然地映射到所解決的問題的表達式赖条，看起來很直觀簡潔失乾。遞歸并不總是好的方案，有時遞歸解決方案可能比迭代算法在計算上更昂貴纬乍。尾遞歸是遞歸的優(yōu)化形式碱茁，能一定程度上減少棧資源使用。動態(tài)規(guī)劃可用于解決最優(yōu)化問題仿贬，通過小問題逐步構(gòu)建大問題纽竣，而遞歸是通過分解大問題為小問題來逐步解決。
