推 ysbh:發現好東西~很用心的去看了一下，發現還是看不懂QQ 06/24 19:54
→ changdetrois:和上面老兄一樣感想，覺得是好東西，需要時間吸收 06/26 08:44
推 Byzantium: 不太懂代換求解那S(k-1)為什麼會等於T(n^0.5) 07/07 11:39
這邊提供一些我自己整理的筆記。
如果遞迴的形式是
T(n) = aT(n/b) + f(n) 那大部分都是直接套用Master Theorem
像是
T(n) = 2T(n/2) + n^3
T(n) = T(9n/10) + n
T(n) = 3T(n/2) + nlgn
除了原本Master Theorem之外，還有延伸版的Master Theorem
可以解
T(n) = 4T(n/2) + n^2 lgn
但是除了Master Theorem之外還有很多是不能直接套用的，要做一些轉換
我大概做了一下分類
遞迴樹展開求解
T(n) = 5T(n/5) + n/lgn
這式子看起來好像是符合Master Theorem，不過實際上不能套用，只好展開求解。
展開的時候要對遞迴樹夠熟。
遞迴轉成加總，遞迴跟加總是可以互換的（就好像遞迴跟迴圈一樣）
T(n) = T(n-1) + f(n)
只要針對f(n)去做加總就好
有時候運氣很好可以加出一個closed form
不行的話就只好找一些上下限來逼近，最簡單的就是積分法。
算不出來就用Euler's summation formula吧！
代換求解
T(n) = T(n^0.5) + f(n) <- 看到根號大多都是用這種方法
令n = 2^2^k, S(k) = T(2^2^k)
則S(k) = S(k-1) + f(2^2^k) 就可以用遞迴轉成加總來解了
T(n) = n^0.5 T(n^0.5) + f(n) <- 看到根號 * T(根號) 用這種方法比較容易算
兩邊要同除n，然後令S(n) = T(n)/n
S(n) = S(n^0.5) + f(n)/n 再用代換法就可以解決
Quick sort類的遞迴式
T(n)= k(T(1)+T(2)+...+T(n-1))/n + f(n)
先寫下T(n)和T(n-1)。
讓T(n)和T(n-1)兩個式子各乘上n和n-1之後相減。
相減之後可以使得T(1) + T(2) ... 那一串加總消失
只剩下T(n)和T(n-1)的關係，此時再用Telescoping或是遞迴轉成加總來做。
如果生成函數夠熟的話，也可以直接用生成函數做，很快就可以得到答案。
一堆加在一起的遞迴式
T(n) = T(n/a) + T(n/b) + T(n/c) ... + f(n)
這邊就要看a b c的總合和n的關係來決定該怎麼解
而且可以會Master theorem有對應
如果真的算不出來就套Akra-Bazzi method的公式吧！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51