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