最近在系統(tǒng)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法浸赫，初學(xué)編程時(shí)以練手題的形式見過(guò)斐波那契數(shù)列闰围，當(dāng)時(shí)僅僅是從「語(yǔ)法」角度進(jìn)行理解，如今再次見到既峡，從「算法」角度再次思考辫诅，多了一層理解。
斐波那契數(shù)列
指的是這樣一個(gè)數(shù)列：1涧狮、1、2么夫、3者冤、5、8档痪、13涉枫、21、……在數(shù)學(xué)上腐螟，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0愿汰，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2（n>=2乐纸，n∈N*）衬廷。
用文字來(lái)說(shuō)，就是斐波那契數(shù)列列由 0 和 1 開始汽绢，之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加吗跋。 --《百度百科》
代碼實(shí)現(xiàn)
如果就定義來(lái)實(shí)現(xiàn)此數(shù)列，要使用到遞歸函數(shù)：
//返回index位置的值
public int fib(int index) {
if (index<= 2) {
return 1;
} else {
return fib(index- 1) + fib(index- 2);
}
}
當(dāng)查詢位數(shù)較大時(shí)，會(huì)發(fā)現(xiàn)這種遞歸方法效率非常低跌宛，明顯這不是一個(gè)好的算法酗宋。
這里想要分析慢的原因，就要先說(shuō)下遞歸調(diào)用的四大基本準(zhǔn)則：
- ** 基準(zhǔn)情形**：必須總要有某些基準(zhǔn)的情形疆拘，它們不用遞歸就能進(jìn)行求解蜕猫。
- ** 不斷推進(jìn)**：對(duì)于那些需要遞歸求解的情形，遞歸調(diào)用必須總能夠朝著產(chǎn)生基準(zhǔn)情形的方向推進(jìn)哎迄。
- 設(shè)計(jì)法則：假設(shè)所有的遞歸調(diào)用都能運(yùn)行回右。
- 合成效益法則：在求解一個(gè)問(wèn)題的同一個(gè)實(shí)例時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)性的工作芬失。 _ --《數(shù)據(jù)結(jié)構(gòu)與算法 -C語(yǔ)言描述》_
這個(gè)例子中楣黍，就違反了第四條合成效益法則，比如當(dāng)傳入的index大于2時(shí)棱烂，會(huì)運(yùn)行else語(yǔ)句塊租漂。可以發(fā)現(xiàn)颊糜，當(dāng)調(diào)用fib(index- 1)時(shí)哩治，其實(shí)內(nèi)部已經(jīng)計(jì)算了后面要用到的fib(index- 2) ，但是這段運(yùn)算并沒(méi)有被使用衬鱼，而是被拋棄业筏，到了后面又再次調(diào)用了fib(index- 2)。這種行為產(chǎn)生了了大量重復(fù)運(yùn)算鸟赫，使得遞歸函數(shù)效率低下蒜胖。
那誰(shuí)說(shuō)得好：計(jì)算任何事情不要超過(guò)一次！
明白了這種遞歸的慢的原因抛蚤，就可以修改算法台谢，如下：
public int fib(int index) {
if (index <= 2)
return 1;
int f1 = 1;// 前前位
int f2 = 1;// 前一位
int fn = 0;
for (int i = 0; i < index - 2; i++) {
//這里是換位操作
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
return fn;
}
這種寫法就可以避免重復(fù)的操作與信息浪費(fèi)。
總之我們?cè)趯戇f歸的算法時(shí)岁经，一定要按照四個(gè)原則來(lái)朋沮，否則算法可能會(huì)有許多不合適的地方。
<br /><br />
