※ 引述《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
: 解法2,3要O(logn)次n-bit的加法和乘法, 時間是O(n^2 logn)
: 這樣看來用加的會比較快 (一點點啦.. logn小到可以當常數)
: 而且簡單好寫XD
: (edit)
: 如果估計得緊一點的的話 方法2,3好像也是O(n^2)....
: 這樣就平手了~_~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.194.100
推
11/05 22:17, , 1F
11/05 22:17, 1F
討論串 (同標題文章)