求解递推方程T（n）=3 m*T（n-m）

Question

我明天有一个计算机科学期中考试，我需要帮助确定一个特定递归函数的复杂性，如下所示，这比我已经研究过的东西要复杂得多：它有两个变量

T（n）=3 mT（n-m）

在m为常数的简单情况下，可以通过编写解包关系轻松获得公式；然而，在这种情况下，拆包并不会使生活变得更容易，如下所示（假设t（0）=c）：

T（n）=3 mT（n-m）

T（n-1）=3 mT（n-m-1）

T（n-2）=3 mT（n-m-2）

...

显然，根据这些不等式，没有直接的消去法。所以，我想知道我是否应该对这种情况使用另一种技术。

Answer 1

不要担心m，这只是一个常数。然而，您错误地展开了递归。展开的每个步骤涉及三个操作：

1. 取T的值和自变量值，其小于m

所以，它看起来像这样：

T(n) = m * T(n - m) + 3 =                                        (Step 1)
     = m * (m * T(n - 2*m) + 3) + 3 =                            (Step 2)
     = m * (m * (m * T(n - 3*m) + 3) + 3) + 3 = ...              (Step 3)

等等展开T（n）到步骤k将由以下公式得出：

T(n) = m^k * T(n - k*m) + 3 * (1 + m + m^2 + m^3 + ... + m^(k-1))

现在设置n-k*m=0，使用初始条件T（0），得到：

k = n / m

现在你需要使用一个几何级数和的公式-最后你会得到一个T（n）的闭合公式（我把最后一步留给你）。