作者tkcn (小安)
看板java
标题Re: Fibonacci number
时间Thu Nov 5 21:45:34 2009
※ 引述《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
1F：推 PsMonkey:FFT？ 快速傅立叶？ @_@??? 11/05 22:17