Re: Fibonacci number
※ 引述《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)
→
11/06 11:33, , 1F
11/06 11:33, 1F
→
11/06 11:37, , 2F
11/06 11:37, 2F
memory炸了XD? 存前兩個數字就好啦~
※ 編輯: zerodevil 來自: 220.133.186.66 (11/06 12:19)
→
11/06 13:04, , 3F
11/06 13:04, 3F
→
11/06 13:07, , 4F
11/06 13:07, 4F
看來只差個常數倍而已 可以確定不是n和logn這種數量級的差距XD
(edit)好像又不太對.. 有可能在位數夠大之後改用複雜度較低的演算法實作乘法
※ 編輯: zerodevil 來自: 220.133.186.66 (11/06 15:02)
→
11/06 20:56, , 5F
11/06 20:56, 5F
討論串 (同標題文章)