使用递归树方法求解带分数的递归方程
Solving recurrence equations with fractions using Recursion Tree Method
我正在尝试找出如何求解递归方程，如果方程是这样的，我可以使用递归树方法轻松地解决它们，例如：
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/2的树枝？使用递归树无法解决这个问题吗？谁能准确解释这在递归树方法中是如何工作的？或者对于这种形式的方程式，是否有另一种更容易的方法？
How can there be 3/2 th of a branch?
简单：你在一个步骤 x 上有 4 个分支，然后在步骤 x + 1 上你将有 4 * 3 / 2 = 6 个分支（如果你不能划分数字，使用 floor ).
Can anyone explain exactly how this would work in the recursion tree
method?
展开递归，创建一个巨大的和，发现相似性并收敛和。
Is there another method that would be easier for this form of equation?
是的，人们已经完成了我在上一步中描述的通用递归 T(n) = a T(n/b) + f(n) and created a theorem。你只需要记住它（实际上你需要理解它）并且你可以解决任何类型的递归。
我正在尝试找出如何求解递归方程，如果方程是这样的，我可以使用递归树方法轻松地解决它们，例如：
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/2的树枝？使用递归树无法解决这个问题吗？谁能准确解释这在递归树方法中是如何工作的？或者对于这种形式的方程式，是否有另一种更容易的方法？
How can there be
3/2 thof a branch?
简单：你在一个步骤 x 上有 4 个分支，然后在步骤 x + 1 上你将有 4 * 3 / 2 = 6 个分支（如果你不能划分数字，使用 floor ).
Can anyone explain exactly how this would work in the recursion tree method?
展开递归，创建一个巨大的和，发现相似性并收敛和。
Is there another method that would be easier for this form of equation?
是的，人们已经完成了我在上一步中描述的通用递归 T(n) = a T(n/b) + f(n) and created a theorem。你只需要记住它（实际上你需要理解它）并且你可以解决任何类型的递归。