作者zerodevil (冰心無情)
看板java
標題Re: Fibonacci number
時間Thu Nov 5 19:35:12 2009
※ 引述《tkcn (小安)》之銘言：
: → AmosYang:題外話:如果要拼F0到Fn全算的話，我 猜 解法一會大勝 XD 11/05 10:56
就算只問Fn 我也覺得解法一大勝XD
理由見下文
: → tkcn:這是當然..解法一只需要乘 n-1 次 11/05 10:58
: → AmosYang:不過不知道實際上 BigInteger 的加與乘的影響有多大... 11/05 11:27
: → AmosYang:(懶得去翻src出來看了) ICPC沒玩到，可以玩 topcoder.com 11/05 11:29
我來試著估計一下大數的影響..
由公式解可得 Fn = (1.618^n - (-0.618)^n) / √5
~= 1.618^n / √5
取log之後可看出Fn要用O(n)bit來存
n-bit的大數加法複雜度是O(n)
乘法複雜度是O(n^2) (如果你用FFT之類的火星演算法那另當別論XD)
所以我們回頭看解法1,2,3
解法1需要O(n)次n-bit的大數加法, 沒有乘法, 時間是O(n^2)
解法2,3要O(logn)次n-bit的加法和乘法, 時間是O(n^2 logn)
這樣看來用加的會比較快 (一點點啦.. logn小到可以當常數)
而且簡單好寫XD
(edit)
如果估計得緊一點的的話 方法2,3好像也是O(n^2)....
這樣就平手了~_~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.186.66
※ 編輯: zerodevil 來自: 220.133.186.66 (11/05 20:12)
1F：→ AmosYang:我今天實際試跑解法一、三,就F5000來說…只差0.001秒 orz 11/06 11:33
2F：→ AmosYang:但算F1000000時…解法一很快就餓死了 XD 11/06 11:37
memory炸了XD? 存前兩個數字就好啦~
※ 編輯: zerodevil 來自: 220.133.186.66 (11/06 12:19)
3F：→ AmosYang:剛再試了F1000000;解法一 105s 解法三 13s (我用C#) 11/06 13:04
4F：→ AmosYang:看來只能去研究 BigInteger 的實作才能論定了 XD (懶) 11/06 13:07
看來只差個常數倍而已 可以確定不是n和logn這種數量級的差距XD
(edit)好像又不太對.. 有可能在位數夠大之後改用複雜度較低的演算法實作乘法
※ 編輯: zerodevil 來自: 220.133.186.66 (11/06 15:02)
5F：→ sbrhsieh:有 gc 機制的執行環境下解法一需不需要考慮 gc 的影響？ 11/06 20:56