Re: Fibonacci number

看板java作者zerodevil (冰心無情)時間16年前 (2009/11/05 22:51)推噓9(9推 0噓 12→)

留言21則, 6人參與討論串7/7 (看更多)

※ 引述《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

推

tkcn

11/05 23:00, , 1^F

11/05 23:00, 1^F

推

tkcn

11/05 23:02, , 2^F

11/05 23:02, 2^F

→

tkcn

11/05 23:03, , 3^F

11/05 23:03, 3^F