Re: [問題] 關於遞迴加快速度的迷思？
※ 引述《LPH66 (f0VMRgEBA)》之銘言：
: ※ 引述《Schottky (Schottky)》之銘言：
: : 那麼 Fibonacci 整數數列本身也是可以用類似的二分再二分法去計算的,
: : 我一直在奇怪, 前面怎麼都沒有人提到過... 可能是目前用到的 n 太小的關係...
: : 令函數 f(n) = (a, b, c, d) 傳回值是四個係數, 代表以 F[0]=x, F[1]=y 開頭的
: : Fibonacci 數列, 其最後兩項為 F[n-1]=ax+by, F[n]=cx+dy,
: : 將兩條數列接起來, 則可推得 f(2n-1) = ((a^2+bc),(ab+bd),(ac+cd),(bc+d^2))
: : 所以我們只需要把數列切成等長的兩半計算, 算完再用上面的公式接起來即可...
: 其實應該是有提到過, 只是型式不一樣而已...
: 就是這條推文
: : 推 c2251393:是說可以構造矩陣((1, 1),(1, 0))來加速www 09/06 23:48
: 這個做法的原理是
: [1 1] . [y] = [x+y]
: [1 0] [x] [ y ]
: 所以我們有
: [1 1]^n . [f(1)] = [f(n+1)]
: [1 0] [f(0)] [ f(n) ]
: 那若我們記
: [1 1]^n = [d c] (這樣就有 [1 1]^n [y] = [d c] [y] = [cx+dy] )
: [1 0] [b a] [1 0] [x] [b a] [x] [ax+by]
: 則
: [1 1]^2n = [d c]^2 = [d^2+cb dc+ca ]
: [1 0] [b a] [db+ba cb+a^2]
: 這個矩陣正等同於你的遞迴式
: 因此 "對半"做矩陣次方的做法便等同於你的"將數列切對半"
: 這兩個做法是似二而實一的
這篇沒什麼奇淫怪技，只是一起討論而已。
先講一下，這題目在 程式之美-微軟技術面試心得 這本書裡面有收錄，
手邊有這本書的人可以先翻出來看一下，由於版權問題，我只概述裡面三種解法．．
(1) 定義解 f(n) = f(n-1) + f(n-2) , O(n)
(2) 近似解 f(n) = ( pow(1.0+sqrt(5.0), n) - pow(1.0-sqrt(5.0), n) ) /
( pow(2.0, 1) * sqrt(5.0) ) , O(1) , 精度問題
(3) 矩陣解 就如同 LPH66 所推演 , O(logn)。
然後具我所知，矩陣解在演算法 Big-O 可能是最佳的(不好意思我沒再翻文獻)，
但實際用電腦跑出來應該不是最快的 (吧)，
目前所知，mathmatica 用的算法不是 matrix method , 但跑得比較快。
---------
然後接下來有些 coder 會弄出一套自己的風格做加速的處理，
比如一開始說的直接用空間換時間、或做部份建表、
或是直接推導 fib ，可得其中一項特性：
f(2n)=f(n+1)f(n)+f(n)f(n-1) ，
上面這個不夠漂亮，下面兩個比較常用到
f(2n) = f(n) * ( 2f(n+1) - f(n) )
f(2n+1) = f(n+1)^2 + f(n)^2
然後上面這式子，其實某種層面與 matrix method 是一樣的，所以也屬 O(logn)。
另見過另一種算法，個人覺得蠻有趣的，先說，實際上效能應不怎麼佳。
n n
(1+√5) - (1-√5)
f(n) = －－－－－－－－－－－ ，
n
2 √5
n n
令 (1+√5) = A + B√5 ，則 (1-√5) = A-B√5，代入 f(n)，
A + B√5 - (A-B√5) B
f(n) = －－－－－－－－－－－ = －－－－－－－－－
n n-1
2 √5 2
關鍵就變成求 (1 + √5 ) ^ n 之 √5 係數，
疑！怎麼又變二項式問題了？然後若 n > 33(65) 成立的話又變大數問題了？
愈搞愈廣，這問題還是先停下來好了．．．
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
對我而言，遞迴函式有三種狀況我會想辦法改寫成非遞迴
1. 呼叫次數多
2. 瓶頸效能
3. 這支 recursive 執行時很可能會非常 "深層" ，導致可能會有 stack ov 情形時，
舉個例子，像是逼不得已的大數目排列組合問題時．．．
--
就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮，
永遠當老闆的傀儡 你是不是想這麼做？
是的話你就拿回去~ 拿啊！！
九世宅男 : 下輩子不要再讓我幹工程師了 ~
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.168.230
→
09/08 21:25, , 1F
09/08 21:25, 1F
討論串 (同標題文章)