作者zerodevil (冰心無情)
看板java
標題Re: Fibonacci number
時間Thu Nov 5 22:51:01 2009
※ 引述《tkcn (小安)》之銘言：
: ※ 引述《zerodevil (冰心無情)》之銘言：
: : 我來試著估計一下大數的影響..
: : 由公式解可得 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)
: 呃...上面那串公式是什麼？
: 該不會又是什麼大學就教的東西吧！
: (老師~我對不起你~Orz)
線性遞迴的公式解
離散之類的可能會講到(?
: : 所以我們回頭看解法1,2,3
: : 解法1需要O(n)次n-bit的大數加法, 沒有乘法, 時間是O(n^2)
: 解法一應該是只有乘法沒有加法吧 :P
我們講的解法一是同一個東西嗎XD
f = new BigInt[n+1]
f[0] = f[1] = 1;
for(int i=2; i<=n; i++) f[i] = f[i-1] + f[i-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
1F：推 tkcn:哈 那應該是我誤會了，我再研究研究 11/05 23:00
2F：推 tkcn:噢 我把fabonacci跟factorial搞混了 XDDD 11/05 23:02
3F：→ tkcn:還有那個公式我現在有印象了 11/05 23:03
4F：推 SansWord:我有一個問題～fabonacci 不是可以解遞迴式嗎？ 11/06 00:07
5F：→ SansWord:那不就O(1)就可以解出來？ 11/06 00:08
6F：→ zerodevil:算公式解的時候那些加減乘除也是要時間的 11/06 02:10
7F：推 KanoLoa:小聲偷問，有跟我一樣整串看下來都不懂的人嗎，我要取暖QQ 11/06 02:56
8F：→ jlovet:遞迴不用多久就會爆炸吧 11/06 03:42
9F：推 SansWord:公式：1/√5 { [ (1+√5)/2 ]^n - [ (1-√5)/2 ]^n } 11/06 06:02
10F：→ SansWord:算這個應該constant time吧? 11/06 06:03
11F：→ tkcn:直接代公式 √5 要怎麼辦? 他可不是分數呀 11/06 09:02
12F：→ AmosYang:ICPC 進場可以帶紙本的筆記； √5 算個100位印在紙上 11/06 11:23
13F：→ AmosYang:帶進場，然後用 BigDecimal 硬幹? XD 11/06 11:24
15F：→ AmosYang:人; rounding error 沒在怕的啦 XD 11/06 11:28
16F：推 SansWord:按照這個公式，√5 項會被消掉，大可用一個變數替代 11/06 12:53
17F：推 SansWord:然後偶數次再算出來 11/06 12:57
先不考慮無理數什麼的
你光算一個數的n次方就至少要O(logn)次乘法了
※ 編輯: zerodevil 來自: 220.133.186.66 (11/06 13:05)
18F：→ AmosYang:(亂入) 如果是做 applied physics 的題目… 11/06 13:13
19F：→ AmosYang:精確度有到千分之一通常就很夠了 XD (逃) 11/06 13:15
20F：推 tkcn:我覺得100位應該是完全不夠吧, 要更多就會有大數乘法慢的問題 11/06 13:17
21F：推 SansWord:也對，後來想到次方也是需要O(logN) 11/06 14:18