这边提供一些我自己整理的笔记。 如果递回的形式是 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