討論串(共7篇) - Fibonacci number - 看板java

就算只問Fn 我也覺得解法一大勝XD. 理由見下文我來試著估計一下大數的影響... 由公式解可得 Fn = (1.618^n - (-0.618)^n) / √5. ~= 1.618^n / √5. 取log之後可看出Fn要用O(n)bit來存. n-bit的大數加法複雜度是O(n). 乘法複雜度是

(還有404個字)

Re: Fibonacci number

推噓1(1推 )留言7則，0人參與作者tkcn (小安)時間15年前 (2009/11/04 09:09)資訊

內容預覽:

確實如 jlovet 所說，. f(n-1) f(n). f(n) f(n+1). 此種型式的矩陣相乘(平方)，. 只需要 4 次乘法與 3 次加法. 因此 f(10000) 使用 bottom-up，. 乘法次數為: 13*4 + 4*4 = 68. 加法次數為: 13*3 + 4*2 = 47.

Re: Fibonacci number

推噓0(0推 )留言0則，0人參與作者jlovet (打不贏怪兵器不好)時間15年前 (2009/11/04 08:43)資訊

內容預覽:

F(n+1) F(n) F(n+1) F(n). F(n) F(n-1) * F(n) F(n-1). =. F(n+1)*F(n+1)+F(n)*F(n) F(n+1)*F(n)+F(n)*F(n-1). F(n+1)*F(n)+F(n)*F(n-1) F(n)*F(n)+F(n-1)*F(n-1

(還有2個字)

首頁

尾頁