最近不忙互婿，準(zhǔn)備鞏固一下基本功，看了點(diǎn)算法的東西辽狈。這里記錄一下斐波那契數(shù)列算法慈参，及其對(duì)于時(shí)間復(fù)雜度的優(yōu)化方法。
關(guān)于斐波那契數(shù)列稻艰，傳送門(mén)在此懂牧。
就是這樣的數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55......
從第三項(xiàng)開(kāi)始侈净，每一項(xiàng)等于前兩項(xiàng)之和尊勿，不多BB，往下看
一畜侦、遞歸（最容易想到的方法）
這個(gè)數(shù)列的第 0 項(xiàng)我們一般看作是 0元扔，即：
| 數(shù)列第 n 項(xiàng) | 表達(dá)式 | 條件 |
|---|---|---|
| 0 | n = 0 時(shí) | |
| F(n) = | 1 | n = 1 時(shí) |
| F(n - 1) + F(n - 2) | n >= 2 時(shí) |
代碼實(shí)現(xiàn)如下(只考慮 n 是自然數(shù)的情況):
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
雖說(shuō)能正確計(jì)算，但是其僅在 n <= 1 時(shí)旋膳，時(shí)間復(fù)雜度為 O(1)
當(dāng) n >= 2 時(shí)
F(5)
/ \
F(3) F(4)
/ \ / \
F(1) F(2) F(2) F(3)
/ \ / \ / \
通過(guò)這個(gè)樹(shù)澎语，我們能看出它的時(shí)間復(fù)雜度是 O(2^n)
話(huà)說(shuō)大學(xué)時(shí)候，學(xué)校的 OJ 上做過(guò)這題，當(dāng)時(shí)就是用的遞歸擅羞，AC 以后就沒(méi)再繼續(xù)深入研究過(guò)
二尸变、利用數(shù)組（可將時(shí)間復(fù)雜度優(yōu)化為 O(n) ）
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
var arr = [];
arr[0] = 0;
arr[1] = 1;
for (var i = 2; i <= n; i ++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n]
}
}
也是挺巧妙的一種方法，不過(guò)需要?jiǎng)?chuàng)建數(shù)組减俏，占用了一定的內(nèi)存空間召烂，雖說(shuō)現(xiàn)在的手機(jī)、電腦也不差這點(diǎn)內(nèi)存娃承，但是還是可以?xún)?yōu)化一下
三奏夫、利用中間變量（時(shí)間復(fù)雜度也是 O(n)，但可以節(jié)省空間）
同方法二思想類(lèi)似历筝，不過(guò)不使用數(shù)組
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
var temp0 = 0;
var temp1 = 1;
var fn = 0;
for (var i = 2; i <= n; i ++) {
fn = temp0 + temp1;
temp0 = temp1;
temp1 = fn;
}
return fn
}
}
變量位置互換的思想
四酗昼、利用矩陣（可將時(shí)間復(fù)雜度優(yōu)化為 O(log n) ）
這個(gè)就屬于用空間換時(shí)間了
話(huà)說(shuō)這個(gè)矩陣我好像還給了大學(xué)老師，等我看會(huì)了再寫(xiě)上來(lái)梳猪，尷尬
五麻削、高中數(shù)學(xué)（ O(1) ）
這個(gè)就是高中數(shù)學(xué)知識(shí)了，構(gòu)造等比數(shù)列春弥，求通項(xiàng)
話(huà)說(shuō)這個(gè)好像也還給高中老師了碟婆，好在高中數(shù)學(xué)還不錯(cuò)，撿了回來(lái)
鵬哥帶你們復(fù)習(xí)一下高中數(shù)學(xué)：
已知等比數(shù)列：1, 3, 9, 27, 81...... 求其第 n 項(xiàng)
很顯然公比為 3惕稻，直接套公式竖共，a(n) = a(1) * q^(n - 1)
即 a(n) = 3^(n - 1)
話(huà)說(shuō)這個(gè) markdown 寫(xiě)數(shù)學(xué)公式是真難受啊
然后在看這個(gè)斐波那契數(shù)列，看起來(lái)不是等比俺祠，這就需要我們?nèi)?gòu)造等比公给，眼前浮現(xiàn)出高中數(shù)學(xué)老師粉筆一揮，抑揚(yáng)頓挫的說(shuō)差后成等比的情景蜘渣，懷念啊……
推導(dǎo)過(guò)程有點(diǎn)長(zhǎng)淌铐，有空我整理下再發(fā)上來(lái)，先看通項(xiàng)
function Fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var ratio = 1 / sqrt5;
var base1 = (sqrt5 + 1) / 2;
var base2 = (1 - sqrt5) / 2;
var fn = ratio * (Math.pow(base1, n) + (Math.pow(base2, n)));
return Math.round(fn);
}
不過(guò)這個(gè)蔫缸，浮點(diǎn)數(shù)你懂的腿准，精度上要差一些。
這里只是做以討論拾碌，沒(méi)有考慮浮點(diǎn)數(shù)加減乘除的問(wèn)題吐葱，n <= 75 時(shí)是正確的，n = 76 時(shí)就開(kāi)始有偏差了校翔，關(guān)于浮點(diǎn)數(shù)運(yùn)算問(wèn)題有空再寫(xiě)吧
根據(jù)情況選擇對(duì)應(yīng)的方法吧弟跑，數(shù)值越大，矩陣運(yùn)算的時(shí)間優(yōu)勢(shì)體現(xiàn)越明顯
