作者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