解決復發方程用遞歸樹方法

Question

我試圖找出如何解決遞歸方程，我可以很容易地他們用遞歸樹方法，如果公式是這樣的，比如做分數：

T(1) = 1; 
T(n) = n + 2T(n/2) for n > 1 

但我無法理解如何解決其復發是由一小部分修改的方程式，這樣的例子：

T(1) = 1; 
T(n) = n + 3/2T(.9n) for n > 1 

哪有一個分支在樹上3 /二路？使用遞歸樹解決這個問題是不可能的？任何人都可以解釋如何在遞歸樹方法中工作嗎？或者還有另一種方法對於這種形式的等式更容易嗎？

Answer 1

怎麼可能有一個分支3/2 th？

很簡單：你有一個一步x 4個分公司，然後一步x + 1你將有4 * 3/2 = 6分支（如果你不能分割的數字，使用地板）。

任何人都可以解釋這將如何工作在遞歸樹 方法？

您展開遞歸，創建一個巨大的總和，找出相似性並收斂總和。

是否有另一種方法可以更容易的這種形式的等式？

是的，人們已經完成了我在上一步描述的一般遞歸T(n) = a T(n/b) + f(n) and created a theorem。所有你需要的是記住它（實際上你需要了解它），你可以解決任何這種遞歸。