解决复发方程用递归树方法

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。所有你需要的是记住它（实际上你需要了解它），你可以解决任何这种递归。