algorithm - 使用递归树方法求解带分数的递归方程

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/2的 Twig ？使用递归树无法解决这个问题吗？谁能准确解释这在递归树方法中是如何工作的？或者对于这种形式的方程式，是否有另一种更容易的方法？

Answer 1

How can there be 3/2 th of a branch?

简单:您在 x 步上有 4 个分支，然后在 x + 1 步上您将有 4 * 3/2 = 6 branches(如果你不能划分数字，使用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 .您只需要记住它(实际上您需要理解它)，您就可以解决任何类型的递归问题。