這邊提供一些我自己整理的筆記。 如果遞迴的形式是 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